資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：使總和可被P整除
假設我們有一個數組nums和另一個值p，我們刪除最小的子陣列（不是整個陣列），使得剩餘值的總和可以被p整除。我們需要找到需要刪除的最小子陣列的長度，如果沒有這樣的子陣列，則返回-1。
因此，如果輸入類似於nums = [8,2,6,5,3] p = 7，則輸出將為1，因為如果我們刪除3，則總和將為21，並且可以被7整除。
為了解決這個問題，我們將遵循以下步驟：
- ans := 無限大
- s := (nums中所有元素的和) mod p
- d := 一個包含鍵值對{0: -1}的對映
- cum := 0
- 如果s等於0，則
- 返回0
- 對於i從0到nums的大小，執行以下操作：
- cum := cum + nums[i]
- r := cum mod p
- 如果(r-s)mod p存在於d中，則
- ans := ans和i - d[(r-s) mod p]的最小值
- d[r] := i
- 如果ans < nums的大小，則返回ans，否則返回-1
示例
讓我們看看以下實現以獲得更好的理解：
def solve(nums, p):
ans = float("inf")
s = sum(nums) % p
d = {0:-1}
cum = 0
if s == 0:
return 0
for i in range(len(nums)):
cum+=nums[i]
r = cum%p
if (r-s)%p in d:
ans = min(ans, i-d[(r-s)%p])
d[r] = i
return ans if ans<len(nums) else -1
nums = [8,2,6,5,3]
p = 7
print(solve(nums, p))輸入
[8,2,6,5,3], 7
輸出
1
更新於: 2021年10月4日
325 次瀏覽
廣告