最大的交换

https://www.lintcode.com/problem/1095/?utm_source=sc-libao-ql

描述

给定一个非负整数, 你可以选择交换它的两个数位. 返回你能获得的最大的合法的数.

给定的数字在 [0, 10^8] 范围内

样例

样例1:

输入: 2736输出: 7236解释: 交换数字2和数字7.

样例2:

输入: 9973输出: 9973解释: 不用交换.

分析：

把数字化成int list, 用dict记载每个数字最后出现的位置。

遍历Int list, 对每个数字，遍历9~当前数字，找到第一个最后出现位置大于当前位置的，交换

注意字符到数组之间的相互变换：

int_list= list(map(int,str(num))
res = int(''.join(map(int,int_list)))

class Solution:
    """
    @param num: a non-negative intege
    @return: the maximum valued number
    """
    def maximum_swap(self, num: int) -> int:
        # Write your code here
        digits = list(map(int, str(num)))
        bucket = {x:i for i,x in enumerate(digits)}
        n = len(digits)
        for i in range(n):
            for j in range(9, digits[i],-1):
                if j in bucket and bucket[j] > i:
                    digits[i], digits[bucket[j]] = digits[bucket[j]], digits[i]
                    return int(''.join(map(str,digits)))
        return num