Số lớn nhất bằng 1 lần hoán vị chữ số C++

Cho số N. Hoán vị 1 cặp chữ số để được số lớn nhất có thể.

Thuật toán

• Duyệt từ phải sang trái, giữ maxDigit và maxIdx.
• Nếu s[i] < maxDigit: ghi nhớ swapL = i, swapR = maxIdx.
• Cuối cùng swap swapL và swapR (nếu có).

Đảm bảo swap chữ số nhỏ nhất có thể (bên trái) với chữ số lớn nhất bên phải.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

int largestOneSwap(int n) {
    string s = to_string(n);
    int maxD = -1, maxI = -1, swapL = -1, swapR = -1;
    for (int i = s.size()-1; i >= 0; i--) {
        if (s[i] > maxD) { maxD = s[i]; maxI = i; }
        else if (s[i] < maxD) { swapL = i; swapR = maxI; }
    }
    if (swapL != -1) swap(s[swapL], s[swapR]);
    return stoi(s);
}

int main() {
    cout << largestOneSwap(678) << endl; // 876
    return 0;
}

Kết quả

876