leetcode 第 383 场算法比赛

零、背景

晚上吃完饭，突然想起来今天周日，leetcode 比赛还没做。

便看了下，发现这次比赛的题都比较简单，而且最后一题可以使用字符串hash代替kmp和后缀树算法，百试不爽。

A: 循环判断前缀和。
B: 枚举后缀是否与前缀相等。
C: 暴力预处理所有区域，最后求平均值。
D: 字符串hash快速比较前缀与后缀是否相等。

一、边界上的蚂蚁

题意：给一个数组，代表左右移动的步长，问移动后到达原点的次数。

思路：求前缀和，判断是否在原点。

二、将单词恢复初始状态所需的最短时间 I

题意：给一个字符串，每次可以删除前缀 k 个字符，并追加任意 k 个字符，问几次操作才能使得字符串与原字符串相等。

思路：假设进行 i 次后匹配，共删除 i*k个字符，剩余n-i*k个字符。
说明长度为 n-i*k 的后缀与前缀相等。

换句话说，需要找到最小的 i，使得后缀与前缀相等。

数据范围不大，枚举所有 i，判断前缀与后缀是否相等即可。
复杂度：O(n/k * n)

三、找出网格的区域平均强度

题意：给一个数字矩阵，求每个位置所属区域平均值的平均值，如果不存在，返回原位置值。
区域定义：如果一个3*3的正方形内相邻的数字的差都不大于 K，则称这个正方形为一个区域，区域的平均值为。
区域平均值定义：区域内所有数字和除以数字个数。

思路：分为两个步骤。
第一步，预处理出所有满足要求的区域平均值，储存在左上角位置。
第二步，枚举一个位置所属的9个正方形，看是否有区域存在，存在了求平均值。

四、将单词恢复初始状态所需的最短时间 II

题意：与第二题一样，数据范围变大了。

思路：使用 hash 预处理字符串, 然后把第二题代码中 strncmp 换成前缀与后缀的hash判断即可。

五、最后

这次比赛比较简单，最后一题直接使用前后缀字符串 hash 来暴力枚举即可轻松通过。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code