首页 > itarticle > 算法笔记: 力扣#696 计数二进制子串

算法笔记: 力扣#696 计数二进制子串

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class :
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans, prev, cur = 0, 0, 1
        
        for i in range(1, len(s)):
            if s[i] != s[i-1]:
                ans += min(prev, cur)
                prev, cur = cur, 1
            else:
                cur += 1
        return ans + min(prev, cur)

Java 实现

class  {
    public int countBinarySubstrings(String s) {
        int ans = 0;
        int prev = 0;
        int cur = 1;
        
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i) != s.charAt(i-1)){
                ans += (prev < cur ? prev : cur);
                prev = cur;
                cur = 1;
            }else{
                cur ++;
            }
        }
        return ans + (prev < cur ? prev : cur);
    }
}

时间复杂度

O(N).

空间复杂度

O(1).

链接

696. Count Binary Substrings
696. 计数二进制子串
 (English version) Algorithm Notes: Leetcode#696 Count Binary Substrings