aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--maximum_swap.c39
-rw-r--r--maximum_swap.py30
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))