我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 696. 計數二進制子串
題目
給定一個字串 s，計算具有相同數量0和1的非空(連續)子字串的數量，并且這些子字串中的所有0和所有1都是組合在一起的，
重復出現的子串要計算它們出現的次數，
示例 1 :
輸入: "00110011"
輸出: 6
解釋: 有6個子串具有相同數量的連續1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”，
請注意，一些重復出現的子串要計算它們出現的次數，
另外，“00110011”不是有效的子串，因為所有的0（和1）沒有組合在一起，
示例 2 :
輸入: "10101"
輸出: 4
解釋: 有4個子串：“10”，“01”，“10”，“01”，它們具有相同數量的連續1和0，
注意：
- s.length 在1到50,000之間，
- s 只包含“0”或“1”字符，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-binary-substrings
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-01壓縮，前后差值累積和
必須是連續的且數量相等的0和1都有，那么，實際就是 01和10兩種形式的雙向擴展，這兩種形式的N種擴展壓縮之后就是N01N或者N10N;
再通俗點，把10串壓碩訓，比如把“110001101110000”壓縮為232134，那么從壓縮后的第二個數開始每個數與前一個數的最小值的累加和就是最終解，即：
\[min(2,3)+min(3,2)+min(2,1)+min(1,3)+min(3,4) \]
原因：因為必須有相同數量的0和1，那么只需要知道符合條件的0或者1其中一個數量就能得到當前整個串及其子串的所有數量（其實就是0/1最大連續值）；
程式可以這樣寫（初始m=n=count=0）：
- 先求首個字符的連續數m，然后從下一個不同的字符開始計數n，只要n不大于m，就count++；
- 當n>m時，把n當做m，重復第一步的邏輯即可；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020-8-10 14:38:39
* @Description: 696. 計數二進制子串
*
*/
public class LeetCode_0696 {
}
class Solution_0696 {
/**
* @author: ZhouJie
* @date: 2020-8-10 14:41:19
* @param: @param s
* @param: @return
* @return: int
* @Description: 1-01壓縮，壓縮連續01的串為統計數，然后計算每一個數與前一個數的最小值的累加和；
*
*/
public int countBinarySubstrings(String s) {
int count = 0;
if (s == null || s.length() == 0) {
return count;
}
char[] cs = s.toCharArray();
char c = cs[0];
int m = 0, n = 0;
for (int i = 0; i < cs.length; i++) {
if (cs[i] == c) {
n++;
if (n <= m) {
count++;
}
} else {
c = cs[i--];
m = n;
n = 0;
}
}
return count;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/86679.html
標籤：Java
上一篇：JVM垃圾回收（GC）