刷题日记4

2025.1.21

2904. 最短且字典序最小的美丽子字符串

2904. 最短且字典序最小的美丽子字符串 - 力扣（LeetCode）

class Solution {
public:string shortestBeautifulSubstring(string s, int k) {//遍历找到美丽子字符串，更新时候如果<res，输出字符串直接更改,//如果==res，和输出字符串进行比较，取小的那个//问题：如何比较字符串int l=0,r=0,sum=0,res=1e9+5;string str;while(r<s.size()){sum+=s[r]-'0';while(sum>k||s[l]=='0'){sum-=s[l]-'0';l++;}if(sum==k){int len=r-l+1;string st=s.substr(l,len);if(len<res||(len==res&&st<str)){res=len;str=st;}}r++;}return str;}
};

思考：1。思路是正确的，和灵神思路一样。值得肯定。

2。卡点一：计算累加sum的时候，需要s[r]-'0'。不能直接sum+=s[r]。

3。卡点二：字符串之间的比较。s1<s2。按照字典序进行比较。abc<abd。

4。卡点三：第二层while循环中，判断条件还要加上s[l]=='0'。

5.在逻辑运算中，&&优先级高于||

1234. 替换子串得到平衡字符串

1234. 替换子串得到平衡字符串 - 力扣（LeetCode）

class Solution {
public:int balancedString(string s) {//m=n/4，是每个字符应该出现的次数//滑动窗口，在窗口外，每种字符的次数必须满足<=m，该窗口才符合能替换的子串的条件//那么在二层循环中，满足子串条件才记录res，缩小范围int n=s.size(),m=n/4,cnt['X']{};for(char c:s)cnt[c]++;if(cnt['Q']==m&&cnt['W']==m&&cnt['E']==m&&cnt['R']==m) return 0;int l=0,r=0,res=1e9+5;while(r<n){cnt[s[r]]--;while(cnt['Q']<=m&&cnt['W']<=m&&cnt['E']<=m&&cnt['R']<=m){res=min(res,r-l+1);cnt[s[l]]++;l++;}r++;}return res;}
};

自己的错误版本：

class Solution {
public:int balancedString(string s) {//先统计字符长度n，//统计每个qwer的个数，统计更改为多余字母的个数//接着遍历，滑窗找到包含所有多余字母的最小字符串int n=s.size();vector<int>num(4,0);int r=0,res=1e9+5;while(r<n){if(s[r]=='Q')num[0]++;else if(s[r]=='W')num[1]++;else if(s[r]=='E')num[2]++;else num[3]++;r++;}for(int i=0;i<4;i++){if(num[i]>n/4) num[i]-=n/4;else num[i]==0;}int l=0;r=0;while(r<n){if(s[r]=='Q') num[0]--;else if(s[r]=='W')num[1]--;else if(s[r]=='E')num[2]--;else num[3]--;while(num[0]<0||num[1]<0||num[2]<0||num[3]<0){if(s[l]=='Q')num[0]++;else if(s[l]=='W')num[1]++;else if(s[l]=='E')num[2]++;else num[3]++;l++;}if(num[0]==0&&num[1]==0&&num[2]==0&&num[3]==0){res=min(res,r-l+1);}r++;}return res;}
};

思考：解题思路已经注释，这里写一下自己的收获。

1。对于存储q,w,e,r的对应的个数，用空间换时间，类似哈西表，用int cnt['X']。

2。需要添加上初始时各个字符都为m的情况，不然l会直接遍历到数组溢出。

2875. 无限数组的最短子数组

2875. 无限数组的最短子数组 - 力扣（LeetCode）

class Solution {
public:int minSizeSubarray(vector<int>& nums, int target) {//遍历nums，l,r一直增加，访问nums时duin取余//二层循环，大于target时，l右移，//二层循环外更新int n=nums.size();int l=0,r=0,res=1e9+5;long long total=0,sum=0;for(int i=0;i<n;i++)total+=nums[i];while(r<2*n){sum+=nums[r%n];while(sum>target%total){sum-=nums[l%n];l++;}if(sum==target%total) res=min(res,r-l+1);r++;}if(res==1e9+5)return -1;else return res+target/total*n;}
};

思考：1。思考上的一个错误：两个数组不一定能满足条件。nums.length*nums[i]最大值是大于target的，但是这是最大值。也就是说不知道需要多少个数组才能累加到target。

2。思路：当累加达到target时需要大于两个的数组时，至少中间的数组是全部计算的，那么就是说只需要研究两个数组就行，即total是数组之和，target/total是全部都计算上的数组个数，target%total是需要在两个数组上寻找的最短子数组的累加之和。