leetcode 696. Count Binary Substrings
LeetCode Binary count
2023-09-14 09:11:53 时间
Give a string s
, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
Example 1:
Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.
Example 2:
Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
Note:
s.length
will be between 1 and 50,000.s
will only consist of "0" or "1" characters.
解法1:
使用两个计数器,记录连续1和0的次数。每次循环时候,如果当前数字的计数器比之前数字的计数器数值小,则ans+=1。
计数细节:看到计数连续出现的字符,当s[i]==s[i-1],计数器+=1,否则reset计数器,将上次的计数存起来。
class Solution(object): def countBinarySubstrings(self, s): """ :type s: str :rtype: int """ # 00 11 00 11 # | | | | #cnt=2 new_cnt=2 cnt=2 new_cnt=2 # ans +=2 ans+=2 ans+=2 ans = 0 cnt = 1 pre_cnt = 0 for i in xrange(1, len(s)): if s[i]==s[i-1]: cnt += 1 else: pre_cnt = cnt cnt = 1 if pre_cnt >= cnt: ans += 1 return ans
直接将连续的字符串计数器用数组记录起来,然后将结果加起来!此法更直观!!
'00001111'
=>[4, 4]
=>min(4, 4)
=>4
'00110'
=>[2, 2, 1]
=>min(2, 2) + min(2, 1)
=>3
'10101'
=>[1, 1, 1, 1, 1]
=>4
class Solution(object): def countBinarySubstrings(self, s): cnt = 1 chunks = [] for i in xrange(1, len(x)): if s[i] == s[i-1]: cnt += 1 else: chunks.append(cnt) cnt = 1 return sum(min(chunks[i], chunks[i-1]) for i in xrange(1, len(chunks)))
上述解法有错,漏掉了s[-1]计数,修正后的:
class Solution(object): def countBinarySubstrings(self, s): """ :type s: str :rtype: int """ cnt = 1 arr = [] for i in range(1, len(s)): if s[i] == s[i-1]: cnt += 1 else: arr.append(cnt) cnt = 1 arr.append(cnt) return sum(min(arr[i], arr[i-1]) for i in range(1, len(arr)))
相关文章
- LeetCode每日一题-3:回文链表
- ☆打卡算法☆LeetCode 205. 同构字符串 算法解析
- ☆打卡算法☆LeetCode 211. 添加与搜索单词 - 数据结构设计 算法解析
- ☆打卡算法☆LeetCode 221. 最大正方形 算法解析
- ☆打卡算法☆LeetCode 225. 用队列实现栈 算法解析
- 有效的括号(leetcode 20)
- LeetCode第一题:两数之和-C++
- LeetCode笔记:Weekly Contest 306
- LeetCode周赛301,离大谱,手速场掉分,质量场掉大分……
- JavaScript刷LeetCode模板技巧篇(二)
- 【刷题day06】力扣(LeetCode)每日一刷[21. 合并两个有序链表][206. 反转链表 ][392. 判断子序列]
- leetcode 54. 螺旋矩阵 js高效实现
- Binary Tree Postorder Traversal — LeetCode
- LeetCode 78.子集 - Go 实现
- LeetCode - #63 不同路径 II
- LeetCode - #72 编辑距离(Top 100)
- LeetCode - #74 搜索二维矩阵
- 【动态规划】LeetCode 题解:416-分割等和子集