一、分析题目
二、代码
1、看了题解之后AC的代码
#include <iostream> using namespace std; int main() { int n; cin >> n; string s; cin >> s; int zero=0, one=0; for(auto ch : s) { if(ch=='0') zero++; if(ch=='1') one++; } int res=0; int half=n/2; int zero_cnt=0, one_cnt=0; int left=0, right=0; while(right<n-1) //细节：防止重复计数 { if(s[right]=='0') zero_cnt++; if(s[right]=='1') one_cnt++; while(right-left+1>half) { if(s[left]=='0') zero_cnt--; if(s[left]=='1') one_cnt--; left++; } if(right-left+1==half) { if(zero_cnt*2==zero && one_cnt*2==one) res+=2; } right++; } cout << res << endl; return 0; }
2、值得学习的代码
#include <iostream> #include <string> using namespace std; int n; string s; int main() { cin >> n >> s; int sum[2] = { 0 }; // 统计字符串中所有 0 和 1 的个数 for(auto ch : s) { sum[ch - '0']++; } int left = 0, right = 0, ret = 0, half = n / 2; int count[2] = { 0 }; // 统计窗⼝内 0 和 1 的个数 while(right < n - 1) // 细节问题 { count[s[right] - '0']++; while(right - left + 1 > half) { count[s[left++] - '0']--; } if(right - left + 1 == half) { if(count[0] * 2 == sum[0] && count[1] * 2 == sum[1]) { ret += 2; } } right++; } cout << ret << endl; return 0; }
三、反思与改进
这道题我一开始的做法是暴力解法，就是先统计字符串里面 0 和 1 的个数，因为题目明确说明了字符串的长度是偶数，所以再记录一下 0 和 1 数量的一半（这个是这道题的解题关键）。因为受到 “环形” 这一限制，我后面就想到了得用滑动窗口来解这道题，但是却忽略了一些细节，只过了 50% 的测试用例。在计算满足条件的连续区间数量时，没有考虑正确环形字符串的特性，所以即使我在字符串的末尾添加了一段和起始位置相同的字符串，但是我的循环仍然只考虑了从起始位置开始的子串，这就可能会导致遗漏一些解。
上面给出的代码不需要在字符串末尾添加字符，而是利用了字符串长度为偶数这一特性，一次+2，因为其中一半符合条件，那么剩下的一般一定也符合条件。
