670. Maximum Swap

Problem

Bài toán yêu cầu bạn tìm số lớn nhất có thể thu được bằng cách hoán đổi đúng một cặp chữ số trong một số nguyên không âm. Nếu không có hoán đổi nào làm tăng giá trị, return về số ban đầu

Approach

Chuyển số thành mảng các chữ số để dễ thao tác

Với mỗi vị trí, kiểm tra xem có chữ số lớn hơn ở bên phải không (ưu tiên chữ số lớn nhất và ở vị trí xa nhất bên phải)

Nếu có, hoán đổi và return về kết quả. Nếu không, return về số ban đầu

Để tối ưu, ta có thể duyệt từ phải → trái đẻ ghi nhớ vị trí xuất hiện cuối cùng của từng chữ số (0→9), rồi duyệt từ trái → phải để tìm vị trí swap tối ưu

Time and space complexity

TC: O(n), với n là số lượng chữ số num

SC: O(1): Mảng last có 10 elements

Solution

typescripttypescript

1function maximumSwap(num: number): number {
2    const digits = num.toString().split('').map(Number);
3    const last = new Array(10).fill(-1);
4    for (let i = 0; i < digits.length; i++) {
5        last[digits[i]] = i;
6    }
7    for (let i = 0; i < digits.length; i++) {
8        for (let d = 9; d > digits[i]; d--) {
9            if (last[d] > i) {
10                [digits[i], digits[last[d]]] = [digits[last[d]], digits[i]]
11                return parseInt(digits.join(''), 10)
12            }
13        }
14    }
15    return num
16};

💡

Giải thích code

last lưu vị trí cuối cùng xuất hiện của mỗi chữ số 0 → 9

Với mỗi chữ số từ trái → phải, tìm chữ số lớn nhất lớn hơn nó và nằm bên phải nó để swap

Chỉ cần thực hiện đúng một lần swap đầu tiên tìm được, vì swap này sẽ cho kết quả lớn nhất

Nếu không tìm thấy swap nào cải thiện, return về số ban đầu

Ví dụ minh họa

Input: 2736

Chuyển thành [2][7][3][6]

Swap 2 với 7 → [7][2][3][6] → Output: 7236

Input: 9973

Chuyển thành [9][9][7][3]

Không có swap nào tạo số lớn hơn → Output: 9973

Loading content...

1function maximumSwap(num: number): number { 2 const digits = num.toString().split('').map(Number); 3 const last = new Array(10).fill(-1); 4 for (let i = 0; i < digits.length; i++) { 5 last[digits[i]] = i; 6 } 7 for (let i = 0; i < digits.length; i++) { 8 for (let d = 9; d > digits[i]; d--) { 9 if (last[d] > i) { 10 [digits[i], digits[last[d]]] = [digits[last[d]], digits[i]] 11 return parseInt(digits.join(''), 10) 12 } 13 } 14 } 15 return num 16};

670. Maximum Swap

Related Posts

Related Posts

670. Maximum Swap

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists