CY-Left

LeetCode基本功底

[leetcode]696. Count Binary Substrings-统计二进制字符串

题目以及简单翻译

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.
给出一个字符串 s,计算由 ‘0’ 和 ‘1’ 组成的,连续且不为空的字符串,并且所有的 ‘0’ 和 ‘1’都是连续的。

Substrings that occur multiple times are counted the number of times they occur.
计算子串对称状况发生次数。
例子 1:

Input: "00110011"
Output: 6

分析: 六个 ‘0’ 和 ‘1’ 分别连续出现相同次数的子串:”0011″, “01”, “1100”, “10”, “0011”, 和 “01”.

注意,重复的子串也记作发生次数。

同时,”00110011″ ‘0’ 和 ‘1’ 出现次数相同,但是其中由 ‘0’ 和 ‘1’并未连续出现。

例子 2:

Input: "10101"
Output: 4

分析: 四个符合条件的子串: “10”, “01”, “10”, “01”

注意:

  • s.length 在 1 和 50,000 之间
  • s 只包含 “0” 或者 “1” 字符。

解题思路

占内存且不讨好的方法

字符串 s 存储的东西其实并不重要,我们只要知道每一个字符串片段中中 0 和 1 出现了几次,比如“0011”,我们可以理解为“22”,合法子串一共六个,”0011″, “01”.

class Solution {
public:
    int countBinarySubstrings(string s) {
        int size = s.size();
        int resoult[size] = {0};
        int j=0;
        int answer = 0;

        for (int i=0;i<size;) {
            if(s[i] == '1'){
                resoult[j] += 1;
                i++;
            }else if(s[i] == '0'){
                resoult[j] += 1;
                i++;
            }
            if(s[i-1]!=s[i]) j++;
        }

        for(int i=0;i<j-1;i++){
            answer += min(resoult[i],resoult[i+1]);
        }
        return answer;
    }
};

聪明的方法

两个值分别存储0和1的数量,0(或者1)存满(一个0(或者1)区间存储完毕)之后,开始存储1(或者0)同时结果增加,直到1也存满,此时轮换继续。

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

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=382



Have any Question or Comment?

发表评论

电子邮件地址不会被公开。 必填项已用*标注