class Solution {
public:
int numSub(string s) {
}
};
1513. 仅含 1 的子串数
给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。
返回所有字符都为 1 的子字符串的数目。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
示例 1：
输入：s = "0110111" 输出：9 解释：共有 9 个子字符串仅由 '1' 组成 "1" -> 5 次 "11" -> 3 次 "111" -> 1 次
示例 2：
输入：s = "101" 输出：2 解释：子字符串 "1" 在 s 中共出现 2 次
示例 3：
输入：s = "111111" 输出：21 解释：每个子字符串都仅由 '1' 组成
示例 4：
输入：s = "000" 输出：0
提示：
s[i] == '0' 或 s[i] == '1'1 <= s.length <= 10^5原站题解
cpp 解法, 执行用时: 4 ms, 内存消耗: 9 MB, 提交时间: 2023-09-14 15:08:33
// 寻找每一段只有1的串，等差数列求和
class Solution {
public:
static constexpr int P = int(1E9) + 7;
int numSub(string s) {
int p = 0;
long long ans = 0;
while (p < s.size()) {
if (s[p] == '0') {
++p;
continue;
}
int cnt = 0;
while (p < s.size() && s[p] == '1') {
++cnt;
++p;
}
ans = ans + (1LL + (long long)cnt) * cnt / 2;
ans = ans % P;
}
return ans;
}
};
java 解法, 执行用时: 6 ms, 内存消耗: 42.3 MB, 提交时间: 2023-09-14 15:07:40
class Solution {
public int numSub(String s) {
final int MODULO = 1000000007;
long total = 0;
int length = s.length();
long consecutive = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == '0') {
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
consecutive = 0;
} else {
consecutive++;
}
}
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
return (int) total;
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.6 MB, 提交时间: 2023-09-14 15:07:09
const mod = 1000000007
func numSub(s string) int {
sum, count := 0, 0
for i := 0; i < len(s); i++ {
if s[i] == '1' {
count++
} else {
sum = (sum + (count+1)*count/2) % mod
count = 0
}
}
if count != 0 { // 这里注意一下，如果是‘1’结尾的字符串，最后count不为零，需要再算一次
sum = (sum + (count+1)*count/2) % mod
}
return sum
}
python3 解法, 执行用时: 72 ms, 内存消耗: 16.5 MB, 提交时间: 2023-09-14 15:06:52
class Solution:
def numSub(self, s: str) -> int:
total, consecutive = 0, 0
length = len(s)
for i in range(length):
if s[i] == '0':
total += consecutive * (consecutive + 1) // 2
consecutive = 0
else:
consecutive += 1
total += consecutive * (consecutive + 1) // 2
total %= (10**9 + 7)
return total
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-14 15:05:30
static MOD: i32 = 1000000007;
impl Solution {
pub fn num_sub(s: String) -> i32 {
let mut cnt = 0;
s.into_bytes().into_iter().fold(0, |ans, c| {
if c == b'0' {cnt = 0; ans}
else {
cnt += 1;
(ans + cnt) % MOD
}
})
}
}