leetcode.字符串.696计数二进制子串-java

1. 具体题目

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。重复出现的子串要计算它们出现的次数。

示例 1 :　　输入: "00110011"　　输出: 6　　解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

示例 2 :　　输入: "10101"　　输出: 4　　解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

2. 思路分析

看到题目，首先想到了leetcode20.有效的括号，将 '0' 和 1' 等效于括号，设置一个计数器。但是要遍历字符串2次，第一次遇到 '0' 计数器 + 1，遇到 '1' 计数器 - 1；第二次遇到 '1' 计数器 + 1，遇到 '0' 计数器 - 1。

3. 代码

 1 public int countBinarySubstrings(String s) {
 2         int count = 0;
 3         int res = 0;
 4         for(int i = 0; i < s.length(); i++){
 5             if(s.charAt(i) == '0') count++;
 6             if(s.charAt(i) == '1'){　　
 7                 if(count > 0){　　//若有可配对的"0"，结果 + 1
 8                     res++;
 9                     count--;
10                 }
11                 if(i + 1 < s.length() && s.charAt(i + 1) == '0'){　　//若无可配对的"1"，计数器置0
12                     count = 0;
13                 }
14             }
15         }
16         count = 0;
17         for(int i = 0; i < s.length(); i++){
18             if(s.charAt(i) == '1') count++;
19             if(s.charAt(i) == '0'){
20                 if(count > 0){
21                     res++;
22                     count--;
23                 }
24                 if(i + 1 < s.length() && s.charAt(i + 1) == '1'){
25                     count = 0;
26                 }
27             }
28         }
29         return res;
30     }

4. 思路优化

实际上，字符串中若有 n 个 "0" 和 (n + m) 个 "1" 相邻，则说明可以产生 n 个重复字符串，所以只要统计数组中各连续子串中元素的数量即可，比如s=“11000111000000”，则可以得到一个统计数组groups = [2，3，4，6]，对该数组做遍历，每次得到 min(groups[i], groups[i+1])的值，将其全部相加可得最后结果。

5. 代码优化

 1 public int countBinarySubstrings(String s) {
 2         int[] groups = new int[s.length()];
 3         int t = 0;
 4         groups[0] = 1;
 5         for (int i = 1; i < s.length(); i++) {
 6             if (s.charAt(i-1) != s.charAt(i)) {
 7                 groups[++t] = 1;
 8             } else {
 9                 groups[t]++;
10             }
11         }
12
13         int ans = 0;
14         for (int i = 1; i <= t; i++) {
15             ans += Math.min(groups[i-1], groups[i]);
16         }
17         return ans;
18     }