1.边界上的蚂蚁(模拟)
class Solution {
public:int returnToBoundaryCount(vector<int>& nums) {int n = nums.size();int res = 0, cnt = 0;for(int i = 0; i < n; i++){res += nums[i];if(res == 0) cnt++;}return cnt;}
};
2.将单词恢复初始状态所需的最短时间 I(Z函数)
class Solution {
public:int minimumTimeToInitialState(string word, int k) {int n = word.size();vector<int> z(n);z[0] = n - 1;// z函数匹配for(int i = 1, l = 0, r = 0; i < n; i++){if(i <= r) z[i] = min(z[i - l], r - i + 1);while(word[z[i]] == word[i + z[i]]) z[i]++;if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;}for(int i = 1; i < n; i++){// 如果是k的倍数,且后缀和前缀匹配,那就返回操作次数if(i % k == 0 && z[i] == n - i) return i / k;}// n / k 向上取整 return (n - 1) / k + 1;}
};
3.找出网格的区域平均强度(模拟)
class Solution {
public:vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {int n = image.size();int m = image[0].size();// 存储平均值vector<vector<int>> res(n, vector<int>(m, 0));// 存储每个区域重合多少次 vector<vector<int>> cnt(n, vector<int>(m, 0));// 遍历右下角下角for(int i = 2; i < n; i++){for(int j = 2; j < m; j++){int f = 1;// 检查左右相邻的格子for(int k = i - 2; k <= i; k++){if(abs(image[k][j - 2] - image[k][j - 1]) > threshold || abs(image[k][j - 1] - image[k][j]) > threshold){f = 0;break;} }if(!f) continue;// 检查上下相邻的格子for(int k = j - 2; k <= j; k++){if(abs(image[i - 2][k] - image[i - 1][k]) > threshold || abs(image[i - 1][k] - image[i][k]) > threshold){f = 0;break;}}if(!f) continue;// 计算平均值int avg = 0;for(int k = i - 2; k <= i; k++){for(int z = j - 2; z <= j; z++){avg += image[k][z];}}avg /= 9;// 累加每个位置的平均值和统计每个位置重合次数for(int k = i - 2; k <= i; k++){for(int z = j - 2; z <= j; z++){res[k][z] += avg;cnt[k][z]++;}}}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(!cnt[i][j]) res[i][j] = image[i][j];else res[i][j] /= cnt[i][j];}}return res;}
};
4.将单词恢复初始状态所需的最短时间 II(z函数)
class Solution {
public:int minimumTimeToInitialState(string word, int k) {int n = word.size();vector<int> z(n);z[0] = n - 1;// z函数匹配for(int i = 1, l = 0, r = 0; i < n; i++){if(i <= r) z[i] = min(z[i - l], r - i + 1);while(word[z[i]] == word[i + z[i]]) z[i]++;if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;}for(int i = 1; i < n; i++){// 如果是k的倍数,且后缀和前缀匹配,那就返回操作次数if(i % k == 0 && z[i] == n - i) return i / k;}// n / k 向上取整 return (n - 1) / k + 1;}
};