Code & Fun

第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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maximumSwap(int num) {
vector<int> t;
while(num != 0) {
t.push_back(num % 10);
num /= 10;
}

int k = t.size() - 1;
while(k >= 0) {
auto max = max_element(t.begin(),t.begin() + k + 1);
if (*max != t[k]) {
int a = *max;
*max = t[k];
t[k] = a;
break;
}
k--;
}

for(auto it = t.rbegin();it != t.rend();it++) {
num = 10 * num + *it;
}
return num;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int maximumSwap(int num) {
string numString = to_string(num);
int n = numString.length();
vector<int> dpPosition(n, -1);

int curMaxPos = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (numString[i] > numString[curMaxPos]) {
curMaxPos = i;
}
dpPosition[i] = curMaxPos;
}

for (int i = 0; i < n; i++) {
if(numString[dpPosition[i]] != numString[i]) {
swap(numString[i], numString[dpPosition[i]]);
break;
}
}

return stoi(numString);
}

本文首发于Code & Fun