Pythonの数字で最大k個の隣接するスワップの後に可能な最小の整数を見つけるプログラム

非常に大きな整数を表すnumという文字列があり、別の値kもあるとします。値の隣接する2桁は、最大でk回交換できます。取得できる最小値を見つける必要があります。

したがって、入力がnum ="5432" k =4の場合、最初の数値は5432であるため、出力は2453になります。最初のフェーズの後は4532、次に4523、次に4253、最後のフェーズは2453になります。

これを解決するために、次の手順に従います

• min_num：=numの数字を並べ替える

• i：=0、to_find：=0

• numはmin_numと同じではなく、k>0およびi

  • indx：=numのインデックスiからのアイテムto_findのインデックス

  • indxは-1と同じではありませんが、実行してください

    • indx --i <=kの場合、

      • num：=num[インデックス0からi-1へ]連結num[indx]concatenatenum[インデックスiからindx-1へ]連結num[インデックスindx+1から終了まで]

      • k：=k-（indx --i）

      • i：=i + 1

      • to_find：=0

      • indx：=numのインデックスiからのアイテムto_findのインデックス

    • それ以外の場合

      • ループから出てきます

  • to_find：=to_find + 1

• numを返す

例

理解を深めるために、次の実装を見てみましょう

def solve(num, k):
   min_num = sorted(list(num))
   min_num = ''.join(min_num)
   i = 0
   to_find = 0
   while num != min_num and k > 0 and i < len(num):
      indx = num.find(str(to_find), i)
      while indx != -1:
         if indx - i <= k:
            num = num[:i] + num[indx] + num[i:indx] + num[indx+1:]
            k -= (indx - i)
            i += 1
            to_find = 0
            indx = num.find(str(to_find), i)
         else:
            break
      to_find += 1
   return num

num = "5432"
k = 4
print(solve(num, k))

入力

"5432", 4

出力

2453