[数据结构与算法]力扣 696. 计数二进制子串

题目

给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。

重复出现的子串要计算它们出现的次数

示例 1

输入: “00110011”
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-binary-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

实现

方法1：

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n,sum,res = len(s),0,list()
        var=0
        s=list(s)
        for i in range(n-1):
            if s[i] == s[i + 1]:
                var += 1
            else:
                var += 1
                res.append(var)
                var = 0
        if var !=0:
            res.append(var)
        if s[n-1]==s[n-2]  and len(res) !=0:
            res[-1]+=1
        else:
            res.append(1)
        for i in range(len(res)-1):
            sum+=min(res[i],res[i+1])
        return sum