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

資訊專欄INFORMATION COLUMN

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

lanffy / 2209人閱讀

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

D88 696. Count Binary Substrings 題目鏈接

696. Count Binary Substrings

題目分析

給定一個01字符串，返回僅用連續(xù)的0和1串所能組成的二進制字符串個數(shù)。

例如，00110011，就包含0011，01，1100，10，0011，01共6個。001100則不算，因為兩個00被11分割開了，不是連續(xù)的。

思路 思路1:

生成01，0011，000111和10，1100，111000字符串，再用substr_count函數(shù)去計算個數(shù)的。但是會超時。

function countBinarySubstrings($s) {
    $totalLength = strlen($s);
    $total = 0;
    for($i=0;$i<=$totalLength/2; $i++){
        //01 0011 000111
        $boz = str_repeat("0",$i).str_repeat("1",$i);
        //10 1100 111000
        $bzo = strrev($boz);
        $total += substr_count($s, $boz);
        $total += substr_count($s, $bzo);
    }
    return $total;
}
思路2

用棧的思想。先把數(shù)字壓入棧內(nèi)，遇到不同數(shù)字時出棧。出完棧時，把后面出現(xiàn)的數(shù)字頂上，作為下一個出棧的棧。然而寫起來略嫌麻煩。寫了個Wrong Answer出來就放棄了。于是又換了個思路。

思路3

只記錄前一組是0還是1，以及出現(xiàn)的次數(shù)。

先取字符串的第一個字符作為第一組的字符。
從第二個字符開始判斷。
判斷是否與第一組出現(xiàn)的字符相同。相同，則判斷是否與前一個字符相同。這里需要注意的是，前一組的字符不一定等于前一個字符。所以需要分開判斷。
如果與前一個字符相同，則給前一組字符出現(xiàn)個數(shù)（或者叫長度）+1。如果與前一個字符不同，則說明兩個相同的字符夾住了不同的字符（例如010或者101）。那么此時需要拋棄前一組的所有內(nèi)容。因為前一組已經(jīng)沒有內(nèi)容可以和下一組匹配了。所以需要把當(dāng)前組作為前一組，把當(dāng)前字符作為下一組。

如果當(dāng)前字符與前一組的字符不同，則說明配對成功。
前一組未配對字符數(shù)量減1，當(dāng)前組未配對數(shù)量+1。這里是因為，當(dāng)前在變成前一組的時候，會與其后面的字符匹配，到時候會減去對應(yīng)數(shù)量。因此這里需要+1。

當(dāng)前一組未配對字符數(shù)量達到0時，說明前一組已經(jīng)沒有可以匹配的字符。故把當(dāng)前組替換未前一組。

如此循環(huán)即可。

最終代碼 
 $val){
            if($stack1 == $val){
                if($val == $prev){
                    $stack1Amount++;
                }
                else{
                    $stack1 = $stack2;
                    $stack1Amount = $stack2Amount;
                    $stack2Amount = 0;
                    $stack2 = null;
                }
            }
            if($stack1 != $val){
                $stack2 = $val;
                $stack2Amount++;
                $stack1Amount--;
                $total++;
            }
            if($stack1Amount == 0){
                $stack1 = $stack2;
                $stack1Amount = $stack2Amount;
                $stack2 = null;
                $stack2Amount = 0;
            }
            $prev = $val;
        }
        return $total;
    }
}

若覺得本文章對你有用，歡迎用愛發(fā)電資助。

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

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

相關(guān)文章

  • [LintCode/LeetCode] Count Binary Substrings

    Problem Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0s and 1s, and all the 0s and all the 1s in these substrings are grouped consecutively. Subs...

    BaronZhang 評論0 收藏0

  • Leetcode PHP題解--D76 993. Cousins in Binary Tree

    摘要：題目鏈接題目分析在二叉樹中，若兩個葉子節(jié)點的層數(shù)相同，但具有不同的父節(jié)點，那么這兩個節(jié)點互為節(jié)點。給定一個二叉樹及兩個節(jié)點，返回兩個節(jié)點在二叉樹中，是否互為節(jié)點。遍歷完成后，直接判斷數(shù)組中對應(yīng)的值是否相同即可。 D76 993. Cousins in Binary Tree 題目鏈接 993. Cousins in Binary Tree 題目分析 在二叉樹中，若兩個葉子節(jié)點的層數(shù)相同...

    張遷 評論0 收藏0

  • Leetcode PHP題解--D58 693. Binary Number with Altern

    摘要：題目鏈接題目分析給定一個數(shù)字，返回其二進制形式中，和是否交替出現(xiàn)。若為偶數(shù)，最低位為，那么只能重復(fù)出現(xiàn)串。根據(jù)以上規(guī)則創(chuàng)建長度為給定數(shù)字二進制長度一半的串，并轉(zhuǎn)換為十進制。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D58 693. Binary Number with Alternating Bits 題目鏈接 693. Binary Number with Alternati...

    yexiaobai 評論0 收藏0

  • Leetcode PHP題解--D59 226. Invert Binary Tree

    摘要：題目鏈接題目分析反轉(zhuǎn)二叉樹。思路類似反轉(zhuǎn)兩個變量，先把左右子樹存進單獨的變量，再相互覆蓋左右子樹。并對子樹進行相同的操作。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D59 226. Invert Binary Tree 題目鏈接 226. Invert Binary Tree 題目分析 反轉(zhuǎn)二叉樹。 思路 類似反轉(zhuǎn)兩個變量，先把左右子樹存進單獨的變量，再相互覆蓋左右子樹。 并...

    miqt 評論0 收藏0

  • Leetcode PHP題解--D47 868. Binary Gap

    摘要：題目鏈接題目分析給定一個數(shù)字，計算其二進制表示中，出現(xiàn)的兩個最大距離。因為只有一個是沒辦法比較距離的。當(dāng)出現(xiàn)時，判斷當(dāng)前距離是否大于記錄的最大值。最后判斷當(dāng)只有一個時，直接返回。否則返回所記錄的最大距離。 D47 868. Binary Gap 題目鏈接 868. Binary Gap 題目分析 給定一個數(shù)字，計算其二進制表示中，出現(xiàn)的兩個1最大距離。 思路 當(dāng)然是先轉(zhuǎn)換成二進制了。再...

    Flink_China 評論0 收藏0

發(fā)表評論

0條評論

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