假設我們有一個陣列 [5, 4, -2, 4, -3] 并且我們希望所有元素都等于 0。子陣列可用于加或減 1。例如，我可以從索引 0 開始加 1到 3，然后串列是 [5 1, 4 1, -2 1, 4 1, -3 1]。這算一個動作。如何盡量減少移動次數？我的方法雖然可能很慢，但它是遍歷串列，如果一個數字是正數，則繼續向右擴展，直到達到 0 或負數。反之亦然。然后，如果該視窗大于 0，則將該范圍內的所有數字減去迄今為止的最小值。否則，如果該視窗小于 0，則到目前為止通過 abs(minimum) 添加該范圍內的所有數字。例如：
[5, 4, -2, -5, -3]
5 is start, 4 is end since we reach end of positives. Minimum so far is 4.
[5 - 4, 4 - 4, -2, -5, -3] = [1, 0, -2, -5, -3]
[1, 0, -2, 4, -3] 1 is start, 1 is end. minimum so far is 1.
[1 - 1, 0, -2, -5, -3] = [0, 0, -2, -5, -3]
We go to 0, but we skip it
[0, 0, -2, -5, -3] -2 is start, -3 is end. abs(-2) is minimum so far
[0, 0, 0, -3, -1] -3 is start, -1 is end. abs(-1) is minimum so far
[0, 0, 0, -3 1, -1 1] = [0, 0, 0, -2, 0]
[0, 0, 0, -2, 0] -2 is start, -2 is end. abs(-2) is minimum so far
[0, 0, 0, -2 2, 0] = [0, 0, 0, 0, 0]
總共需要 4 1 abs(-2) abs(-1) abs(-2) 移動。
有沒有更高效的演算法？另外，我的方法正確嗎？
uj5u.com熱心網友回復：
您對演算法的描述似乎朝著正確的方向發展，但并不完整，因此很難確定它是否正確。
您可以通過將串列分成連續的正值、負值和零值組來解決此問題。對于每個組，您可以通過對應于最小絕對值的數量使整個子范圍的所有數字更接近于零。這將為您留下一組新的組，您可以在這些組上重復該程序，直到所有元素都為零。
from itertools import groupby
def incdec(A):
count = 0
while any(A):
groups = (list(g) for _,g in groupby(A,lambda n:(n>0)-(n<0)))
A = []
for group in groups:
moves = min(group,key=abs)
count = abs(moves)
A.extend(n-moves for n in group)
return count
輸出：
print(incdec([5, 4, -2, -5, -3])) # 10
print(incdec([5, 4, -2, 4, -3])) # 14
print(incdec([5, 3, 4, 2, 3, 0, 1, 1 , -2, -4, -3])) # 12
# sample process expansion:
#
# [5, 3, 4, 2, 3, 0, 1, 1 , -2, -4, -3]
# [5, 3, 4, 2, 3], [0], [1, 1],[-2, -4, -3]
# -2 -1 2 5 moves
# [3, 1, 2, 0, 1, 0, 0, 0 , 0, -2, -1]
# [3, 1, 2], [0], [1], [0, 0, 0 , 0], [-2, -1]
# -1 -1 1 3 moves
# [2, 0, 1, 0, 0, 0, 0, 0 , 0, -1, 0]
# [2], [0], [1], [0, 0, 0, 0, 0 , 0], [-1], [0]
# -2 -1 1 4 moves
# ---------
# 12 moves
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/388159.html
上一篇：查找網格捕獲的“水”量