資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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次瀏覽
廣告