leetcode670

Posted on | In

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:

1
2
3
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

1
2
3
Input: 9973
Output: 9973
Explanation: No swap.

Note:
The given number is in the range [0, 10^8]

Idea

Simply thinking, brute force is ok, whose time complexity is O(n^2). In fact, for the former bit, we should find a largest bit which occurs latest, which is the solution.

1
2
largest 7689 >> 9687
latest 7688 >> 8687

Code

cited from https://leetcode.com/problems/maximum-swap/discuss/107066/Python-Straightforward-with-Explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        A = map(int, str(num))
        num2idx = {x: i for i, x in enumerate(A)}
        for i, x in enumerate(A):
            for larger in range(9, x, -1):
                if num2idx.get(larger, -1) > i: # find a larger bit which is later
                    A[i], A[num2idx[larger]] = A[num2idx[larger]], A[i]
                    return int("".join(map(str, A)))
        return num

Thinking

How about 9973, where ‘num2idx = {x: i for i, x in enumerate(A)}’ may omits 9:0 pair and leave 9:1 ?

Python

map(function, iterable, …)

1
2
3
4
5
6
7
8
9
10
11
>>>def square(x) :            # 计算平方数
...     return x ** 2
... 
>>> map(square, [1,2,3,4,5])   # 计算列表各个元素的平方
[1, 4, 9, 16, 25]
>>> map(lambda x: x ** 2, [1, 2, 3, 4, 5])  # 使用 lambda 匿名函数
[1, 4, 9, 16, 25]
 
# 提供了两个列表，对相同位置的列表数据进行相加
>>> map(lambda x, y: x + y, [1, 3, 5, 7, 9], [2, 4, 6, 8, 10])
[3, 7, 11, 15, 19]

map(int, str(123))

1
2
>> map(int, ['1', '2', '3'])
>> map([int('1'), int('2'), int('3')])