LWC 54：696. Count Binary Substrings

LWC 54：696. Count Binary Substrings

Problem:

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: “00110011” Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”. Notice that some of these substrings repeat and are counted the number of times they occur. Also, “00110011” is not a valid substring because all the 0’s (and 1’s) are not grouped together.

Example 2:

Input: “10101” Output: 4 Explanation: There are 4 substrings: “10”, “01”, “10”, “01” that have equal number of consecutive 1’s and 0’s.

Note:

s.length will be between 1 and 50,000.

s will only consist of “0” or “1” charters.

```    public int countBinarySubstrings(String s) {

int n = s.length();
char[] cs = s.toCharArray();

int cnt = 0;
for (int i = 1; i < n; ++i){
if (group(cs, i)) cnt ++;
}
return cnt;
}

boolean group(char[] cs, int j){
int cnt = 1;
int pre = cs[j] - '0';
j --;

while (j >= 0 && cs[j] - '0' == pre) {
cnt ++;
j --;
}

while (j >= 0 && cs[j] - '0' != pre && cnt != 0) {
cnt --;
j --;
}

return cnt == 0;
}```

```    public int countBinarySubstrings(String s) {
int n = s.length();
char[] cs = s.toCharArray();

int now = cs[0] - '0';
int cnt = 0;
int ans = 0;
int lst = 0;

for (int i = 0; i < n; ++i) {
if (now != cs[i]) {
ans += Math.min(cnt, lst);
lst = cnt;
cnt = 1;
now = cs[i];
}
else {
cnt ++;
}
}

ans += Math.min(cnt, lst);
return ans;
}```

```    public int countBinarySubstrings(String s) {
int n = s.length();
char[] cs = s.toCharArray();
int[] num = new int[n];
for (int i = 0; i < n; ++i) {
num[i] = cs[i] == '0' ? - 1 : 1;
}

int[] sum = new int[n + 1];
for (int i = 0; i < n; ++i) {
sum[i + 1] = sum[i] + num[i];
}

Map<Integer, Integer> map = new HashMap<>();
map.put(0, 0);
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (map.containsKey(sum[i])) {
if (group(cs, map.get(sum[i]), i - 1)) cnt++;

}
map.put(sum[i], i);
}
return cnt;
}

boolean group(char[] cs, int i, int j) {
int prev = cs[i] - '0';
int n = j - i + 1;
for (int k = 1; k < n / 2; ++k) {
if (prev != cs[k + i] - '0') return false;
}
return true;
} ```

0 条评论

相关文章

06 - JavaSE之常用类

public StringBuffer append(...) 可以为该 StringBuffer 对象添加字符序列，返回添加后的该 StringBuffer ...

672

2448

1.7K7

822

1272

ThreadLocal基本原理及运用

ThreadLocal提供本地线程变量。这个变量里面的值（通过get方法获取）是和其他线程分割开来的，变量的值只有当前线程能访问到，不像一般的类型比如Perso...

872

20110

2735

821