696. 计数二进制子串 [easy]

https://leetcode-cn.com/problems/count-binary-substrings/

给定一个字符串 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到50,000之间。
s 只包含“0”或“1”字符。

通过次数32,040 | 提交次数52,262

Second Try [golang]

2020-08-10

参考题解，可以只是用统计列表，然后汇总即可。

写了个go版本练手，不太熟练，但能运行成功还是不错的～

func countBinarySubstrings(s string) int {
    counts := make([]int, len(s) / 2)  // 从1改为len(s) / 2,速度有翻倍
    idx := 0 
    n := len(s)
    for idx < n {
        char := s[idx] 
        c := 1
        idx++ 

        for (idx < n && s[idx] == char) {
            c++
            idx++
        }
        counts = append(counts, c) // 复制了吗。。
    }
    // fmt.Print(counts)
    rv := 0 
    for i:=1; i < len(counts); i++ {
        rv += min(counts[i - 1], counts[i])
    }
    return rv  
}

// 一个min都要自己写的吗。。。
func min(a, b int) int {
        if a < b {
            return a 
        } else {
            return b 
        }
    }   

执行用时：4 ms, 在所有 Go 提交中击败了98.04%的用户
内存消耗：7 MB, 在所有 Go 提交中击败了20.00%的用户

First Try

2020-08-10

又是直白的模拟法，写得很容易出bug

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        # count continuation 
        if not len(s):
            return 0 
        
        rv = 0 
        count = {0: 0, 1: 0}

        swift = 0 
        for i, c in enumerate(s):
            c = int(c)
            if i == 0:
                char = c 
                count[c] += 1
                continue            
            if c == char:
                count[c] += 1
            else:
                if swift == 0:
                    char ^= 1
                    swift += 1
                    count[c] += 1
                else:
                    # print(i, rv, count, char)
                    rv += min(count.values())
                    count[c] = 0 # 上一个c失效，剩下旧的char,还有下一轮新的c
                    swift = 1 # 又是一个bug, 第一次之后swift就一直是从1开始轮
                    char ^= 1
                    count[c] += 1
        # print(rv, count)
        rv = rv + min(count.values())
        return rv

执行用时：372 ms, 在所有 Python3 提交中击败了8.72%的用户
内存消耗：14.1 MB, 在所有 Python3 提交中击败了63.74%的用户

696. 计数二进制子串 [easy]​

Second Try [golang]​

First Try​

696. 计数二进制子串 [easy]

Second Try [golang]

First Try