目录
100214. 边界上的蚂蚁
题目描述
原题链接
思路分析
代码详解
100204. 将单词恢复初始状态所需的最短时间 I
题目描述
原题链接
思路分析
代码详解
100189. 找出网格的区域平均强度
题目描述
原题链接
思路分析
代码详解
100203. 将单词恢复初始状态所需的最短时间 II
题目描述
原题链接
思路分析
代码详解
100214. 边界上的蚂蚁
题目描述
边界上有一只蚂蚁,它有时向 左 走,有时向 右 走。
给你一个 非零 整数数组 nums 。蚂蚁会按顺序读取 nums 中的元素,从第一个元素开始直到结束。每一步,蚂蚁会根据当前元素的值移动:
- 如果 nums[i] < 0 ,向 左 移动 -nums[i]单位。
- 如果 nums[i] > 0 ,向 右 移动 nums[i]单位。
返回蚂蚁 返回 到边界上的次数。
注意:
- 边界两侧有无限的空间。
- 只有在蚂蚁移动了 |nums[i]| 单位后才检查它是否位于边界上。换句话说,如果蚂蚁只是在移动过程中穿过了边界,则不会计算在内。
原题链接
100214. 边界上的蚂蚁
思路分析
直接模拟即可
代码详解
class Solution { public: int returnToBoundaryCount(vector& nums) { int s = 0, ret = 0, n = nums.size(); for(auto x : nums){ s += x; if(s == 0) ret++; } return ret; } };
100204. 将单词恢复初始状态所需的最短时间 I
题目描述
给你一个下标从 0 开始的字符串 word 和一个整数 k 。
在每一秒,你必须执行以下操作:
- 移除 word 的前 k 个字符。
- 在 word 的末尾添加 k 个任意字符。
注意 添加的字符不必和移除的字符相同。但是,必须在每一秒钟都执行 两种 操作。
返回将 word 恢复到其 初始 状态所需的 最短 时间(该时间必须大于零)。
原题链接
100204. 将单词恢复初始状态所需的最短时间 I
思路分析
设字符串长度为n,求kmp的next数组,这样能够知道字符串的最长公共前后缀长度next[n]
如果(n - next[n]) % k == 0,那么直接返回(n - next[n]) / k
否则继续找更短的公共前后缀
如果都不满足(n - next[i]) % k == 0,那就返回(n + k - 1) / k
代码详解
class Solution { public: int next[55]; int minimumTimeToInitialState(string s, int k) { s.push_back('#'); int n = s.size(); functiongetnext = [&]() { int j = 0, k = -1; next[0] = -1; while (j < n - 1) if (k == -1 || s[j] == s[k]) next[++j] = ++k; else k = next[k]; }; getnext(), n--; if ((n - next[n]) % k == 0) { return (n - next[n]) / k; } else { int i = next[n]; while(~i && ((n - next[i]) % k)) i = next[i]; if(i != -1) return (n - next[i]) / k; } return (n + k - 1) / k; } };
100189. 找出网格的区域平均强度
题目描述
给你一个下标从 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 。
原题链接
100189. 找出网格的区域平均强度
思路分析
数据量很小,直接暴力即可
代码详解
class Solution { public: vector> resultGrid(vector > &image, int threshold) { int n = image.size(), m = image[0].size(); short dir[5]{1, 0, -1, 0, 1}; auto check = [&](int x, int y) { for (int i = x; i <= x + 2; i++) for (int j = y; j <= y + 2; j++) for (int k = 0; k < 4; k++) { int ii = i + dir[k], jj = j + dir[k + 1]; if (ii < x || ii > x + 2 || jj < y || jj > y + 2) continue; if (abs(image[i][j] - image[ii][jj]) > threshold) return false; } return true; }; vector >> cnt(n, vector >(m, vector ())); for (int i = 0; i + 2 < n; i++) for (int j = 0; j + 2 < m; j++) if (check(i, j)) { int s = 0; for (int ii = 0; ii < 3; ii++) for (int jj = 0; jj < 3; jj++) s += image[i + ii][j + jj]; for (int ii = 0; ii < 3; ii++) for (int jj = 0; jj < 3; jj++) cnt[i + ii][j + jj].push_back(s / 9); } vector > ans(n, vector (m)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (cnt[i][j].empty()) ans[i][j] = image[i][j]; else { int s = 0; for (int x : cnt[i][j]) s += x; ans[i][j] = s / cnt[i][j].size(); } } return ans; } };
100203. 将单词恢复初始状态所需的最短时间 II
题目描述
给你一个下标从 0 开始的字符串 word 和一个整数 k 。
在每一秒,你必须执行以下操作:
- 移除 word 的前 k 个字符。
- 在 word 的末尾添加 k 个任意字符。
注意 添加的字符不必和移除的字符相同。但是,必须在每一秒钟都执行 两种 操作。
返回将 word 恢复到其 初始 状态所需的 最短 时间(该时间必须大于零)。
原题链接
100203. 将单词恢复初始状态所需的最短时间 II
思路分析
和第二题一样,时间复杂度O(n)
代码详解
class Solution { public: int next[100005]; int minimumTimeToInitialState(string s, int k) { s.push_back('#'); int n = s.size(); functiongetnext = [&]() { int j = 0, k = -1; next[0] = -1; while (j < n - 1) if (k == -1 || s[j] == s[k]) next[++j] = ++k; else k = next[k]; }; getnext(), n--; if ((n - next[n]) % k == 0) { return (n - next[n]) / k; } else { int i = next[n]; while(~i && ((n - next[i]) % k)) i = next[i]; if(i != -1) return (n - next[i]) / k; } return (n + k - 1) / k; } };