leetcode 696. Count Binary Substrings 连续出现相同次数0或1子串数量 + 很棒的做法

灰太狼 2022-06-03 08:39 193阅读 0赞

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.

以发现我们只要分别统计0和1的个数，而且如果当前遇到的是1，那么只要之前统计的0的个数大于当前1的个数，就一定有一个对应的子字符串，而一旦前一个数字和当前的数字不一样的时候，那么当前数字的计数要重置为1。所以我们遍历元数组，如果是第一个数字，那么对应的ones或zeros自增1。然后进行分情况讨论，如果当前数字是1，然后判断如果前面的数字也是1，则ones自增1，否则ones重置为1。如果此时zeros大于ones，res自增1。反之同理，如果当前数字是0，然后判断如果前面的数字也是0，则zeros自增1，否则zeros重置为1。如果此时ones大于zeros，res自增1。

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int countBinarySubstrings(string s) 
        {
            int res = 0, count0 = 0, count1 = 0;
            for (int i = 0; i < s.length(); i++)
            {
                if (i == 0)
                    (s[i] == '1') ? count1++ : count0++;
                else
                {
                    if (s[i] == '1')
                    {
                        count1 = s[i - 1] == s[i] ? count1 + 1 : 1;
                        if (count0 >= count1)
                            res++;
                    }else
                    {
                        count0 = s[i - 1] == s[i] ? count0 + 1 : 1;
                        if (count1 >= count0)
                            res++;
                    }
                }
            }
            return res;
        }
    };