LeetCode

原题:

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.

Example1

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.

Example2

Note

  • s.length will be between 1 and 50,000.
  • s will only consist of “0” or “1” characters.

题目大意

给一个字符串s,计算具有相同数字0和1的非空(连续)子字符串的数量,并且这些子字符串中的全部0和全部1被连续分组。子串发生多次被计数的次数。

解题思路

纪录当前的0或者1的数量,然后和后面的1或者0的数量进行对比。
代码实现(java):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class {
public int countBinarySubstrings(String s) {
int zeros = 0;
int ones = 0;
int res = 0;
for (int i = 0; i < s.length(); i++) {
if (i == 0) {
if (s.charAt(i) == '1')
ones++;
else
zeros++;
} else {
if (s.charAt(i) == '1') {
ones = (s.charAt(i - 1) == '1') ? ones + 1 : 1;
if (zeros >= ones)
res++;
} else if (s.charAt(i) == '0') {
zeros = (s.charAt(i - 1) == '0') ? zeros + 1 : 1;
if (ones >= zeros)
res++;
}
}
}
return res;
}
}

python实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def countBinarySubstrings(self, s):
"""
:type s: str
:rtype: int
"""
ones = zeros = res = 0
for i in range(len(s)):
if i == 0:
if s[i] == '1':
ones += 1
else:
zeros += 1
else:
if s[i] == '1':
ones = ones + 1 if s[i - 1] == '1' else 1
if zeros >= ones:
res += 1
else:
zeros = zeros + 1 if s[i - 1] == '0' else 1
if ones >= zeros:
res += 1
return res