LeetCode笔记：696. Count Binary Substrings

问题（Easy）：

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's. Note:

• s.length will be between 1 and 50,000.
• s will only consist of "0" or "1" characters.

大意：

给出一个字符串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。 注意：

• s.length会在1到50000之间。
• s只会由0和1字符组成。

思路：

通过一快一慢两个指针去遍历字符串，找到其中连续的0或者1，用一个flag来标记当前是连续的某个数字还是开始遇到另一种数字了。如果找到一样数目的了，就将结果数量加一。

有一个窍门是，当找到一个子串后，比如：“000111”，这是不要只把结果加一，而要加3，因为实际上它还包含了“0011”和“01”这两个符合要求的子串，所以有几个连续的数就加几，然后把慢的那个指针直接指到第一个不同的数字处，就不用一步步往前走这么慢以及重复计算了。

但是这种方案并没有通过，原因是在超长的字符串上运行超时了。

代码（C++）：

class Solution {
public:
    int countBinarySubstrings(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            int j = i+1;
            bool flag = true;
            int turenum = 1;
            int falsenum = 0;
            while (j < s.size()) {
                if (s[j] == s[i]) {
                    if (flag) turenum++;
                    if (!flag) break;
                } else if (s[j] != s[i]) {
                    if (flag) {
                        flag = false;
                        falsenum = 1;
                    } else {
                        falsenum++;
                    }
                    if (falsenum == turenum) {
                        res = res + turenum;
                        i = j - turenum;
                        break;
                    }
                }
                j++;
            }
        }
        return res;
    }
};

他山之石：

看了一个被人的方法，上面的窍门也利用到了，但是他并不是边遍历边计数，而是先遍历一遍字符串，记录每次重复的0和1的数量，比如："00110011"，遍历后记录为：“2222”。“00011”遍历后记录为：“32”。

然后再对这个新的记录，遍历，并取两个相邻数中较小的那一个，这实际上就是看每次响铃的0串和1串中会有的附和要求的子串数量了，速度快多了。

class Solution {
public:
    int countBinarySubstrings(string s) {
        vector<int> rec;
        int count = 1;
        for(int i=1, n=s.size(); i<=n; ++i){
            if(s[i] == s[i-1]){
                ++count;
            }else{
                rec.push_back(count);
                count = 1;
            }
        }
        int res = 0;
        for(int i=1, n=rec.size(); i<n; ++i){
            res += min(rec[i-1], rec[i]);
        }
        return res;
    }
};

合集：https://github.com/Cloudox/LeetCode-Record