LeetCode 筆記 - 1513. Number of Substrings With Only 1s

Posted on

題目在此 1513. Number of Substrings With Only 1s

給定一個字串，請問連續字串中由 1 組成的連續字元的子字串有幾個？
因為最後答案可能會很大，所以請回傳答案 mod 10^9 + 7。

解題思維

這題就是計算出 1 的個數，然後套公式就好了。
公式就是簡單的梯形公式 n * (n + 1) // 2。image 106

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def numSub(self, s: str) -> int:

        if (size := len(s)) == 1:
            return 1
        modulo = 10 ** 9 + 7
        result = 0

        list_1 = s.split('0')

        for sub_1 in list_1:
            n = len(sub_1)
            result += (n + 1) * n // 2
        

        return result % modulo
image 106

也許你也會想看看