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

更新於：2021年5月29日

129 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告