在 Python 中找到 K 个连续交换的最小相邻交换的程序
假设我们有一个二进制数组nums和一个值k。一步，我们可以选择两个相邻的索引并交换它们的值。我们必须找到所需的最小移动次数，以便nums有k个连续的1。
因此，如果输入类似于nums=[1,0,0,1,0,1,0,1],k=3，那么输出将为2，因为在一次交换中我们可以从[1,0,0,1,0,1,0,1]到[1,0,0,0,1,1,0,1]，然后[1,0,0,0,1,1,1,0].
示例
让我们看下面的实现来更好地理解
def solve(nums, k):
j = val = 0
ans = 999999
loc = []
for i, x in enumerate(nums):
if x:
loc.append(i)
m = (j + len(loc) - 1)//2
val += loc[-1] - loc[m] - (len(loc)-j)//2
if len(loc) - j > k:
m = (j + len(loc))//2
val -= loc[m] - loc[j] - (len(loc)-j)//2
j += 1
if len(loc)-j == k:
ans = min(ans, val)
return ans
nums = [1,0,0,1,0,1,0,1]
k = 3
print(solve(nums, k))输入
[1,0,0,1,0,1,0,1], 3输出结果
2