仅含 1 的子串数
难度:
标签:
题目描述
代码结果
运行时间: 40 ms, 内存: 16.8 MB
/*
* 思路:
* 使用 Java Stream 的方式进行解答。首先将字符串按 '0' 分割为子字符串。
* 然后对于每一个子字符串计算其长度,使用 n * (n + 1) / 2 计算可能的
* 子字符串数量。
*/
import java.util.Arrays;
public class Solution {
public int numSub(String s) {
int mod = 1000000007;
return Arrays.stream(s.split("0"))
.mapToInt(str -> str.length() * (str.length() + 1) / 2)
.reduce(0, (a, b) -> (a + b) % mod);
}
}
解释
方法:
解题思路是首先使用字符串的split方法,以'0'为分隔符把字符串s分割成若干部分,这些部分都是连续的'1'的字符串。对于每个连续的'1'字符串,计算其可能生成的所有子字符串的数量。这可以通过数学公式来计算,对于长度为n的字符串,其子字符串数量是(1 + n) * n / 2。这是因为可以选择1个1、2个1直到n个1,每种长度的子字符串的数量分别是n, n-1, ..., 1。对于每一部分直接计算并累加至结果中。由于结果可能很大,每次累加后对10^9 + 7取模以防止整数溢出。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在计算子字符串的总数时使用了组合数学中的公式 '(1 + n) * n / 2'?
▷🦆
split方法将字符串分割为连续的'1'组成的子串列表时,空字符串如何处理,它们对最终结果有什么影响?
▷🦆
结果每次累加后为何要对10^9 + 7取模,这个数有什么特别的意义吗?
▷🦆
在实际的代码实现中,如何保证在对每个子串长度计算子字符串数量时不会出现整数溢出?
▷