Code & Func

第75天。

今天的题目是Maximum Swap:

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: 2736 Output: 7236 Explanation: Swap the number 2 and the number 7. Example 2: Input: 9973 Output: 9973 Explanation: No swap. Note: The given number is in the range [0, 10^8]

怎么说呢，写一个不优雅的解法还是挺简单的。

先把num分解成多个digit，然后尝试在找出最大的，如果最大的值和最高位不同，我们就交换，如果相同，我们就找出除去最高位的最大值，直到找不到能交换的，或者交换一次，我们就退出。

然后把digit按照对应的次序还原即可：

1
int maximumSwap(int num) {
2
    vector<int> t;
3
    while(num != 0) {
4
        t.push_back(num % 10);
5
        num /= 10;
6
    }
7

8
    int k = t.size() - 1;
9
    while(k >= 0) {
10
        auto max = max_element(t.begin(),t.begin() + k + 1);
11
        if (*max != t[k]) {
12
            int a = *max;
13
            *max = t[k];
14
            t[k] = a;
15
            break;
9 collapsed lines
16
        }
17
        k--;
18
    }
19

20
    for(auto it = t.rbegin();it != t.rend();it++) {
21
        num = 10 * num + *it;
22
    }
23
    return num;
24
}

然后是dicuss中的解法,好像想法差不多。

1
int maximumSwap(int num) {
2
    string numString = to_string(num);
3
    int n = numString.length();
4
    vector<int> dpPosition(n, -1);
5

6
    int curMaxPos = n - 1;
7
    for (int i = n - 1; i >= 0; i--) {
8
        if (numString[i] > numString[curMaxPos]) {
9
            curMaxPos = i;
10
        }
11
        dpPosition[i] = curMaxPos;
12
    }
13

14
    for (int i = 0; i < n; i++) {
15
        if(numString[dpPosition[i]] != numString[i]) {
7 collapsed lines
16
            swap(numString[i], numString[dpPosition[i]]);
17
            break;
18
        }
19
    }
20

21
    return stoi(numString);
22
}