資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中查詢二進位制列表中和為 k 的子列表數量的程式
假設我們有一個包含 0 或 1 的二進位制列表。我們還有一個名為 k 的輸入，我們需要找到和等於 k 的子列表的數量。
因此，如果輸入類似於 nums = [1, 0, 0, 1, 1, 1, 0, 1] k = 3，則輸出將為 8，因為子列表為 [1,0,0,1,1]、[0,0,1,1,1]、[0,0,1,1,1,0]、[0,1,1,1]、[0,1,1,1,0]、[1,1,1]、[1,1,1,0] [1,1,0,1]。
為了解決這個問題，我們將遵循以下步驟 -
- sums := 一個最初包含鍵為 0 值為 1 的對映
- r_sum := 0
- ans := 0
- 對於 nums 中的每個 x，執行
- r_sum := r_sum + x
- ans := ans + (sums[r_sum - k] 如果 (r_sum - k) 存在，否則為 0)
- sums[r_sum] := 1 + (sums[r_sum - k] 如果 (r_sum - k) 存在，否則為 0)
- 返回 ans
示例
讓我們看看以下實現以獲得更好的理解 -
def solve(nums, k):
sums = {0: 1}
r_sum = 0
ans = 0
for x in nums:
r_sum += x
ans += sums.get(r_sum - k, 0)
sums[r_sum] = sums.get(r_sum, 0) + 1
return ans
nums = [1, 0, 0, 1, 1, 1, 0, 1]
k = 3
print(solve(nums, k))輸入
[1, 0, 0, 1, 1, 1, 0, 1], 3
輸出
8
更新於: 2021 年 10 月 16 日
150 次檢視
廣告