Hoán đổi tối đa (Maximum Swap) trong Python

Giả sử chúng ta có một số nguyên không âm; chúng ta có thể hoán đổi hai chữ số tối đa một lần để đạt được số có giá trị lớn nhất. Chúng ta phải trả về số lớn nhất có thể đạt được. Ví dụ, nếu đầu vào là 2736, kết quả sẽ là 7236 (hoán đổi 2 và 7).

Để giải quyết, thực hiện các bước sau:

• num := tách từng chữ số của số, tạo thành list
• num1 := sắp xếp num theo thứ tự giảm dần
• index := 0
• Khi index < độ dài num:
  • Nếu num1[index] khác num[index]:
    • a := mảng con của num từ index+1 đến cuối
    • Đảo ngược a
    • a := độ dài a - chỉ số của num1[index] trong a + index + 1 - 1
    • Hoán đổi num[index] và num[a]
    • Thoát vòng lặp
  • Tăng index lên 1
• Ghép các số trong num thành số nguyên
• Trả về kết quả

Ví dụ (Python)

class Solution:
    def maximumSwap(self, num):
        num = list(map(int, list(str(num))))
        num1 = sorted(num, reverse=True)
        index = 0
        while index < len(num):
            if num1[index] != num[index]:
                a = num[index + 1:]
                a.reverse()
                a = len(a) - a.index(num1[index]) + index + 1 - 1
                num[index], num[a] = num[a], num[index]
                break
            index += 1
        return int("".join(str(x) for x in num))

ob1 = Solution()
print(ob1.maximumSwap(5397))

Đầu vào

5397

Kết quả

9357