696. 计数二进制子串

Posted on Edited on In , ,
转载自Leet Code

题目描述

给定一个字符串 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。

注意： - s.length 在1到50,000之间。 - s 只包含“0”或“1”字符。

方法一: 按字符分组

\(T(N) = O(N)\), \(S(N) = O(N)\)

我们可以将字符串 \(s\) 按照 0 和 1 的连续片段分组，并存储在 \(counts\) 数组中。 例如 \(s=00111011\)，可以得到 \(counts=\) {\(2,3,1,2\)}。 此时 \(counts\) 数组中的两个相邻的数代表的一定是两种不同的字符。 假设 \(counts\) 中两个相邻的数字为 \(u\) 和 \(v\)， 则它们能组成的满足条件的子串数目为 \(min\) {\(u\), \(v\)}. 即一对相邻的数字对答案的贡献。 我们只需要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。

{.line-numbers}
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
27
28
29
30
class Solution696 
{
    public int countBinarySubstrings(String s) 
    {
    	if (s==null||s.length()<=0) return 0;

    	Queue<Integer> list = new LinkedList<Integer>();
    	int count = 1;
    	
    	for (int i0=0, i=1; i<s.length(); i++)
    	{
    		if (s.charAt(i)==s.charAt(i0))
    			count++;
    		else
    		{
    			list.add(count); count = 1; i0 = i;
    		}
    	}
    	list.add(count);
    	
    	count = 0; int last = list.poll();
    	while(!list.isEmpty())
    	{
    		int num = list.poll();
    		count+=Math.min(last, num);
    		last = num;
    	}
    	return count;
    }
}

方法二: 按字符分组 (改进)

\(T(N) = O(N)\), \(S(N) = O(N)\)

其实对于位置 \(i\)，我们只关心 \(i-1\) 处的 \(counts\) 值， 因此可以用一个 \(last\) 变量来维护当前位置的前一个位置， 这样就可以省去一个 \(counts\) 数组的空间。

{.line-numbers}
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 Solution696 
{
    public int countBinarySubstrings(String s) 
	{
        List<Integer> counts = new ArrayList<Integer>();
        
        int i = 0;
        while(i<s.length()) 
        {
            char ch = s.charAt(i);
            
            int count = 0;
            while (i<s.length() && s.charAt(i)==ch) 
            {
                i++; count++;
            }
            counts.add(count);
        }
        int ans = 0;
        for ( i = 1; i < counts.size(); ++i) 
        {
            ans += Math.min(counts.get(i), counts.get(i - 1));
        }
        return ans;
    }
}