Chương trình tìm số nguyên nhỏ nhất sau tối đa k lần hoán đổi chữ số kề nhau trong Python

Cho chuỗi num biểu diễn một số nguyên rất lớn và giá trị k. Ta có thể hoán đổi hai chữ số kề nhau tối đa k lần. Yêu cầu tìm giá trị nhỏ nhất có thể đạt được.

Ví dụ: num = "5432", k = 4 → kết quả 2453 (5432 → 4532 → 4523 → 4253 → 2453).

Giải thuật

1. min_num := sắp xếp các chữ số của num theo thứ tự tăng dần.
2. Khởi tạo i := 0, to_find := 0.
3. Trong khi num != min_num và k > 0 và i < len(num):
   • Tìm chỉ số indx của chữ số to_find trong num từ vị trí i.
   • Trong khi indx != -1:
     • Nếu indx - i <= k:
       • Di chuyển chữ số tại indx về vị trí i (dịch các phần tử giữa).
       • Cập nhật k := k - (indx - i), i := i + 1, to_find := 0.
       • Tiếp tục tìm to_find từ vị trí i mới.
     • Ngược lại: thoát vòng lặp trong.
   • to_find := to_find + 1.
4. Trả về num.

Ví dụ minh họa

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

Đầu vào

"5432", 4

Đầu ra

2453