Krains's Blog

vuePress-theme-reco Krains    2020 - 2021
Krains's Blog Krains's Blog

Choose mode

  • dark
  • auto
  • light
Home
Category
  • Algorithm
  • LeetCode题解
  • 数据结构
  • 计算机基础知识
  • Java基础
  • Java多线程
  • JVM
  • MySQL
  • 设计模式
Tag
TimeLine
Contact
  • GitHub (opens new window)
author-avatar

Krains

80

Article

22

Tag

Home
Category
  • Algorithm
  • LeetCode题解
  • 数据结构
  • 计算机基础知识
  • Java基础
  • Java多线程
  • JVM
  • MySQL
  • 设计模式
Tag
TimeLine
Contact
  • GitHub (opens new window)

696. 计数二进制子串

vuePress-theme-reco Krains    2020 - 2021

696. 计数二进制子串


Krains 2020-08-10 09:42:23 字符串

# 题目链接 (opens new window)

仔细观察发现,连续0与连续1构成的串中其符合条件的子串的数目等于Min(n,m)Min(n,m)Min(n,m),n、m分别为连续0和1的个数。

对于这样的问题,解法有很多,简单的一种可以用额外的数组存一下连续0和连续1个数,然后然后遍历数组,统计相邻的最小值即可。

若不用额外空间,考虑的细节就多一点,以下给出了两种相似的解法,细节有所不同。

class Solution {
    public int countBinarySubstrings(String s) {
        int ans = 0;
        int i = 0;
        // pre表示之前一段连续1或0个数,cur为当前连续0或1的个数
        int pre = 0, cur = 0;
        while(i < s.length()){
            char c = s.charAt(i);
            while(i < s.length() && s.charAt(i) == c){
                i++;
                cur++;
            }
            ans += Math.min(pre, cur);
            pre = cur;
            cur = 0;
        }
        
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int countBinarySubstrings(String s) {
        int ans = 0;
        int pre = 0, cur = 1;
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i-1) == s.charAt(i)){
                cur++;
            }else{
                ans += Math.min(pre, cur);
                pre = cur;
                cur = 1;
            }
        }
        // 加上末尾未统计的
        ans += Math.min(pre, cur);

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 复杂度分析

  • 时间复杂度:O(1)O(1)O(1)

  • 空间复杂度:O(1)O(1)O(1)

  • 题目链接
  • 复杂度分析