[LintCode/LeetCode] Count Binary Substrings

BaronZhang 发布于2019-08-16 12:44 / 1501人阅读

Problem

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.

Example

Example 1:

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.
Example 2:

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1"s and 0"s.

Solution

public class Solution {
    /**
     * @param s: a string
     * @return: the number of substrings
     */
    public int countBinarySubstrings(String s) {
        // Write your code here
        int countZero = 0, countOne = 0, result = 0;
        char[] str = s.toCharArray();
        for (int i = 0; i < str.length; i++) {
            if (i == 0) {
                if (str[i] == "0") {
                    countZero++;
                } else countOne++;
            } else {
                if (str[i] == "0") {
                    if (str[i-1] == "0") countZero++;
                    else countZero = 1;
                    if (countOne >= countZero) result++;
                } else {
                    if (str[i-1] == "1") countOne++;
                    else countOne = 1;
                    if (countZero >= countOne) result++;
                }
            }
        }
        return result;
    }
}

云服务器 GPU云服务器 Substrings Binary Count binary-tree

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71631.html

[LintCode/LeetCode] Scramble String

摘要：首先将两个字符串化成字符数组，排序后逐位比较，确定它们等长且具有相同数量的相同字符。然后，从第一个字符开始向后遍历，判断和中以这个坐标为中点的左右两个子字符串是否满足第一步中互为的条件设分为和，分为和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

MASAILA 2019-08-14 15:45 评论0 收藏0
Leetcode PHP题解--D88 696. Count Binary Substrings

摘要：则不算，因为两个被分割开了，不是连续的。思路只记录前一组是还是，以及出现的次数。相同，则判断是否与前一个字符相同。那么此时需要抛弃前一组的所有内容。当前一组未配对字符数量达到时，说明前一组已经没有可以匹配的字符。故把当前组替换未前一组。 D88 696. Count Binary Substrings 题目链接 696. Count Binary Substrings 题目分析给定一...

lanffy 2019-07-01 14:00 评论0 收藏0
[LintCode/LeetCode] Count Univalue Subtrees

Problem Given a binary tree, count the number of uni-value subtrees. A Uni-value subtree means all nodes of the subtree have the same value. Example Given root = {5,1,5,5,5,#,5}, return 4. 5...

luzhuqun 2019-08-16 12:44 评论0 收藏0
[LintCode/LeetCode] Balanced Binary Tree

摘要：根据二叉平衡树的定义，我们先写一个求二叉树最大深度的函数。在主函数中，利用比较左右子树的差值来判断当前结点的平衡性，如果不满足则返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...

morgan 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Binary Tree Pruning

Problem Binary Tree PruningWe are given the head node root of a binary tree, where additionally every nodes value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not...

rockswang 2019-08-16 12:37 评论0 收藏0