成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Count Binary Substrings

BaronZhang / 1524人閱讀

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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71631.html

相關(guān)文章

  • [LintCode/LeetCode] Scramble String

    摘要：首先將兩個字符串化成字符數(shù)組，排序后逐位比較，確定它們等長且具有相同數(shù)量的相同字符。然后，從第一個字符開始向后遍歷，判斷和中以這個坐標(biāo)為中點(diǎn)的左右兩個子字符串是否滿足第一步中互為的條件設(shè)分為和，分為和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

    MASAILA 評論0 收藏0

  • Leetcode PHP題解--D88 696. Count Binary Substrings

    摘要：則不算，因為兩個被分割開了，不是連續(xù)的。思路只記錄前一組是還是，以及出現(xiàn)的次數(shù)。相同，則判斷是否與前一個字符相同。那么此時需要拋棄前一組的所有內(nèi)容。當(dāng)前一組未配對字符數(shù)量達(dá)到時，說明前一組已經(jīng)沒有可以匹配的字符。故把當(dāng)前組替換未前一組。 D88 696. Count Binary Substrings 題目鏈接 696. Count Binary Substrings 題目分析 給定一...

    lanffy 評論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 評論0 收藏0

  • [LintCode/LeetCode] Balanced Binary Tree

    摘要：根據(jù)二叉平衡樹的定義，我們先寫一個求二叉樹最大深度的函數(shù)。在主函數(shù)中，利用比較左右子樹的差值來判斷當(dāng)前結(jié)點(diǎn)的平衡性，如果不滿足則返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...

    morgan 評論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 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<