摘要:則不算,因為兩個被分割開了,不是連續的。思路只記錄前一組是還是,以及出現的次數。相同,則判斷是否與前一個字符相同。那么此時需要拋棄前一組的所有內容。當前一組未配對字符數量達到時,說明前一組已經沒有可以匹配的字符。故把當前組替換未前一組。
D88 696. Count Binary Substrings 題目鏈接
696. Count Binary Substrings
題目分析給定一個01字符串,返回僅用連續的0和1串所能組成的二進制字符串個數。
例如,00110011,就包含0011,01,1100,10,0011,01共6個。001100則不算,因為兩個00被11分割開了,不是連續的。
思路 思路1:生成01,0011,000111和10,1100,111000字符串,再用substr_count函數去計算個數的。但是會超時。
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
用棧的思想。先把數字壓入棧內,遇到不同數字時出棧。出完棧時,把后面出現的數字頂上,作為下一個出棧的棧。然而寫起來略嫌麻煩。寫了個Wrong Answer出來就放棄了。于是又換了個思路。
思路3只記錄前一組是0還是1,以及出現的次數。
先取字符串的第一個字符作為第一組的字符。
從第二個字符開始判斷。
判斷是否與第一組出現的字符相同。相同,則判斷是否與前一個字符相同。這里需要注意的是,前一組的字符不一定等于前一個字符。所以需要分開判斷。
如果與前一個字符相同,則給前一組字符出現個數(或者叫長度)+1。如果與前一個字符不同,則說明兩個相同的字符夾住了不同的字符(例如010或者101)。那么此時需要拋棄前一組的所有內容。因為前一組已經沒有內容可以和下一組匹配了。所以需要把當前組作為前一組,把當前字符作為下一組。
如果當前字符與前一組的字符不同,則說明配對成功。
前一組未配對字符數量減1,當前組未配對數量+1。這里是因為,當前在變成前一組的時候,會與其后面的字符匹配,到時候會減去對應數量。因此這里需要+1。
當前一組未配對字符數量達到0時,說明前一組已經沒有可以匹配的字符。故把當前組替換未前一組。
如此循環即可。
最終代碼$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; } }
若覺得本文章對你有用,歡迎用愛發電資助。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/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...
摘要:題目鏈接題目分析在二叉樹中,若兩個葉子節點的層數相同,但具有不同的父節點,那么這兩個節點互為節點。給定一個二叉樹及兩個節點,返回兩個節點在二叉樹中,是否互為節點。遍歷完成后,直接判斷數組中對應的值是否相同即可。 D76 993. Cousins in Binary Tree 題目鏈接 993. Cousins in Binary Tree 題目分析 在二叉樹中,若兩個葉子節點的層數相同...
摘要:題目鏈接題目分析給定一個數字,返回其二進制形式中,和是否交替出現。若為偶數,最低位為,那么只能重復出現串。根據以上規則創建長度為給定數字二進制長度一半的串,并轉換為十進制。最終代碼若覺得本文章對你有用,歡迎用愛發電資助。 D58 693. Binary Number with Alternating Bits 題目鏈接 693. Binary Number with Alternati...
摘要:題目鏈接題目分析反轉二叉樹。思路類似反轉兩個變量,先把左右子樹存進單獨的變量,再相互覆蓋左右子樹。并對子樹進行相同的操作。最終代碼若覺得本文章對你有用,歡迎用愛發電資助。 D59 226. Invert Binary Tree 題目鏈接 226. Invert Binary Tree 題目分析 反轉二叉樹。 思路 類似反轉兩個變量,先把左右子樹存進單獨的變量,再相互覆蓋左右子樹。 并...
摘要:題目鏈接題目分析給定一個數字,計算其二進制表示中,出現的兩個最大距離。因為只有一個是沒辦法比較距離的。當出現時,判斷當前距離是否大于記錄的最大值。最后判斷當只有一個時,直接返回。否則返回所記錄的最大距離。 D47 868. Binary Gap 題目鏈接 868. Binary Gap 題目分析 給定一個數字,計算其二進制表示中,出現的兩個1最大距離。 思路 當然是先轉換成二進制了。再...
閱讀 3012·2021-11-22 12:06
閱讀 599·2021-09-03 10:29
閱讀 6526·2021-09-02 09:52
閱讀 2013·2019-08-30 15:52
閱讀 3411·2019-08-29 16:39
閱讀 1190·2019-08-29 15:35
閱讀 2061·2019-08-29 15:17
閱讀 1416·2019-08-29 11:17