100214. Ant on the Boundary
边界上有一只蚂蚁，它有时向 左 走，有时向 右 走。
给你一个 非零 整数数组 nums 。蚂蚁会按顺序读取 nums 中的元素，从第一个元素开始直到结束。每一步，蚂蚁会根据当前元素的值移动：
- 如果 nums[i] < 0 ，向 左 移动 -nums[i]单位。
- 如果 nums[i] > 0 ，向 右 移动 nums[i]单位。
返回蚂蚁 返回 到边界上的次数。
注意：
- 边界两侧有无限的空间。
- 只有在蚂蚁移动了 |nums[i]| 单位后才检查它是否位于边界上。换句话说，如果蚂蚁只是在移动过程中穿过了边界，则不会计算在内。
测试样例：
输入：nums = [2,3,-5]
输出：1
解释：第 1 步后，蚂蚁距边界右侧 2 单位远。第 2 步后，蚂蚁距边界右侧 5 单位远。第 3 步后，蚂蚁位于边界上。所以答案是 1 。
解答：这题按照题意hard code，判断每次蚂蚁走完，是不是在0点。
class Solution {
public int returnToBoundaryCount(int[] nums) {
int pos = 0, res = 0;
for (int n : nums) {
pos += n;
if (pos == 0) {
++res;
}
}
return res;
}
}100189. Find the Grid of Region Average
给你一个下标从 0 开始、大小为 m x n 的网格 image ，表示一个灰度图像，其中 image[i][j] 表示在范围 [0..255] 内的某个像素强度。另给你一个 非负 整数 threshold 。
如果 image[a][b] 和 image[c][d] 满足 |a - c| + |b - d| == 1 ，则称这两个像素是 相邻像素 。
区域 是一个 3 x 3 的子网格，且满足区域中任意两个 相邻 像素之间，像素强度的 绝对差 小于或等于 threshold 。
区域 内的所有像素都认为属于该区域，而一个像素 可以 属于 多个 区域。
你需要计算一个下标从 0 开始、大小为 m x n 的网格 result ，其中 result[i][j] 是 image[i][j] 所属区域的 平均 强度，向下取整 到最接近的整数。如果 image[i][j] 属于多个区> 域，result[i][j] 是这些区域的 “取整后的平均强度” 的 平均值，也 向下取整 到最接近的整数。如果 image[i][j] 不属于任何区域，则 result[i][j] 等于 image[i][j] 。
返回网格 result 。
测试样例：
输入：image = [[5,6,7,10],[8,9,10,10],[11,12,13,10]], threshold = 3
输出：[[9,9,9,9],[9,9,9,9],[9,9,9,9]]
解释：图像中存在两个区域，如图片中的阴影区域所示。第一个区域的平均强度为 9 ，而第二个区域的平均强度为 9.67 ，向下取整为 9 。两个区域的平均强度为 (9 + 9) / 2 = 9 。由于所有像素都属于区域 1 、区域 2 或两者，因此 result 中每个像素的强度都为 9 。注意，在计算多个区域的平均值时使用了向下取整的值，因此使用区域 2 的平均强度 9 来进行计算，而不是 9.67 。
解答：这周周赛码量最大的一题了。这题范围不大，所以可以直接暴力枚举每个3*3的子网格是否满足threshold要求，满足的话，就对所有成员递增结果。
class Solution {
private static final int[][] moves = {{-1,0},{1,0},{0,0},{-1,-1},{1,-1},{0,-1},{-1,1},{1,1},{0,1}};
private static final int[] adj = {1,0,-1,0,1};
public int[][] resultGrid(int[][] image, int threshold) {
int m = image.length, n = image[0].length;
int[][] count = new int[m][n], sum = new int[m][n];
for (int i = 1; i < m - 1; ++i) {
for (int j = 1; j < n - 1; ++j) {
int subSum = 0;
for (int[] mv : moves) {
int x = i + mv[0], y = j + mv[1];
for (int k = 0; k < 4; ++k) {
int xt = x + adj[k], yt = y + adj[k + 1];
if (xt >= i - 1 && xt <= i + 1 && yt >= j - 1 && yt <= j + 1) {
if (Math.abs(image[xt][yt] - image[x][y]) > threshold) {
subSum = -1;
break;
}
}
}
if (subSum == -1) {
break;
} else {
subSum += image[x][y];
}
}
if (subSum != -1) {
for (int[] mv : moves) {
int x = i + mv[0], y = j + mv[1];
count[x][y] += 1;
sum[x][y] += subSum / 9;
}
}
}
}
int[][] res = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (count[i][j] == 0) {
res[i][j] = image[i][j];
} else {
res[i][j] = sum[i][j] / count[i][j];
}
}
}
return res;
}
}100203. Minimum Time to Revert Word to Initial State II
给你一个下标从 0 开始的字符串 word 和一个整数 k 。
在每一秒，你必须执行以下操作：
- 移除 word 的前 k 个字符。
- 在 word 的末尾添加 k 个任意字符。
注意 添加的字符不必和移除的字符相同。但是，必须在每一秒钟都执行 两种 操作。
返回将 word 恢复到其 初始 状态所需的 最短 时间（该时间必须大于零）。
测试样例：
输入：word = "abacaba", k = 3
输出：3
解释：第 1 秒，移除 word 的前缀 "aba"，并在末尾添加 "bac" 。因此，word 变为 "cababac"。第 2 秒，移除 word 的前缀 "cab"，并在末尾添加 "aba" 。因此，word 变为 "abacaba" 并恢复到始状态。可以证明，2 秒是 word 恢复到其初始状态所需的最短时间。
解答：这题需要考察前缀和后缀是否一致。没想到啥好办法，所以就直接利用rolling hash来解决。首先利用hash快速判断前后缀子字符串是否一致，一致的位置标为true。然后开始模拟操作。如果所有字符都被操作过了，那么当前一定可以一致。否则就是要确保前后缀一致，即time之后到达标志为true的位置。
class Solution {
private static final int mod = 1_000_000_007;
public int minimumTimeToInitialState(String word, int k) {
int len = word.length();
boolean[] isValid = new boolean[len];
long left = 0, right = 0, mul = 1;
for (int i = 0, j = len - 1; i < word.length(); ++i, --j) {
left = ((word.charAt(i) - 'a') * mul + left) % mod;
right = ((right * 31) + word.charAt(j) - 'a') % mod;
mul = (mul * 31) % mod;
if (left == right) {
isValid[j] = true;
}
}
int pos = k, time = 1;
while (pos < word.length()) {
if (isValid[pos]) {
return time;
}
pos += k;
++time;
}
return time;
}
}