【問題描述】[簡單]

【解答思路】

1. 按字符分組

將字符串 ss 按照 00 和 11 的連續(xù)段分組，存在counts 數(shù)組中，例如 s = 00111011，可以得到這樣的counts 數(shù)組：counts={2,3,1,2}。

這里counts 數(shù)組中兩個相鄰的數(shù)一定代表的是兩種不同的字符。假設(shè) counts 數(shù)組中兩個相鄰的數(shù)字為 u 或者 v，它們對應(yīng)著 u 個 0 和 v 個 1，或者 u 個 1 和 v 個 0。它們能組成的滿足條件的子串?dāng)?shù)目為 min{u,v}，即一對相鄰的數(shù)字對答案的貢獻。

我們只要遍歷所有相鄰的數(shù)對，求它們的貢獻總和，即可得到答案。

時間復(fù)雜度：O(N) 空間復(fù)雜度：O(N)

class Solution {public int countBinarySubstrings(String s) {List<Integer> counts = new ArrayList<Integer>();int ptr = 0, n = s.length();while (ptr < n) {char c = s.charAt(ptr);int count = 0;while (ptr < n && s.charAt(ptr) == c) {++ptr;++count;}counts.add(count);}int ans = 0;for (int i = 1; i < counts.size(); ++i) {ans += Math.min(counts.get(i), counts.get(i - 1));}return ans;} }

對于某一個位置 i，其實我們只關(guān)心 i - 1位置的counts 值是多少，所以可以用一個 last 變量來維護當(dāng)前位置的前一個位置，這樣可以省去一個 counts 數(shù)組的空間。

時間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public int countBinarySubstrings(String s) {int ptr = 0, n = s.length(), last = 0, ans = 0;while (ptr < n) {char c = s.charAt(ptr);int count = 0;while (ptr < n && s.charAt(ptr) == c) {++ptr;++count;}ans += Math.min(count, last);last = count;}return ans;} }

2. 遍歷 數(shù)前面?zhèn)€數(shù)大于后面?zhèn)€數(shù)的子串

定義兩個變量preLen和curLen，分別表示前面連續(xù)字符串中字符的個數(shù)，現(xiàn)在連續(xù)字符串中字符的個數(shù)。
當(dāng)前字符和上一個字符相等時curLen++,不相等時preLen=curLen,然后curLen設(shè)為1。
如果preLen>=curLen,那么結(jié)果+1。
例如0011,應(yīng)該輸出為2。
1.curLen=1,preLen=0,ret=0;
2.curLen=2,preLen=0,ret=0;
3.curLen=1,preLen=2,ret=1;//001中的01
4.curLen=2,preLen=2,ret=2;//0011中的0011

class Solution {public int countBinarySubstrings(String s) {int preLen=0,curLen=1,ret=0;for(int i=1;i<s.length();i++){if(s.charAt(i-1)==s.charAt(i)) curLen++;else{preLen=curLen;curLen=1;}if(preLen>=curLen) ret++;}return ret;} }

【總結(jié)】

1. 字符串?dāng)?shù)數(shù)題目 分類數(shù)找規(guī)律是一種思路

2.這題簡單題難在思路

3.

轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/count-binary-substrings/solution/ji-shu-er-jin-zhi-zi-chuan-by-leetcode-solution/

參考鏈接：https://leetcode-cn.com/problems/count-binary-substrings/solution/yi-ge-bi-jiao-qiao-miao-de-ban-fa-by-uygn9i8c6n/

總結(jié)

以上是生活随笔為你收集整理的[Leetcode][第696题][JAVA][计算二进制子串][分组]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。