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:
- The given number is in the range [0, 108]
解法：从后向前扫，遇到比max_value 大的就记录这个最大数的值和位置，继续向前扫，遇到小于这个max_value时，就记录这个交换位置， 因为越往左扫数位越高，交换后整个数字值越大。
Java:
class Solution { public int maximumSwap(int num) { char[] digits = Integer.toString(num).toCharArray(); int[] buckets = new int[10]; for (int i = 0; i < digits.length; i++) { buckets[digits[i] - '0'] = i; } for (int i = 0; i < digits.length; i++) { for (int k = 9; k > digits[i] - '0'; k--) { if (buckets[k] > i) { char tmp = digits[i]; digits[i] = digits[buckets[k]]; digits[buckets[k]] = tmp; return Integer.valueOf(new String(digits)); } } } return num; }} Python:
class Solution(object): def maximumSwap(self, num): """ :type num: int :rtype: int """ digits = list(str(num)) left, right = 0, 0 max_idx = len(digits)-1 for i in reversed(xrange(len(digits))): if digits[i] > digits[max_idx]: max_idx = i elif digits[max_idx] > digits[i]: left, right = i, max_idx digits[left], digits[right] = digits[right], digits[left] return int("".join(digits)) Python:
def maximumSwap(self, num): A = list(str(num)) ans = A[:] for i in xrange(len(A)): for j in xrange(i+1, len(A)): A[i], A[j] = A[j], A[i] if A > ans: ans = A[:] A[i], A[j] = A[j], A[i] return int("".join(ans)) Python:
def maximumSwap(self, num): A = map(int, str(num)) last = {x: i for i, x in enumerate(A)} for i, x in enumerate(A): for d in xrange(9, x, -1): if last.get(d, None) > i: A[i], A[last[d]] = A[last[d]], A[i] return int("".join(map(str, A))) return num Python: wo
class Solution(): def maxSwap(self, num): s = list(str(num)) i = 0 while i < len(s): j = i + 1 swap = i mx = s[i] while j < len(s): if s[j] > mx: mx = s[j] swap = j j += 1 if swap != i: s[i], s[swap] = s[swap], s[i] break i += 1 return int(''.join(s)) C++:
class Solution {public: int maximumSwap(int num) { string digits = to_string(num); int left = 0, right = 0; int max_idx = digits.length() - 1; for (int i = digits.length() - 1; i >= 0; --i) { if (digits[i] > digits[max_idx]) { max_idx = i; } else if (digits[max_idx] > digits[i]) { left = i; right = max_idx; } } swap(digits[left], digits[right]); return stoi(digits); }}; C++:
int maximumSwap(int num) { string numstr = std::to_string(num); int maxidx = -1; int maxdigit = -1; int leftidx = -1; int rightidx = -1; for (int i = numstr.size() - 1; i >= 0; --i) { // current digit is the largest by far if (numstr[i] > maxdigit) { maxdigit = numstr[i]; maxidx = i; continue; } // best candidate for max swap if there is no more // such situation on the left side if (numstr[i] < maxdigit) { leftidx = i; rightidx = maxidx; } } // num is already in order if (leftidx == -1) return num; std::swap(numstr[leftidx], numstr[rightidx]); return std::stoi(numstr); }
类似题目：
Create Maximum Number