房产中介网站建设管理,品牌运营策划,长沙中企动力,金华专业的网站建设23-11-08每日一题#xff1a;2609.最长平衡子字符串 链接#xff1a;2609.最长平衡子字符串 总体思路#xff1a; 平衡字符串要求“字符串前半段的0和后半段的1个数相同” 分别记录0和1的计数结果#xff0c;并最终取二者的最小值2字符串必须0开头#xff0c;1结束 …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可能是大字符串最后一个字符所以得并上“i1s.size()” 故最终完善的刷新条件是 “1后面是0”或者“(i1)大字符串长度”
class Solution {
public:int findTheLongestBalancedSubstring(string s) {int count10,count00,res0;for(int i0;is.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[i1]0||(i1)s.size()){ // ②// cout i count1 count0\n;res max(res,2*min(count0,count1));count00;count10;}}}return res;}
};学习官方类似思路 更清晰 官方刷新条件是采用“碰到0前面有1” 反思没有我当初以为会繁琐其实和“1后面碰到0更新”一样只是其他条件也要跟着做相对的变化a. 将上方中的“(i1)大字符串长度”考虑作“i为0”即可b. 将s[i] 1作为if最初层的条件就好 ① ns.size()把将s.size()提前提出会快一点不然for循环里每次都得算一遍就慢② 每碰到“1”就更新一下res这样即使“1”在大字符串末尾也不担心会因为没满足“碰到0前面有1” 这个刷新条件而错过刷新了③ 切换子字符串 – 单独拎出刷新count0和count1的情况走到这步的前提是s[i]0所以else if(i0 || s[i-1]1) 表明的是 a. 要么s[i]0 i00’作为大字符串开头b. 要么s[i]0 s[i-1]10’作为新子字符串开头 比较自己和官方的思路 我是在切换子字符即刷新count0和count1时一起更新结果 需要多考虑1在末尾的情况而且期间有把自己绕晕的倾向官方思路是每次有1时更新结果 无需考虑1在末尾的情况但切换子字符串的逻辑要单独拎出来
class Solution {
public:int findTheLongestBalancedSubstring(string s) {int count00,count10,res0,ns.size()//①for(int i0;in;i){if(s[i]1){count1;res max(res,2*min(count0,count1));//②}else if(i0 || s[i-1]1) //③走到这步隐含说明s[i]0{ count0 1;count1 0;}else{//碰到0就计数1count0;}}return res;}
};
