Python程序：查找仅包含1的子字符串个数

假设我们有一个二进制字符串s。我们需要找到所有字符都是'1'的子字符串的个数。答案可能非常大，因此返回结果模10^9 + 7。

因此，如果输入类似于s = "1011010"，则输出为5，因为1. 四个"1" 2. 一个"11"

为了解决这个问题，我们将遵循以下步骤：

• m := 10^9+7

• result := 0

• div := 使用'0'分割二进制字符串

• 对于div中的每个x：

  • 如果x为空，则跳过本次迭代

  • result := result + (x的长度 * (x的长度 + 1)) / 2 的商

• 返回 result mod m

让我们来看下面的实现，以便更好地理解：

示例

 在线演示

def solve(s):
   m = 10**9+7
   result = 0
   for x in s.split('0'):
      if not x: continue
      result += (len(x)*(len(x)+1)) // 2
   return result % m
s = "1011010"
print(solve(s))

输入

"1011010"

输出

5

Arnab Chakraborty

更新于：2021年5月29日

129 次浏览

启动您的职业生涯

完成课程获得认证

开始学习