难度: Medium
给你一个二进制字符串 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运行时间: 40 ms
内存: 16.8 MB
class Solution:
def numSub(self, s: str) -> int:
li=s.split('0')
res=0
for i in li:
if i!='':
res+=(1+len(i))*(len(i))//2
res=res%(pow(10,9)+7)
return res
解题思路是首先使用字符串的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)
class Solution:
def numSub(self, s: str) -> int:
li = s.split('0') # 以'0'为分隔符分割字符串，得到所有连续的'1'组成的子串列表
res = 0
for i in li:
if i != '':
res += (1 + len(i)) * len(i) // 2 # 使用组合数学公式计算连续1的子串数
res = res % (pow(10, 9) + 7) # 取模操作，保证结果不会溢出
return res # 返回计算的子串数
这个公式用于计算长度为n的连续字符串中所有可能的子字符串的数量。对于一个长度为n的字符串，我们可以选择任意起点和终点来形成一个子字符串，因此长度为1的子字符串有n个，长度为2的子字符串有n-1个，依此类推，直到长度为n的子字符串有1个。这样，总的子字符串数量就是n + (n-1) + (n-2) + ... + 1，这是一个等差数列的求和公式，其和为(1 + n) * n / 2。
在使用split方法以'0'为分隔符分割字符串时，如果'0'出现在字符串的开始或结束，或者连续出现多个'0'，则会在结果数组中产生空字符串。这些空字符串实际上代表了没有'1'的序列，因此它们不包含任何子字符串。在计算子字符串的总数时，空字符串被忽略，因为它们的长度为0，不会对总数产生任何贡献。
10^9 + 7是一个非常大的素数，常在计算机编程竞赛中用于模运算以防止整数溢出，并保证结果的稳定性。对结果进行模10^9 + 7的操作能够确保即使结果非常大也不会超过编程语言处理整数的常规范围，同时利用模运算的性质保证每步操作后的结果仍然正确。此外，对大素数取模是防止潜在的散列碰撞，提高计算效率的一种常用方法。
在实际的代码实现中，为了避免在计算子字符串数量时出现整数溢出，我们使用了模运算。由于每次计算完子字符串数量后都立即对10^9 + 7取模，因此即使中间步骤的值非常大，取模操作也会将其缩减到一个安全的范围内。此外，使用的是整数除法，确保每步计算都是安全的整数运算。