leetcode 696. 计数二进制子串(python)

刺骨的言语ヽ痛彻心扉 2022-05-14 16:25 157阅读 0赞

给定一个字符串 `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”字符。

class Solution(object):
        def countBinarySubstrings(self, s):
            """
            :type s: str
            :rtype: int
            """
            #利用map函数求出被切分开的0和1组合长度
            L = list(map(len, s.replace('01', '0 1').replace('10', '1 0').split(' ')))
            #因为限定了只能0和1挨着，所以只能相邻的才可能组队，用了zip函数
            res = sum(min(a,b) for a,b in zip(L, L[1:]) )
            return res

知识点一：map()函数

**map()是 Python 内置的高阶函数，它接收一个函数 f 和一个 list，并通过把函数 f 依次作用在 list 的每个元素上，得到一个新的 list 并返回。**

**知识点二：zip函数**

zip函数的原型为：**zip(\[iterable, …\])**

参数iterable为可迭代的对象，并且可以有多个参数。该函数返回一个以元组为元素的列表，其中第 i 个元组包含每个参数序列的第 i 个元素。返回的列表长度被截断为最短的参数序列的长度。只有一个序列参数时，它返回一个1元组的列表。没有参数时，它返回一个空的列表。

方法二：

下边的方法很好理解，但是无法AC（因为超出时间限制了）

class Solution:
        def countBinarySubstrings(self, s):
            """
            :type s: str
            :rtype: int
            """
            if(len(s)<2 or s.count('0')==len(s) or s.count('1')==len(s)):
                return 0
            s2='01'
            s3='10'
            out=0
            while(s.count(s2) or s.count(s3)):
                out+=s.count(s2)
                s2='0'+s2+'1'
                out+=s.count(s3)
                s3='1'+s3+'0'
            return out