前言
持续更新了
正文
问题来源
本问题来自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。
分析：
func reverseString(s []byte) {
i, j := 0, len(s)-1
for i < j {
s[i], s[j] = s[j], s[i]
i++
j--
}
}func min(a, b int) int {
if a < b {
return a
}
return b
}
func countBinarySubstrings(s string) int {
counts := make([]int, 0)
for i := 0; i < len(s);{
count := 0
ch := s[i]
for ;i < len(s) && ch == s[i]; i++ {
count++
}
counts = append(counts, count)
}
res := 0
for i := 1; i < len(counts); i++ {
res += min(counts[i], counts[i-1])
}
return res
}
总结：
勤思考。
结语
不管怎么样好好加油。
