資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢可刪除的最小子列表的長度，以使列表和能被k整除
假設我們有一個包含正值的列表，稱為nums，還有一個正數k。我們需要找到可以從nums中刪除的最短子列表（可以為空）的長度，使得剩餘元素的和能被k整除。但是我們不能刪除整個列表。如果沒有這樣的子列表可以刪除，則返回-1。
因此，如果輸入類似於nums = [5,8,6,3] k = 8，則輸出將為1，因為[5,8,6,3]的元素的當前和為22。如果我們刪除長度為1的子列表[6]，則和為16，它可以被8整除。
為了解決這個問題，我們將遵循以下步驟：
- rem := (nums中所有元素的和 + k) mod k
- 如果rem等於0，則
- 返回0
- n := nums的大小
- presum := 0
- mp := 一個字典，最初為鍵0儲存-1
- res := n
- 對於i從0到n - 1，執行以下操作：
- presum := presum + nums[i]
- m :=(presum + k) mod k
- mp[m] := i
- 如果(m - rem + k) mod k存在於mp中，則
- res := res和(i - mp[(m - rem + k) mod k])的最小值
- 如果res不等於n，則返回res，否則返回-1
示例
讓我們看看以下實現以獲得更好的理解：
def solve(nums, k):
rem = (sum(nums) + k) % k
if rem == 0:
return 0
n, presum = len(nums), 0
mp = {0: -1}
res = n
for i in range(n):
presum += nums[i]
m = (presum + k) % k
mp[m] = i
if (m - rem + k) % k in mp:
res = min(res, i - mp[(m - rem + k) % k])
return res if res != n else -1
nums = [5,8,6,3]
k = 8
print(solve(nums, k))輸入
[5,8,6,3], 8
輸出
1
更新於： 2021年10月18日
155 次瀏覽
廣告