Leetcode696 计数二进制子串

题目描述

file

方法一:按连续相同字符计数分组

class Solution:
    def countBinarySubstrings(self,s):
        counts = []
        i = 0
        while i < len(s):
            j = i
            while j < len(s) and s[i] == s[j]:
                j += 1
            counts.append(j-i)
            i = j
        ans = 0
        for i in range(len(counts)-1):
            ans += min(counts[i],counts[i+1])
        return ans

 

方法二

class Solution:
    def countBinarySubstrings(self,s):
        cur,last,res = 1,0,0
        for i in range(1,len(s)):
            if(s[i] == s[i-1]):
                cur += 1
            else:
                last = cur
                cur = 1
            if(last >= cur):
                res += 1
        return res

 

思路:

  • 方法一 : 具体可见 题解
  • 方法二 :用last来记录之前一种数字的个数, cur来记录当前数字的个数; 当last >= cur的时候, res ++;