資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢和至少為目標值的最小子列表的大小
假設我們有一個名為 nums 的數字列表，以及另一個名為 target 的輸入，我們需要找到最短子列表的大小，使得其總和等於或大於 target。如果不存在這樣的子列表，則返回 -1。
因此，如果輸入類似於 nums = [2, 11, -4, 17, 4] target = 19，則輸出將為 2，因為我們可以選擇 [17, 4] 使得總和至少為 19。
為了解決這個問題，我們將遵循以下步驟：
ps := 一個僅包含一個元素 0 的列表
對於 nums 中的每個數字 num，執行以下操作：
在 ps 後插入 (ps 的最後一個元素 + num)
如果 num >= target，則
返回 1
min_size := 無窮大
q := [0]
j := 0
對於範圍從 1 到 ps 大小的 i，執行以下操作：
j := j 和 q 大小 - 1 的最小值
當 j < q 大小 且 ps[i] - ps[q[j]] >= target 時，執行以下操作：
min_size := min_size 和 (i - q[j]) 的最小值
j := j + 1
當 q 不為空 且 ps[i] <= ps[q 的最後一個元素] 時，執行以下操作：
從 q 中刪除最後一個元素
在 q 的末尾插入 i
如果 min_size < 無窮大，則返回 min_size，否則返回 -1
示例
讓我們檢視以下實現以更好地理解：
class Solution:
def solve(self, nums, target):
ps = [0]
for num in nums:
ps += [ps[-1] + num]
if num >= target:
return 1
min_size = float("inf")
q = [0]
j = 0
for i in range(1, len(ps)):
j = min(j, len(q) - 1)
while j < len(q) and ps[i] - ps[q[j]] >= target:
min_size = min(min_size, i - q[j])
j += 1
while q and ps[i] <= ps[q[-1]]:
q.pop()
q.append(i)
return min_size if min_size < float("inf") else -1
ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target))輸入
[2, 11, -4, 17, 4], 19
輸出
2
更新於： 2020-12-23
149 次瀏覽
廣告