diff options
-rw-r--r-- | maximum_swap.c | 39 | ||||
-rw-r--r-- | maximum_swap.py | 30 |
2 files changed, 69 insertions, 0 deletions
diff --git a/maximum_swap.c b/maximum_swap.c new file mode 100644 index 0000000..ba91371 --- /dev/null +++ b/maximum_swap.c @@ -0,0 +1,39 @@ +// 670. Maximum Swap +#include "leetcode.h" + +/* + * 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. + */ + +int maximumSwap(int num) { + int digits[9] = {0}, idx = 8; + while (num) { + digits[idx--] = num % 10; + num /= 10; + } + idx++; + for (int i = idx; i < 9; i++) { + int max_idx = i; + for (int j = i + 1; j < 9; j++) + if (digits[j] >= digits[max_idx]) + max_idx = j; + if (digits[i] < digits[max_idx]) { + digits[i] ^= digits[max_idx]; + digits[max_idx] ^= digits[i]; + digits[i] ^= digits[max_idx]; + break; + } + } + num = 0; + for (; idx < 9; idx++) { + num *= 10; + num += digits[idx]; + } + return num; +} + +int main() { + printf("%d\n", maximumSwap(2736)); // expect: 7236 + printf("%d\n", maximumSwap(9973)); // expect: 9973 +} diff --git a/maximum_swap.py b/maximum_swap.py new file mode 100644 index 0000000..ce384c1 --- /dev/null +++ b/maximum_swap.py @@ -0,0 +1,30 @@ +# 670. Maximum Swap + +""" +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. +""" + + +class Solution(object): + def maximumSwap(self, num): + """ + :type num: int + :rtype: int + """ + num = [int(x) for x in str(num)] + max_idx, xi, yi = len(num) - 1, 0, 0 + for i in range(len(num) - 1, -1, -1): + if num[i] > num[max_idx]: + max_idx = i + elif num[i] < num[max_idx]: + xi = i + yi = max_idx + num[xi], num[yi] = num[yi], num[xi] + return int("".join([str(x) for x in num])) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumSwap(2736)) + print(obj.maximumSwap(9973)) |