資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢給定字串數字的所有子字串的總和
假設我們有一個字串格式的數字，我們需要找到字串 s 的所有子字串的總和。答案可能非常大，因此返回結果模 10^9+7。
所以，如果輸入類似 s = "268"，那麼輸出將是 378，因為子字串是 "2"、"6"、"8"、"26"、"68" 和 "268"，總和是 378。
為了解決這個問題，我們將遵循以下步驟：
- M := 10^9 + 7
- sum_val := 0
- B := 1
- res := 0
- 對於 i 從 s 的大小 - 1 到 0，遞減 1，執行：
- res :=(res + s[i] 的數字值 * B *(i + 1)) mod M
- sum_val := sum_val - s[i] 的數字值
- B := (B * 10 + 1) mod M
- 返回 res
示例
讓我們看看下面的實現來更好地理解：
def solve(s): M = 10 ** 9 + 7 sum_val = 0 B = 1 res = 0 for i in range(len(s) - 1, -1, -1): res = (res + int(s[i]) * B * (i + 1)) % M sum_val -= int(s[i]) B = (B * 10 + 1) % M return res s = "268" print(solve(s))
輸入
"268"
輸出
378
更新於: 2021年10月7日
395 次瀏覽
廣告