算法提升——LeetCode383场周赛总结

周赛题目

边界上的蚂蚁

边界上有一只蚂蚁，它有时向左走，有时向右走。

给你一个非零整数数组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 子网格内的 resultfor (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算法不甚了解，后续需要学习该算法，并输出一篇总结笔记。