写在前面：好久没写博客了，今天正好是周末Leetcode周赛，补充一个笔记吧。期末考试还剩一周了，暂时得放几天代码鸽子，不然期末就要GG了
更好的阅读体验： 戳我跳转
5483. 整理字符串
给你一个由大小写英文字母组成的字符串 s 。
一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：
0 <= i <= s.length - 2
s[i] 是小写字符，但 s[i + 1] 是相同的大写字符；反之亦然 。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。
请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。
注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。
分析：
模拟题，每次将删除的字符标记一下，注意在循环里最好不要用string的erase函数，会发生一些未定义行为，为了方便相邻字符的比较，可以用一个变量记录上一个有效字符的位置，当某次循环没有发生删除字符时，说明已经整理完毕。
代码：
class Solution {
public:
string makeGood(string s) {
int n = s.size();
while(true){
bool flag = 0;
int j = -1; //当前字符的上一个有效字符
for(int i = 0; i<n; i++){
if(s[i] == '@') continue;
if(j==-1) j = i;
else{
char a = s[i], b = s[j]; //判断a和b是否满足条件
if(a-32 == b || a+32 == b){
flag = 1; //本次遍历有效
s[i] = s[j] = '@';
j = -1;
}else j = i;
}
}
if(!flag) break; //本次循环没有删除字符，说明字符串已经整理完毕
}
string ans = "";
for(int i = 0; i<n; i++) if(s[i]!='@') ans += s[i];
return ans;
}
};
5484. 找出第 N 个二进制字符串中的第 K 位
给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：
S1 = "0"-
当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))
其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）
例如，符合上述描述的序列的前 4 个字符串依次是：
S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。
分析：
模拟题，按照题意计算出每个字符串即可。
代码：
class Solution {
public:
char findKthBit(int n, int k) {
vector<string> s(30,"");
s[1] = "0";
s[2] = "011";
s[3] = "0111001";
s[4] = "011100110110001";
for(int i = 5; i<=n; i++){
string t = invert(s[i-1]);
reverse(t.begin(),t.end());
s[i] = s[i-1] + '1';
s[i] += t;
}
return s[n][k-1];
}
string invert(string x){
int n = x.size();
string res = "";
for(int i = 0; i<n; i++){
if(x[i] == '0') res += '1';
else res += '0';
}
return res;
}
};
5471. 和为目标值的最大数目不重叠非空子数组数目
给你一个数组nums 和一个整数 target 。
请你返回非空不重叠子数组的最大数目，且每个子数组中数字和都为 target 。
分析：
动态规划。
-
dp[i]表示前i个数字中和为目标值的最大数目不重叠非空子数组数目。 - 对于
s[i]来说, 只需在1~i-1中找到满足s[i] - s[j] == target的j, 然后比较dp[i-1]和dp[h[s[j]]] + 1的大小，就可以转移到dp[i]
-dp[i-1]表示当前s[i]从前面的数字中没有找到j,只能从前一个数字转移
-dp[h[s[j]]] + 1表示从h[s[j]]转移过来
代码：
class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
int n = nums.size();
vector<int> s(n+100, 0);
unordered_map<int,int> h; //<前缀和,下标>
h.clear();
//处理前缀和
for(int i = 1; i<=n; i++){
s[i] = s[i-1] + nums[i-1];
}
h[0] = 0;
vector<int> dp(n+10,0);
//dp[i] 表示前i个数字中和为目标值的最大数目不重叠非空子数组数目
//对于s[i]来说, 只需在1~i-1中找到s[i] - s[j] == target, 然后比较dp[i-1] 和 dp[h[s[j]]] + 1的大小，就可以转移到dp[i]
//这里：dp[i-1]表示当前s[i]从前面的数字中没有找到j,只能从前一个数字转移
//dp[h[s[j]]] + 1 表示从h[s[j]] 转移过来
for(int i = 1; i<=n; i++){
dp[i] = dp[i-1];
if(h.count(s[i]-target)){
dp[i] = max(dp[i],dp[h[s[i]-target]]+1);
}
h[s[i]] = i; //当前前缀和更新到map中
}
return dp[n];
}
};
5486. 切棍子的最小成本
有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
给你一个整数数组 cuts ，其中 cuts[i]表示你需要将棍子切开的位置。
你可以按顺序完成切割，也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本。
分析：
因为木棍肯定是要切完的，只是切割的顺序不同，代价不同，我们可以先把所有的木棍切成长短不一的木条，然后以相同的代价合并两个木条，那么这题就转换成了合并石子问题，也就是区间DP问题。
f[l][r]表示合并l和r两堆石子的最小代价
那么我们可以根据在[l,r]中的点k为最后一次合并的点来分类：
f[l][r] = min(f[l][r], f[l][k]+ f[k+1][r]+s[r]-s[l-1]) s[r]-s[l-1]为代价 循环k，只要找到最小值即可。
代码：
class Solution {
public:
int minCost(int n, vector<int>& cuts) {
sort(cuts.begin(),cuts.end());
int m = cuts.size();
vector<int> a(m+10,0);
int last = 0;
for(int i = 0; i<cuts.size(); i++){
a[i] = (cuts[i]-last);
last = cuts[i];
}
a[m] = n-cuts[m-1];
vector<vector<int>> f(120,vector<int>(120,0));
vector<int> s(120,0);
m++;
for(int i = 1; i<=m; i++) s[i] = a[i-1] + s[i-1];
for(int len = 2; len<=m; len++)
for(int i = 1; i+len-1<=m; i++)
{
int l = i, r = l+len-1;
f[l][r] = 1e9;
for(int k = l; k<r; k++){
f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
}
}
return f[1][m];
}
};
