資訊專欄INFORMATION COLUMN
摘要：則不算，因?yàn)閮蓚€(gè)被分割開(kāi)了，不是連續(xù)的。思路只記錄前一組是還是，以及出現(xiàn)的次數(shù)。相同，則判斷是否與前一個(gè)字符相同。那么此時(shí)需要拋棄前一組的所有內(nèi)容。當(dāng)前一組未配對(duì)字符數(shù)量達(dá)到時(shí)，說(shuō)明前一組已經(jīng)沒(méi)有可以匹配的字符。故把當(dāng)前組替換未前一組。
D88 696. Count Binary Substrings 題目鏈接
696. Count Binary Substrings
題目分析給定一個(gè)01字符串，返回僅用連續(xù)的0和1串所能組成的二進(jìn)制字符串個(gè)數(shù)。
例如，00110011，就包含0011，01，1100，10，0011，01共6個(gè)。001100則不算，因?yàn)閮蓚€(gè)00被11分割開(kāi)了，不是連續(xù)的。
思路 思路1:生成01，0011，000111和10，1100，111000字符串，再用substr_count函數(shù)去計(jì)算個(gè)數(shù)的。但是會(huì)超時(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ù)字時(shí)出棧。出完棧時(shí)，把后面出現(xiàn)的數(shù)字頂上，作為下一個(gè)出棧的棧。然而寫起來(lái)略嫌麻煩。寫了個(gè)Wrong Answer出來(lái)就放棄了。于是又換了個(gè)思路。
思路3只記錄前一組是0還是1，以及出現(xiàn)的次數(shù)。
先取字符串的第一個(gè)字符作為第一組的字符。
從第二個(gè)字符開(kāi)始判斷。
判斷是否與第一組出現(xiàn)的字符相同。相同，則判斷是否與前一個(gè)字符相同。這里需要注意的是，前一組的字符不一定等于前一個(gè)字符。所以需要分開(kāi)判斷。
如果與前一個(gè)字符相同，則給前一組字符出現(xiàn)個(gè)數(shù)（或者叫長(zhǎng)度）+1。如果與前一個(gè)字符不同，則說(shuō)明兩個(gè)相同的字符夾住了不同的字符（例如010或者101）。那么此時(shí)需要拋棄前一組的所有內(nèi)容。因?yàn)榍耙唤M已經(jīng)沒(méi)有內(nèi)容可以和下一組匹配了。所以需要把當(dāng)前組作為前一組，把當(dāng)前字符作為下一組。
如果當(dāng)前字符與前一組的字符不同，則說(shuō)明配對(duì)成功。
前一組未配對(duì)字符數(shù)量減1，當(dāng)前組未配對(duì)數(shù)量+1。這里是因?yàn)椋?dāng)前在變成前一組的時(shí)候，會(huì)與其后面的字符匹配，到時(shí)候會(huì)減去對(duì)應(yīng)數(shù)量。因此這里需要+1。
當(dāng)前一組未配對(duì)字符數(shù)量達(dá)到0時(shí)，說(shuō)明前一組已經(jīng)沒(méi)有可以匹配的字符。故把當(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;
}
}
若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/31731.html
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...
摘要：題目鏈接題目分析在二叉樹(shù)中，若兩個(gè)葉子節(jié)點(diǎn)的層數(shù)相同，但具有不同的父節(jié)點(diǎn)，那么這兩個(gè)節(jié)點(diǎn)互為節(jié)點(diǎn)。給定一個(gè)二叉樹(shù)及兩個(gè)節(jié)點(diǎn)，返回兩個(gè)節(jié)點(diǎn)在二叉樹(shù)中，是否互為節(jié)點(diǎn)。遍歷完成后，直接判斷數(shù)組中對(duì)應(yīng)的值是否相同即可。 D76 993. Cousins in Binary Tree 題目鏈接 993. Cousins in Binary Tree 題目分析 在二叉樹(shù)中，若兩個(gè)葉子節(jié)點(diǎn)的層數(shù)相同...
摘要：題目鏈接題目分析給定一個(gè)數(shù)字，返回其二進(jìn)制形式中，和是否交替出現(xiàn)。若為偶數(shù)，最低位為，那么只能重復(fù)出現(xiàn)串。根據(jù)以上規(guī)則創(chuàng)建長(zhǎng)度為給定數(shù)字二進(jìn)制長(zhǎng)度一半的串，并轉(zhuǎn)換為十進(jìn)制。最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 D58 693. Binary Number with Alternating Bits 題目鏈接 693. Binary Number with Alternati...
摘要：題目鏈接題目分析反轉(zhuǎn)二叉樹(shù)。思路類似反轉(zhuǎn)兩個(gè)變量，先把左右子樹(shù)存進(jìn)單獨(dú)的變量，再相互覆蓋左右子樹(shù)。并對(duì)子樹(shù)進(jìn)行相同的操作。最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 D59 226. Invert Binary Tree 題目鏈接 226. Invert Binary Tree 題目分析 反轉(zhuǎn)二叉樹(shù)。 思路 類似反轉(zhuǎn)兩個(gè)變量，先把左右子樹(shù)存進(jìn)單獨(dú)的變量，再相互覆蓋左右子樹(shù)。 并...
摘要：題目鏈接題目分析給定一個(gè)數(shù)字，計(jì)算其二進(jìn)制表示中，出現(xiàn)的兩個(gè)最大距離。因?yàn)橹挥幸粋€(gè)是沒(méi)辦法比較距離的。當(dāng)出現(xiàn)時(shí)，判斷當(dāng)前距離是否大于記錄的最大值。最后判斷當(dāng)只有一個(gè)時(shí)，直接返回。否則返回所記錄的最大距離。 D47 868. Binary Gap 題目鏈接 868. Binary Gap 題目分析 給定一個(gè)數(shù)字，計(jì)算其二進(jìn)制表示中，出現(xiàn)的兩個(gè)1最大距離。 思路 當(dāng)然是先轉(zhuǎn)換成二進(jìn)制了。再...
閱讀 3190·2021-11-22 12:06
閱讀 850·2021-09-03 10:29
閱讀 6876·2021-09-02 09:52
閱讀 2154·2019-08-30 15:52
閱讀 3569·2019-08-29 16:39
閱讀 1340·2019-08-29 15:35
閱讀 2237·2019-08-29 15:17
閱讀 1559·2019-08-29 11:17
