670. Maximum Swap
Đề Bài
You are given an integer num. You can swap two digits at most once to get the maximum valued number.
Return the maximum valued number you can get.
Example 1:
Input: num = 2736 Output: 7236 Explanation: Swap the number 2 and the number 7.
Example 2:
Input: num = 9973 Output: 9973 Explanation: No swap.
Constraints:
0 <= num <= 108
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(1)
Lời Giải
C++
0670-maximum-swap.cpp
class Solution {
public:
int maximumSwap(int num) {
string s = to_string(num);
const int n = s.size();
int ans = num;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
swap(s[i], s[j]);
ans = max(ans, stoi(s));
swap(s[i], s[j]);
}
}
return ans;
}
};