LeetCode刷题之696.计数二进制子串

LeetCode刷题之696.计数二进制子串

我不知道将去向何方，但我已在路上！

时光匆匆，虽未曾谋面，却相遇于斯，实在是莫大的缘分，感谢您的到访 ！

• 题目：
  给定一个字符串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:
    def countBinarySubstrings(self, s: str) -> int:
        a,jicun,result = [0],s[0],0
        for i in range(len(s)):
            if s[i] == jicun:
                a[-1] += 1
            if s[i] != jicun:
                a.append(1)
                jicun = s[i]
        for i in range(len(a)-1):
            result += min(a[i],a[i+1])
        return(result)
# 执行用时 :216 ms, 在所有 python3 提交中击败了62.96%的用户
# 内存消耗 :14.2 MB, 在所有 python3 提交中击败了17.74%的用户

• 算法说明：
  遍历字符串s，统计每个字符出现的个数，将其记录在a中，如果当前遍历的元素和jicun元素一样，将a的最后一个数字+1，如果不一样在a的最后面添加1，并将jicun的值更新为当前的元素，继续循环；用for循环遍历a中的元素，取相邻两个元素中较小的一个累加到result中，返回result。