总结
前三题比较基础，第三题是一个前缀和，因为之前见过所以很快就过了。最后一题弃疗了，看上去像一个DP优化问题，但是确实实力限制没有想出来，准备听一下讲解。
Q1：100339. 找出加密后的字符串
题目传送门：找出加密后的字符串 - 力扣（LeetCode）
签到题
最后实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
string getEncryptedString(string s, int k) {
int n = s.size();
string ans = s;
for(int i=0;i<n;++i){
ans[i] = s[(i+k)%n];
}
return ans;
}
};
|
Q2：100328. 生成不含相邻零的二进制字符串
题目传送门：生成不含相邻零的二进制字符串 - 力扣（LeetCode）
本来以为是一道DP（但应该也可以吧），一看数据范围果断暴搜。
最后实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<string> validStrings(int n) {
vector<string> ans;
function<void(int,int,string)> dfs = [&](int now,int last,string tmp){
if(now==n) {ans.push_back(tmp);return;}
dfs(now+1,1,tmp+'1');
if(last==1) dfs(now+1,0,tmp+'0');
};
dfs(0,1,"");
return ans;
}
};
|
Q3：100359. 统计 X 和 Y 频数相等的子矩阵数量
题目传送门：统计 X 和 Y 频数相等的子矩阵数量 - 力扣（LeetCode）
前缀和题目
最后实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int numberOfSubmatrices(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dp(n+1,vector<int>(m+1, 0));
vector<vector<bool>> vis(n+1,vector<bool>(m+1, false));
int ans = 0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
int nw = grid[i-1][j-1]=='.'?0:(grid[i-1][j-1]=='X'?1:-1);
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + nw;
vis[i][j] = vis[i-1][j] | vis[i][j-1] | (nw!=0);
if (dp[i][j]==0&&vis[i][j]) ans++;
}
}
return ans;
}
};
|
Q4：100350. 最小代价构造字符串
题目传送门：最小代价构造字符串 - 力扣（LeetCode）
做不来呜呜呜😭
官方给出的解法是使用字典树，但是灵神把他Hack了。
字典树做法核心思想就是用字典树这个数据结构优化我们每次的字符串匹配问题
正解是使用字符串哈希
最后实现代码如下：