LeetCode刷题--思路总结记录

23-11-08每日一题：2609.最长平衡子字符串

• 链接：2609.最长平衡子字符串

• 总体思路：

  • 平衡字符串要求“字符串前半段的0和后半段的1个数相同” ==> 分别记录0和1的计数结果，并最终取二者的最小值×2
  • 字符串必须0开头，1结束 ==> 忽略s一开头的1
  • 一个字符串记录后，怎么从上个字符串结尾的1，切换到下个字符串开头的0？

• 按普通样例“0100111”走==> 碰到’0’就给count0++，碰到‘1’就给count1++ ==> 当碰到0前面有1，就刷新一次res，并重计算count0和count1

  • ① 由于可能字符串1开头，得忽略 ==> 故“ 碰到‘1’就给count1++”就得修改成，碰到‘1’且count0≠0时
  • ② 若刷新的条件是以“碰到0前面有1”的角度，那么对于“01000111”最大的平衡字符串中“000111”之后没有0作结尾，就没法更新结果了（即只有当“0001110”时才能更新出正确答案），或者更新结果得比较繁琐 ==> 于是思考刷新的条件应修改为“1后面是0” ==> 同时由于1可能是大字符串最后一个字符，所以得并上“i+1==s.size()” ==> 故最终完善的刷新条件是 “1后面是0”或者“(i+1)=大字符串长度”

class Solution {
public:int findTheLongestBalancedSubstring(string s) {int count1=0,count0=0,res=0;for(int i=0;i<s.size();i++){if(s[i]=='0') {count0++;// cout<<' '<<i<<' '<<count1<<' '<<count0<<'\n';}else if( (count0!=0) & s[i]=='1' ){ // ①count1++;// cout<<' '<<i<<' '<<count1<<' '<<count0<<'\n';if(s[i+1]=='0'||(i+1)==s.size()){ // ②// cout<<' '<<i<<' '<<count1<<' '<<count0<<'\n';res = max(res,2*min(count0,count1));count0=0;count1=0;}}}return res;}
};

• 学习官方类似思路 ==> 更清晰
  • 官方刷新条件是采用“碰到0前面有1”
    • 反思：没有我当初以为会繁琐，其实和“1后面碰到0更新”一样，只是其他条件也要跟着做相对的变化
    • a. 将上方中的“(i+1)=大字符串长度”，考虑作“i为0”即可；
    • b. 将s[i] == '1'作为if最初层的条件就好
  • ① n=s.size()：把将s.size()提前提出，会快一点，不然for循环里每次都得算一遍，就慢
  • ② 每碰到“1”就更新一下res，这样即使“1”在大字符串末尾，也不担心会因为没满足“碰到0前面有1” 这个刷新条件，而错过刷新了
  • ③ 切换子字符串 – 单独拎出刷新count0和count1的情况：走到这步的前提是s[i]='0'，所以else if(i==0 || s[i-1]=='1') 表明的是
    • a. 要么s[i]='0' & i==0：'0’作为大字符串开头
    • b. 要么s[i]='0' & s[i-1]=='1'：'0’作为新子字符串开头
  • 比较自己和官方的思路：
    • 我是在切换子字符（即刷新count0和count1）时，一起更新结果 ==> 需要多考虑1在末尾的情况，而且期间有把自己绕晕的倾向
    • 官方思路是每次有1时，更新结果 ==> 无需考虑1在末尾的情况，但切换子字符串的逻辑要单独拎出来

class Solution {
public:int findTheLongestBalancedSubstring(string s) {int count0=0,count1=0,res=0,n=s.size()//①for(int i=0;i<n;i++){if(s[i]=='1'){count1++;res = max(res,2*min(count0,count1));//②}else if(i==0 || s[i-1]=='1') //③走到这步隐含说明s[i]='0'{   count0 = 1;count1 = 0;}else{//碰到0就计数+1count0++;}}return res;}
};