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。
二、代码和思路
第一次:
主要考虑左右连续二进制数的长度,然后选择两者之间的最小值加入到count,从右边的开始位置继续遍历
这样相当于重复遍历右边的连续二进制的数量,做了下面第二次的改进
class Solution(object):
def countBinarySubstrings(self, s):
"""
:type s: str
:rtype: int
"""
count=0
i,j,n=0,0,len(s)
while i<n-1:
k=i
while i<n-1 and s[i+1]==s[i]:
i += 1
if i==n-1:return count
i += 1
j=i
while j<n-1 and s[j+1]==s[j]:
j += 1
count += min(i-k,j-i+1)
return count
第二次:
1.这里首先查看第一次连续相等二进制的长度,记录
2.寻找第二个连续相等二进制的长度,与第一次长度相比的较小值加到count,并将第二次的连续相等二进制的长度记录
3.重复1,2,这里的算法复杂度相当于O(n)
class Solution(object):
def countBinarySubstrings(self, s):
"""
:type s: str
:rtype: int
"""
count=0
i,j,n=0,0,len(s)
while i<n-1 and s[i+1]==s[i]:
i += 1
cou_part=i-j+1
j=i
while i<n-1:
i += 1
while i<n-1 and s[i+1]==s[i]:
i += 1
count += min(cou_part,i-j)
if i==n-1:return count
cou_part=i-j
j=i
return count
三、运行结果