统计连续出现的 0 和 1 出现的次数,保存到一个counts数组中,如00110110,对应的数组为{2,2,1,2,1},所能组成子串的个数为min{u,v},u和v分别代表0和1的个数或者1和0的个数。应该返回2+1+1+1=5
法1
class Solution {
public int countBinarySubstrings(String s) {
//维护一个保存相邻的0和1出现次数的数组
List<Integer> counts = new ArrayList<>();
int p = 0;
int n = s.length();
//建立保存出现次数的数组
while(p < n){
char c = s.charAt(p);
int count = 0;
while(p<n && s.charAt(p)== c){
p++;
count++;
}
counts.add(count);
}
int ans = 0;
for(int i=1;i<counts.size();i++){
ans += Math.min(counts.get(i-1),counts.get(i));
}
return ans;
}
}
法2,一点优化,只保存i的前一个count
//省去一个counts数组
class Solution {
public int countBinarySubstrings(String s) {
int p = 0, n = s.length(), last = 0, ans = 0;
while (p < n) {
char c = s.charAt(p);
int count = 0;
while (p < n && s.charAt(p) == c) {
++p;
++count;
}
ans += Math.min(count, last);
last = count;
}
return ans;
}
}