696. Count Binary Substrings

這題雖然是簡單的, 但我一開始完全沒想法

看了討論後知道, 假設我們先從0開始, 一旦換成1後, 前面那組0就會先被固定, 這時只要1的數目增加, 前面那組的0的總數比1還大, 就一定構成條件

但當再次遇見0時, 前面的那組0就會被取代, 這時就被歸到1從新計算, 反之換這邊的0去看1的條件了

class Solution {
public:
int countBinarySubstrings(string s) {
        int zeros = 0;
        int ones = 0;
        int res = 0;
        for(int i = 0; i < s.size(); i++){
            if(i == 0){
                if(s[i] == '1')
                    ones++;
                else
                    zeros++;
             
            }else{
                if(s[i] == '1'){
                    ones = (s[i -1] == '1')?ones + 1:1;
                    if(zeros >= ones) res++;
                }else{
                    zeros = (s[i - 1] == '0')? zeros + 1:1;
                    if(ones >= zeros) res++;
                }
            }
        }
        return res;
    }
};

另外一種方式, 就是把0, 1的數量都先group起來, 接著我們在一次做清算

舉例 : 0110001111 可以分成[1, 2, 3, 4]

我們只要兩倆之間取較小值就可以了, 以3, 4為例min(3, 4) = 3 (“01”, “0011”, “000111”)

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

有人寫得更漂, 練習一下

class Solution {
public:
int countBinarySubstrings(string s) {
        int cur = 1 ; 
        int pre = 0;
        int res = 0;
        for(int i = 1;i < s.size();i++){
            if(s[i] == s[i -1])cur++;
            else{
                res += min(cur, pre);
                pre = cur;
                cur = 1;
            }
        }
        return res + min(cur, pre);
    }
};