PythonでK個の連続するスワップの最小隣接スワップを見つけるプログラム

1つのバイナリ配列numsと値kがあるとします。 1回の移動で、2つの隣接するインデックスを選択し、それらの値を交換できます。 numsがk個の連続した1になるように、必要な最小移動数を見つける必要があります。

したがって、入力がnums =[1,0,0,1,0,1,0,1]、k =3の場合、1回のスワップで[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：=新しいリスト

• インデックスiごとに、値xをnumsで、実行します

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

入力

[1,0,0,1,0,1,0,1], 3

出力

2