LeetCode --- 420周赛
题目列表
3324. 出现在屏幕上的字符串序列
3325. 字符至少出现 K 次的子字符串 I
3326. 使数组非递减的最少除法操作次数
3327. 判断 DFS 字符串是否是回文串
一、出现在屏幕上的字符串序列
根据题目意思进行模拟即可，代码如下
class Solution {
public:
vector<string> stringSequence(string target) {
vector<string> ans;
int n = target.size();
string tmp;
for(int i = 0; i < n; i++){
tmp += 'a';
ans.push_back(tmp);
while(target[i]!=tmp[i]){
tmp[i] = (tmp[i] - 'a' + 1)%26 + 'a';
ans.push_back(tmp);
}
}
return ans;
}
};二、字符至少出现 K 次的子字符串I
题目要求我们统计符合条件的子字符串的个数，类似这种维护区间某种性质的题，都可以考虑用滑动窗口来做，这题也是同理。滑动窗口维护的区间是以 R 为右端点，且没有一个字母出现 >= k 次的最长子字符串。那么以 R 为右端点的符合题目要求的子字符串的个数就为 L 个，将结果相加，就能得到答案，代码如下
class Solution {
public:
int numberOfSubstrings(string s, int k) {
int n = s.size(), ans = 0;
int cnt[26]{};
for(int l = 0, r = 0; r < n; r++){
++cnt[s[r] - 'a'];
// [l, r] 内不存在字符的个数 >= k
while(cnt[s[r] - 'a'] == k){
--cnt[s[l] - 'a'];
l++;
}
ans += l; // 左端点在[0, l)内的都满足题目要求
}
return ans;
}
};三、使数组非递减的最少出发操作次数
根据题目所给的描述，我们能得到以下几点：
1、要求最少操作次数，根据贪心的思想，我们肯定是让后面的数字尽可能大，而我们只能让数变小，所以最后一个数不用进行操作，同时从后向前遍历数组，让遍历到的数字都保持尽量大。
2、对于任意一个数，我们最多只能执行一次操作，为什么？假设有一个数字为 x，x 的最大真因子为a，b = a/x，如果 b 还能被分解为 c * d，那么 x 的最大真因子应该是 a * c 或者 a * d，所以每个数最多只能被操作一次，且操作完的数为质数，因为无法被再次分解。
根据上述两点，我们只要提前预处理得到任意一个数能被分解为哪个质数，就能在O(1)的时间内完成对任意一个数的操作，然后倒序遍历数组就能得到答案，代码如下
const int MX = 1e6 + 1;
vector<int> f(MX);
int init = [](){
// 时间复杂度为O(UlogU) U = MX
for(int i = 2; i < MX; i++){
// 没有被赋值，说明当前的数字无法被比它小的数字组成，即它是个质数
if(f[i] == 0){
for(int j = 2 * i; j < MX; j += i){
if(f[j] == 0) // 表示之前没被赋值过，比如 51 = 3 * 17，既能被 3 赋值，又能被17 赋值，显然 f[51] = 3
f[j] = i;
}
}
}
return 0;
}();
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size(), ans = 0;
for(int i = n - 2; i >= 0; i--){
if(nums[i] <= nums[i+1]) continue;
if(f[nums[i]] == 0) return -1;
nums[i] = f[nums[i]];
if(nums[i] > nums[i+1]) return -1;
ans++;
}
return ans;
}
};四、判断DFS字符串是否是回文字符串
题意概括如下：对每一个结点进行后序遍历得到一个字符串，并判断得到的字符串是否是回文串。这里首先要明确一点，任意结点经过后续遍历得到的字符串，都是根节点进行后序遍历得到的字符串的子串(由递归的性质决定)，也就是说我们只要对根节点进行遍历得到字符串s，同时记录每个结点的字符串的区间，那么问题就变成了如何快速判断一个区间是否是回文串。
如何快速判断一个区间是否是回文串呢？这里就要介绍 Manacher 算法，用O(n)的时间进行预处理，然后用O(1)的时间判断子串是否是回文串。
代码实现如下
class Solution {
public:
vector<bool> findAnswer(vector<int>& parent, string s) {
int n = parent.size();
vector<vector<int>> g(n);
for(int i = 1; i < n; i++)
g[parent[i]].push_back(i);
string t;
// [L[i], R[i]] 表示以i为根节点进行dfs，得到的子串区间
vector<int> R(n), L(n);
auto dfs = [&](auto && dfs, int x)->void{
L[x] = t.size();
for(int y:g[x])
dfs(dfs, y);
R[x] = t.size();
t += s[x];
};
dfs(dfs, 0);
// 为了简化代码逻辑，不分回文串的奇偶讨论，我们在 t 的字符之间都添加一个 #
// 同时为了不对边界情况进行特判，我们在 t 前后加上两个不同的特殊字符
// 如 acbaddb => ^#a#c#b#a#d#d#b#$
string tmp = "^";
for(auto e : t){
tmp += '#';
tmp += e;
}
tmp += "#$";
// Manacher 算法
int m = tmp.size();
vector<int> halfLen(m-2);
int box_mid = 0, box_R = 0;
for(int i = 2; i < m-2; i++){ // 我们并不关心以前两个字符或者最后两个字符为中点的回文串
int hl = 1;
// 算法的核心：根据已知条件，得到一些结论
if(i < box_R){
hl = min(halfLen[2 * box_mid - i], box_R - i);
}
while(tmp[i - hl] == tmp[i + hl]){
hl++;
box_mid = i, box_R = hl + i;
}
halfLen[i] = hl;
}
vector<bool> ans(n);
for(int i = 0; i < n; i++){
// 将 t 的区间 [L[i], R[i]] 映射到 tmp 的区间 [left, right]上
// 下标间的关系为 2*(i+1)
int left = 2 * (L[i] + 1), right = 2 * (R[i] + 1);
int mid = (left + right)/2;
ans[i] = (halfLen[mid] >= R[i] - L[i] + 1);
}
return ans;
}
};