Python程式：在最多k次相鄰交換數字後找到可能的最小整數

假設我們有一個名為num的字串，表示一個非常大的整數，還有一個值k。我們可以交換該值中任何兩個相鄰的數字，最多交換k次。我們必須找到我們可以得到的最小值。

因此，如果輸入類似於num = "5432" k = 4，則輸出將為2453，因為一開始數字是5432。然後在第一階段它將變為4532，然後4523，然後4253，最後階段為2453。

為了解決這個問題，我們將遵循以下步驟

  • min_num := 對num的數字進行排序

  • i := 0，to_find := 0

  • 當num與min_num不同且k > 0且i < num的大小，執行以下操作

    • indx := 從num中索引i開始查詢to_find的索引

    • 當indx與-1不同，執行以下操作

      • 如果indx - i <= k，則

        • num := num[從索引0到i-1]連線num[indx]連線num[從索引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

更新於: 2021年10月6日

140次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告