会展设计是干什么的_进入公众号平台_全网搜索关键词查询_谷歌搜索引擎在线

目录

牛客_小葱的01串_滑动窗口

题目解析

C++代码

Java代码

---

牛客_小葱的01串_滑动窗口

小葱的01串 (nowcoder.com)

描述：

        给定一个长度为偶数的环形 01 字符串。（环形指，第一个字符和最后一个字符是相邻的）

        字符串初始每个字符都是白色。小葱想把一段连续区间染成红色，使得红色的字符'0'数量等于白色的字符'0'数量，红色的字符'1'数量等于白色的字符'1'数量。问有多少种不同的染色方法？

两个方案不同当且仅当存在一个某字符，在一个方案是染成红色，在另一个方案为白色。

输入描述:

第一行输入一个正整数 n，代表字符串长度。
第二行输入一个长度为 n 的 01 字符串（仅由字符'0'和字符'1'组成的字符串）
数据范围：
2≤n≤300000 。保证 n 是偶数。

输出描述:

合法的染色方案数。

---

题目解析

长度固定的滑动窗口，因为要想符合要求，必定是一半一半的。

C++代码

#include <iostream>
using namespace std;int main()
{int n = 0, res = 0;string str;cin >> n >> str;int cnt0 = 0, cnt1 = 0;for(int i = 0; i < n; ++i){if(str[i] == '0')++cnt0;else++cnt1;}if(cnt0 % 2 != 0 || cnt1 % 2 != 0){cout << 0 << endl;return 0;}cnt0 /= 2, cnt1 /= 2;int left = 0, right = 0;int tmp0 = 0, tmp1 = 0;while(right < n - 1){if(str[right] == '0')++tmp0;else++tmp1;while(right - left + 1 > n / 2) // 下面注释的出窗口逻辑错了{if(str[left++] == '0')--tmp0;else--tmp1;}if(right - left + 1 == n / 2) // 注释掉也行，但有点怪{if(tmp0 == cnt0 && tmp1 == cnt1)res += 2;}++right;}/*while(right < n - 1){if(str[right] == '0')++tmp0;else++tmp1;while(left < n && right - left + 1 == n / 2 && tmp0 == cnt0 && tmp1 == cnt1){//cout << tmp0 << " " << tmp1 << endl;//cout << left << " " << right << endl;res += 2;if(str[left++] == '0')--tmp0;else--tmp1;}++right;}*/cout << res << endl;return 0;
}

Java代码

import java.util.*;public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);int n = in.nextInt();char[] s = in.next().toCharArray();int[] sum = new int[2]; // 统计字符串中所有 0 和 1 的个数for(int i = 0; i < n; i++){sum[s[i] - '0']++;}int left = 0, right = 0, ret = 0, half = n / 2;int[] count = new int[2]; // 统计窗⼝内 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++;}System.out.println(ret);}
}