class Solution {
public:
int numberOfSubstrings(string s) {
}
};
100348. 统计 1 显著的字符串的数量
给你一个二进制字符串 s。
请你统计并返回其中 1 显著 的 子字符串 的数量。
如果字符串中 1 的数量 大于或等于 0 的数量的 平方，则认为该字符串是一个 1 显著 的字符串 。
示例 1：
输入：s = "00011"
输出：5
解释：
1 显著的子字符串如下表所示。
| i | j | s[i..j] | 0 的数量 | 1 的数量 |
|---|---|---|---|---|
| 3 | 3 | 1 | 0 | 1 |
| 4 | 4 | 1 | 0 | 1 |
| 2 | 3 | 01 | 1 | 1 |
| 3 | 4 | 11 | 0 | 2 |
| 2 | 4 | 011 | 1 | 2 |
示例 2：
输入：s = "101101"
输出：16
解释：
1 不显著的子字符串如下表所示。
总共有 21 个子字符串，其中 5 个是 1 不显著字符串，因此有 16 个 1 显著子字符串。
| i | j | s[i..j] | 0 的数量 | 1 的数量 |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 |
| 4 | 4 | 0 | 1 | 0 |
| 1 | 4 | 0110 | 2 | 2 |
| 0 | 4 | 10110 | 2 | 3 |
| 1 | 5 | 01101 | 2 | 3 |
提示：
1 <= s.length <= 4 * 104s 仅包含字符 '0' 和 '1'。相似题目
原站题解
golang 解法, 执行用时: 53 ms, 内存消耗: 6.5 MB, 提交时间: 2024-07-29 17:48:54
// 枚举右端点，在枚举的同时，维护 0 的下标列表 a。
func numberOfSubstrings(s string) (ans int) {
tot1 := 0
a := []int{-1} // 哨兵
for right, b := range s {
if b == '0' {
a = append(a, right)
} else {
ans += right - a[len(a)-1]
tot1++
}
for k := len(a) - 1; k > 0 && (len(a)-k)*(len(a)-k) <= tot1; k-- {
cnt0 := len(a) - k
cnt1 := right - a[k] + 1 - cnt0
ans += max(a[k]-a[k-1]-max(cnt0*cnt0-cnt1, 0), 0)
}
}
return
}
// 枚举左端点
func numberOfSubstrings2(s string) (ans int) {
a := []int{}
for i, b := range s {
if b == '0' {
a = append(a, i)
}
}
n := len(s)
tot1 := n - len(a)
a = append(a, n) // 哨兵
for left, b := range s {
if b == '1' {
ans += a[0] - left // 不含 0 的子串个数
}
for k, j := range a[:len(a)-1] {
cnt0 := k + 1
if cnt0*cnt0 > tot1 {
break
}
cnt1 := j - left - k
ans += max(a[k+1]-j-max(cnt0*cnt0-cnt1, 0), 0)
}
if b == '0' {
a = a[1:] // 这个 0 后面不会再枚举到了
}
}
return
}
java 解法, 执行用时: 92 ms, 内存消耗: 44.3 MB, 提交时间: 2024-07-29 17:47:23
class Solution {
public int numberOfSubstrings(String S) {
char[] s = S.toCharArray();
int n = s.length;
int m = 0;
int[] a = new int[n + 1];
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
a[m++] = i;
}
}
int tot1 = n - m;
a[m] = n; // 哨兵
int ans = 0;
int i = 0; // >= left 的第一个 0 的下标是 a[i]
for (int left = 0; left < n; left++) {
if (s[left] == '1') {
ans += a[i] - left; // 不含 0 的子串个数
}
for (int k = i; k < m; k++) {
int cnt0 = k - i + 1;
if (cnt0 * cnt0 > tot1) {
break;
}
int cnt1 = a[k] - left - (k - i);
ans += Math.max(a[k + 1] - a[k] - Math.max(cnt0 * cnt0 - cnt1, 0), 0);
}
if (s[left] == '0') {
i++; // 这个 0 后面不会再枚举到了
}
}
return ans;
}
// 枚举右端点
public int numberOfSubstrings2(String S) {
char[] s = S.toCharArray();
int ans = 0;
int tot1 = 0;
int[] a = new int[s.length + 1];
a[0] = -1; // 哨兵
int m = 1;
for (int right = 0; right < s.length; right++) {
if (s[right] == '0') {
a[m++] = right;
} else {
ans += right - a[m - 1];
tot1++;
}
for (int k = m - 1; k > 0 && (m - k) * (m - k) <= tot1; k--) {
int cnt0 = m - k;
int cnt1 = right - a[k] + 1 - cnt0;
ans += Math.max(a[k] - a[k - 1] - Math.max(cnt0 * cnt0 - cnt1, 0), 0);
}
}
return ans;
}
}
cpp 解法, 执行用时: 163 ms, 内存消耗: 15.5 MB, 提交时间: 2024-07-29 17:46:31
class Solution {
public:
int numberOfSubstrings(string s) {
int ans = 0, tot1 = 0;
vector<int> a = {-1}; // 哨兵
for (int right = 0; right < s.length(); right++) {
char b = s[right];
if (b == '0') {
a.push_back(right);
} else {
ans += right - a.back();
tot1++;
}
for (int k = a.size() - 1; k && (a.size() - k) * (a.size() - k) <= tot1; k--) {
int cnt0 = a.size() - k;
int cnt1 = right - a[k] + 1 - cnt0;
ans += max(a[k] - a[k - 1] - max(cnt0 * cnt0 - cnt1, 0), 0);
}
}
return ans;
}
// 枚举左端点
int numberOfSubstrings2(string s) {
int n = s.length();
vector<int> a;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
a.push_back(i);
}
}
int tot1 = n - a.size();
a.push_back(n); // 哨兵
int ans = 0, i = 0; // >= left 的第一个 0 的下标是 a[i]
for (int left = 0; left < n; left++) {
if (s[left] == '1') {
ans += a[i] - left; // 不含 0 的子串个数
}
for (int k = i; k < a.size() - 1; k++) {
int cnt0 = k - i + 1;
if (cnt0 * cnt0 > tot1) {
break;
}
int cnt1 = a[k] - left - (k - i);
ans += max(a[k + 1] - a[k] - max(cnt0 * cnt0 - cnt1, 0), 0);
}
if (s[left] == '0') {
i++; // 这个 0 后面不会再枚举到了
}
}
return ans;
}
};
python3 解法, 执行用时: 4471 ms, 内存消耗: 18.2 MB, 提交时间: 2024-07-29 17:45:38
# 枚举子串中的 0 的个数
class Solution:
# 枚举左端点
def numberOfSubstrings1(self, s: str) -> int:
n = len(s)
a = [i for i, b in enumerate(s) if b == '0']
tot1 = n - len(a)
a.append(n) # 哨兵
ans = i = 0 # >= left 的第一个 0 的下标是 a[i]
for left, b in enumerate(s):
if b == '1':
ans += a[i] - left # 不含 0 的子串个数
for k in range(i, len(a) - 1):
cnt0 = k - i + 1
if cnt0 * cnt0 > tot1:
break
cnt1 = a[k] - left - (k - i)
# 可以改成手动比大小，那样更快
ans += max(a[k + 1] - a[k] - max(cnt0 * cnt0 - cnt1, 0), 0)
if b == '0':
i += 1 # 这个 0 后面不会再枚举到了
return ans
# 枚举右端点
def numberOfSubstrings2(self, s: str) -> int:
ans = tot1 = 0
a = [-1] # 哨兵
for right, b in enumerate(s):
if b == '0':
a.append(right)
else:
ans += right - a[-1] # 不含 0 子串的个数
tot1 += 1
for k in range(len(a) - 1, 0, -1):
cnt0 = len(a) - k
if cnt0 * cnt0 > tot1:
break
cnt1 = right - a[k] + 1 - cnt0
# 可以改成手动比大小，那样更快
ans += max(a[k] - a[k - 1] - max(cnt0 * cnt0 - cnt1, 0), 0)
return ans
# 更快写法
def numberOfSubstrings(self, s: str) -> int:
ans = tot1 = 0
a = [-1] # 哨兵
for right, b in enumerate(s):
if b == '0':
a.append(right)
else:
ans += right - a[-1] # 不含 0 子串的个数
tot1 += 1
for k in range(len(a) - 1, 0, -1):
cnt0 = len(a) - k
if cnt0 * cnt0 > tot1:
break
cnt1 = right - a[k] + 1 - cnt0
d = cnt0 * cnt0 - cnt1
if d <= 0:
ans += a[k] - a[k - 1]
elif (res := a[k] - a[k - 1] - d) > 0:
ans += res
return ans