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;
}
};
