在Python中查找K个连续的1的最小相邻交换次数的程序

假设我们有一个二进制数组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]。

为了解决这个问题，我们将按照以下步骤进行 −

j：= 0
val：= 0
ans：= 999999
loc：=新列表
对于nums中的每个索引i和值x，执行以下操作
- 如果x是非零的，那么
  - 在loc的末尾插入i
  - m：=（j+loc大小-1）/ 2的商
  - val：= val + loc [-1] – loc [m] -（loc大小-j）/ 2的商
  - 如果loc的长度 – j> k，则
  - m：=（j+loc大小）/ 2的商
  - val：= val-loc [m] – loc [j] -（loc大小-j）/ 2的商
  - j：= j +1
  - 如果loc大小-j与k相同，则
  - ans：= ans和val的最小值
返回ans

示例

让我们看一下以下实现，以获得更好的理解

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))