| 整理字符串 | 找出第N个二进制字符串中的第K位 | 和为目标值的最大数目不重叠非空子数组数目 | 切棍子的最小成本 |
|---|---|---|---|
| 3分 简单 | 4分 中等 | 6分 中等 | 7分 困难 |
| √ | √ | √ | √ |
5483 统计好三元组
用栈维护，类似于合法括号的抵消
枚举字符串s，与栈顶元素比较，符合条件的就弹出栈顶
否则加入栈顶
复杂度
O(n)
执行用时
4ms
内存消耗
6.5MB
class Solution {
public:string makeGood(string s) {stack<char>st;for(int i=0;i<s.length();i++){if(st.empty()) st.push(s[i]);else{char x1=st.top();char x2=s[i];int f1=(x1>='a'&&x1<='z')?(x1-'a'):(x1-'A');int f2=(x2>='a'&&x2<='z')?(x2-'a'):(x2-'A');if(x1!=x2&&f1==f2){st.pop();}else st.push(x2);}}string ans="";while(!st.empty()){ans+=st.top();st.pop();}reverse(ans.begin(),ans.end());return ans;}
};
5484 找出第N个二进制字符串中的第K位
按题意模拟出第n个字符串 s 即可
执行用时
292 ms
内存消耗
74.8 MB
复杂度
class Solution {
public:char findKthBit(int n, int k) {string s="0";for(int i=2;i<=n;i++){string tmp=s;for(auto& it:tmp){if(it=='1') it='0';else it='1';}reverse(tmp.begin(),tmp.end());s=s+"1"+tmp;}return s[k-1];}
};
5485 和为目标值的最大数目不重叠非空子数组数目
贪心的想，从最左边开始，一旦找到一个和为目标值的非空子数组，就选择这一组非空子数组
用前缀和的思想找和为target的子数组，mp[i]记录前缀和为i的最右位置, l 表示可选元素的最左边界，若当前位置为i,以i为右端点且和为target的子数组存在，那么选择这个子数组，l=i+1,我们不能在选择 l 之前的元素了
num是当前的前缀和，若num-target在mp中存在，说明，mp[num-target]+1~i 这一段是和为target的子数组
另外，还要满足mp[num-target]+1>=lif(mp.find(num-target)!=mp.end()){if(mp[num-target]+1>=l){l=i+1;ans++;} }
复杂度
O(nlogn)
执行用时
824 ms
内存消耗
86.7MB
class Solution {
public:int maxNonOverlapping(vector<int>& nums, int target) {int l=0;int n=nums.size();int num=0;map<int,int>mp;mp[0]=-1;int ans=0;for(int i=0;i<n;i++){num+=nums[i];if(mp.find(num-target)!=mp.end()){if(mp[num-target]+1>=l){l=i+1;ans++;} }mp[num]=i;}return ans;}
};
5486 切棍子的最小成本
这道题使把棍子从1份，切到m份
而动态规划中的石子归并是最开始m堆，合并成1堆的最小花费，所以我们只要转换一下，这道题就是石子归并的模板题。
转化过程:
先从小到大sort一遍，然后与前一个元素做差就是新的石子的大小，注意特判下第一个和最后一个石子
sort(cuts.begin(),cuts.end());
int m=cuts.size()+1;
for(int i=1;i<=m;i++) {if(i==1) a[i]=cuts[0];else if(i==m) a[i]=n-cuts[i-2];else a[i]=cuts[i-1]-cuts[i-2];sum[i]=sum[i-1]+a[i];
}
动态规划转移方程
dp[i][j] 表示合并第i堆到第j堆的最小花费
第一维:从小到大枚举合并的长度len
第二维: i 为区间左端点，j为区间右端点
第三维: 该区间原本是两份石子，现在要合并到一份石子，枚举左边一份石子的右端点s
dp[i][j]=min(dp[i][j],dp[i][s]+dp[s+1][j]+sum[j]-sum[i-1]);
for(int len=1;len<m;len++) { for (int i=1,j=len+1;j<=m;i++,j++){ dp[i][j] = INF;for(int s=i;s<j;s++) {dp[i][j]=min(dp[i][j],dp[i][s]+dp[s+1][j]+sum[j]-sum[i-1]);}}}
复杂度
O(N^3)
执行用时
116 ms
内存消耗
22.1 MB
class Solution {
public:int minCost(int n, vector<int>& cuts) {sort(cuts.begin(),cuts.end());int m=cuts.size()+1;vector<int>a(150,0);vector<int>sum(150,0);vector<vector<int>>dp(150,vector<int>(150,0));int INF=0x3f3f3f3f;for(int i=1;i<=m;i++) {if(i==1) a[i]=cuts[0];else if(i==m) a[i]=n-cuts[i-2];else a[i]=cuts[i-1]-cuts[i-2];sum[i]=sum[i-1]+a[i];}for(int len=1;len<m;len++) { for (int i=1,j=len+1;j<=m;i++,j++){ dp[i][j] = INF;for(int s=i;s<j;s++) {dp[i][j]=min(dp[i][j],dp[i][s]+dp[s+1][j]+sum[j]-sum[i-1]);}}}return dp[1][m];}
};