670. Maximum Swap

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, 10^8 ]

Solutions

　　刚开始一脸懵逼，因为不想用暴力求解，结果想半天越想懵，还是参考后用暴力解了……

class Solution(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        str_num = list(str(num))
        n = len(str_num)
        res = str_num[:]
        for i in range(n):
            for j in range(i+1, n):
                str_num[i], str_num[j] = str_num[j], str_num[i]
                if res < str_num:
                    res = str_num[:]
                str_num[i], str_num[j] = str_num[j], str_num[i]
        return ''.join(res)
# Runtime: 20 ms, faster than 67.02% of Python online submissions for Maximum Swap.
# Memory Usage: 11.8 MB, less than 36.89% of Python online submissions for Maximum Swap.

　　按照规律的思路：

从前往后找到第一升序的位置：R[i-1] < R[i]；
再从前往后找到比后半部分 R[i:] 的最大值小的位置，交换这两个数即可。

class Solution(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        i, R = 1, list(str(num))
        n = len(R)
        while i < n and R[i-1] >= R[i]:
            # 找到第一个升序的 i
            i += 1
        if i < n:
            j, k = 0, str(num).rfind(max(R[i:]))
            while j < i and R[j] >= R[k]:
                j += 1
            R[j], R[k] = R[k], R[j]
        return ''.join(R)

# Runtime: 8 ms, faster than 99.13% of Python online submissions for Maximum Swap.
# Memory Usage: 11.9 MB, less than 22.13% of Python online submissions for Maximum Swap.

Solutions

References