LeetCode演算法題-Count Binary Substrings(Java實現)
這是悅樂書的第293 次更新,第311 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第161題(順位題號是696)。給定一個字串s,計算具有相同數字0和1的非空且連續子串的數量,並且這些子串中的所有0和所有1都是連續的。重複出現的子串也計算在內。例如:
輸入:“00110011”
輸出:6
說明:有6個子串具有相同數量的連續1和0:“0011”,“01”,“1100”,“10”,“0011”和“01”。其中一些子字串重複出現了,但是也需要計算它們出現的次數。此外,“00110011”不是有效的子字串,因為所有0(和1)都沒有組合在一起。
輸入:“10101”
輸出:4
說明:有4個子串:“10”,“01”,“10”,“01”具有相同數量的連續1和0。
注意:
-
字串長度將介於1到50,000之間。
-
s只包含“0”或“1”字元。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
題目的意思是在給定的字串中找到連續的0和1組成的子串個數,其中0和1是挨著的,可以有多個連續的0與多個連續的1。比如,0011,其中就有兩個子串符合,一是第二位與第三位組成的01,二是其本身,兩個0和兩個1。再比如00111,同樣也只有兩個子串符合,一是01,二是0011。所以,我們的判斷標準就變成了,在一個由0和1組成的連續子串中,0的個數與1的個數,取其中的較小值,就是可能的子串數。
對此,我們將原字串中,將每段連續的0或者1的個數統計出來,然後比較相鄰的兩段的值,取其中較小的進行累加,最後就是該字串所有可能的子串數。
此解法的時間複雜度是O(n),空間複雜度是O(n)。
public int countBinarySubstrings(String s) { int[] arr = new int[s.length()]; arr[0] = 1; int index = 0; for (int i=1; i<s.length(); i++) { if (s.charAt(i) != s.charAt(i-1)) { arr[++index] = 1; } else { arr[index]++; } } int count = 0; for (int i=1; i <= index; i++) { count += Math.min(arr[i], arr[i-1]); } return count; }
03 第二種解法
第一種解法中,我們將每段分組的值存到了新陣列中,在分段完後,再去計算總數,但是我們也可以不使用新陣列,直接在統計分段時,就將值累加起來。我們使用兩個臨時變數,一個儲存當前這段分組的長度,一個儲存上一段分組的長度,在迴圈字串中的字元時,如果當前字元和前一個字元不相等,說明該分段了,此時需要先比較兩個臨時變數的值,取較小的累加到count上去,然後將上一段的長度賦值給另外一個變數,當前新段的長度重置為1。在迴圈結束後,還需要再取兩者之間的較小值再累加一次,因為有可能最後一段就是連續的,而不能在迴圈裡進行判斷了。
public int countBinarySubstrings(String s) { int currentLength = 1, prevLength = 0, count = 0; for (int i=1; i<s.length(); i++) { if (s.charAt(i) != s.charAt(i-1)) { count += Math.min(prevLength, currentLength); prevLength = currentLength; currentLength = 1; } else { currentLength++; } } count += Math.min(prevLength, currentLength); return count; }
04 小結
演算法專題目前已日更超過四個月 ,演算法題文章161 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!