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, 108]
Solution #1, 所有上升的数字都有可能被换到前面,拐点之前下降的则不会。找拐点之后最大的往前换,如果有相同的则取index靠后的。
9872345, 2为拐点,987不可能往前换,345则可能往前换
654123439,1为拐点,23439中最大的9可以往前换
class Solution { public int maximumSwap(int num) { char[] A = Integer.toString(num).toCharArray(); int i = 1; for (; i < A.length; i++) { if (A[i] > A[i - 1]) break; } int max = -1; for (; i < A.length; i++) { if (max == -1 || A[max] - '0' <= A[i] - '0') { max = i; } } if (max == -1) return num; for (int j = 0; j < A.length; j++) { if (A[j] < A[max]) { char temp = A[j]; A[j] = A[max]; A[max] = temp; return Integer.valueOf(new String(A)); } } return num; } }
Solution #2, 把0-9每个数的位置预先存上,再从左遍历原数字,如果发现它右方有数字比它大,则进行交换,返回结果
class Solution { public int maximumSwap(int num) { char[] A = Integer.toString(num).toCharArray(); int[] pos = new int[10]; for (int i = 0; i < A.length; i++) { char c = A[i]; pos[c - '0'] = i; } for (int i = 0; i < A.length; i++) { int val = A[i] - '0'; for (int j = 9; j > 0; j--) { if (val >= j) break; if (pos[j] > i) { char temp = A[pos[j]]; A[pos[j]] = A[i]; A[i] = temp; return Integer.valueOf(new String(A)); } } } return num; } }
No comments:
Post a Comment