周赛题目
边界上的蚂蚁
边界上有一只蚂蚁，它有时向左走，有时向右走。
给你一个非零整数数组nums。蚂蚁会按顺序读取nums中的元素，从第一个元素开始直到结束。每一步，蚂蚁会根据当前元素的值移动：
如果nums[i]<0，向左移动-nums[i]单位。
如果nums[i]>0，向右移动nums[i]单位。
返回蚂蚁返回到边界上的次数。
解题思路
本题是一道简单题，只要看懂题目，知道是求每次+nums[i]后的值为0的次数即可。
class Solution {
public int returnToBoundaryCount(int[] nums) {
int result=0;
int target=0;
for(int tem:nums){
target+=tem;
if (target==0){
result++;
}
}
return result;
}
}
将单词恢复初始状态所需的最短时间 I
给你一个下标从0开始的字符串word和一个整数k。
在每一秒，你必须执行以下操作：
移除word的前k个字符。
在word的末尾添加k个任意字符。
注意添加的字符不必和移除的字符相同。但是，必须在每一秒钟都执行两种操作。
返回将word恢复到其初始状态所需的最短时间（该时间必须大于零）。
解题思路
本题需要至少切割1次，最多切割len/k向上取整次必然可以恢复。因为每次切割后面是拼接任意字符，所以只需要考虑切割后剩余的字符串是不是原来word的开头即可。
class Solution {
public int minimumTimeToInitialState(String word, int k) {
int result=0;
int start=k;
int len=word.length();
int sum = (int) Math.ceil((double) len / k);
while(start<len){
result++;
if (word.indexOf(word.substring(start))==0){
return result;
}
start+=k;
}
return sum;
}
}
找出网格的区域平均强度
给你一个下标从0开始、大小为mxn的网格image，表示一个灰度图像，其中image[i][j]表示在范围[0…255]内的某个像素强度。另给你一个非负整数threshold。
如果image[a][b]和image[c][d]满足|a-c|+|b-d|==1，则称这两个像素是相邻像素。
区域是一个3x3的子网格，且满足区域中任意两个相邻像素之间，像素强度的绝对差小于或等于threshold。
区域内的所有像素都认为属于该区域，而一个像素可以属于多个区域。
你需要计算一个下标从0开始、大小为mxn的网格result，其中result[i][j]是image[i][j]所属区域的平均强度，向下取整到最接近的整数。如果image[i][j]属于多个区域，result[i][j]是这些区域的“取整后的平均强度”的平均值，也向下取整到最接近的整数。如果image[i][j]不属于任何区域，则result[i][j]等于image[i][j]。
返回网格result。
解题思路
遍历所有3*3的子网格，如果存在差值超过threshwold则跳过；如果合法则计算平均值。
public class Solution {
public int[][] resultGrid(int[][] a, int threshold) {
int m = a.length;
int n = a[0].length;
int[][] result = new int[m][n];
int[][] cnt = new int[m][n];
for (int i = 2; i < m; i++) {
next: // 定义跳出标签
for (int j = 2; j < n; j++) {
// 检查左右相邻格子
for (int x = i - 2; x <= i; x++) {
if (Math.abs(a[x][j - 2] - a[x][j - 1]) > threshold || Math.abs(a[x][j - 1] - a[x][j]) > threshold) {
continue next; // 不合法，跳出双重循环
}
}
// 检查上下相邻格子
for (int y = j - 2; y <= j; ++y) {
if (Math.abs(a[i - 2][y] - a[i - 1][y]) > threshold || Math.abs(a[i - 1][y] - a[i][y]) > threshold) {
continue next; // 不合法，跳出双重循环
}
}
// 合法，计算 3x3 子网格的平均值
int avg = 0;
for (int x = i - 2; x <= i; x++) {
for (int y = j - 2; y <= j; y++) {
avg += a[x][y];
}
}
avg /= 9;
// 更新 3x3 子网格内的 result
for (int x = i - 2; x <= i; x++) {
for (int y = j - 2; y <= j; y++) {
result[x][y] += avg; // 先累加，最后再求平均值
cnt[x][y]++;
}
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (cnt[i][j] == 0) {
// (i,j) 不属于任何子网格
result[i][j] = a[i][j];
} else {
result[i][j] /= cnt[i][j]; // 求平均值
}
}
}
return result;
}
}
将单词恢复初始状态所需的最短时间 II
给你一个下标从0开始的字符串word和一个整数k。
在每一秒，你必须执行以下操作：
移除word的前k个字符。
在word的末尾添加k个任意字符。
注意添加的字符不必和移除的字符相同。但是，必须在每一秒钟都执行两种操作。
返回将word恢复到其初始状态所需的最短时间（该时间必须大于零）。
解题思路
这道题和第二道题截图思路是一样的，但是不能再用JDK自带的方法区解，会超时。从第二道题中我们能看出来本题的本质上计算s的后缀和s的最长公共前缀的长度，即使用哦个扩展KMP判断，如果最长公共前缀的长度大于等于后缀长度，说明操作可以恢复到初始值。
class Solution {
public int minimumTimeToInitialState(String S, int k) {
char[] s = S.toCharArray();
int n = s.length;
int[] z = new int[n];
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r) {
z[i] = Math.min(z[i - l], r - i + 1);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
l = i;
r = i + z[i];
z[i]++;
}
if (i % k == 0 && z[i] >= n - i) {
return i / k;
}
}
return (n - 1) / k + 1;
}
}
总结
通过总结周赛的解法，学习到自己还有很多不足。同时也学到了一个平时开发不会用到的操作，就是如何用continue跳出双重循环。
后续因为本次题目中所使用到的KMP算法不甚了解，后续需要学习该算法，并输出一篇总结笔记。
