Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

Input: 2736Output: 7236Explanation: Swap the number 2 and the number 7.

 

Example 2:

Input: 9973Output: 9973Explanation: No swap.

 

Note:

1. The given number is in the range [0, 10⁸]

思路：

暴力枚举所有交换可能，竟然没有超时。。。感觉因为输入最多到10⁸

最多8位，复杂度O(n³)虽然很高，但数据规模小，但总之不是什么好办法。

vector
           
             digits(int num){    if (num == 0)return{
         0};    vector
            
              ret;        while (num > 0)    {        ret.push_back(num % 10);        num /= 10;    }    reverse(ret.begin(), ret.end());    return ret;}int toNum(vector
             
              num){    int r = 0;    for (int i = 0; i < num.size();i++)    {        r *= 10;        r += num[i];    }    return r;}int maximumSwap(int n){    vector
              
                num = digits(n);    int m = n;    for (int i = 0; i < num.size();i++)    {        for (int j = i + 1; j < num.size();j++)        {            swap(num[i], num[j]);            m = max(m, toNum(num));            swap(num[i], num[j]);        }    }    return m;}