LeetCode 670. Maximum Swap
25 Jul 2018Description:
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.
Note:
- The given number is in the range \([0, 10^8]\)
Example:
input:
2736output:
7236explanation:
Swap the number 2 and the number 7.
input:
9973output:
9973explanation:
No swap.
Solution:
class Solution:
def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
numStr = repr(num)
numDigit = [int(ch) for ch in numStr]
if len(numDigit) <= 1:
return num
maxTable = [-1] * len(numDigit)
currentMax = (-1, -1)
for i in range(len(numDigit) - 1, -1, -1):
if numDigit[i] > currentMax[0]:
currentMax = (numDigit[i], i)
maxTable[i] = currentMax
for i in range(len(numDigit)):
if maxTable[i][0] > numDigit[i]:
# swap numDigit[i] and numDigit[maxTable[i][1]]
temp = numDigit[i]
numDigit[i] = numDigit[maxTable[i][1]]
numDigit[maxTable[i][1]] = temp
break
result = 0
for i in range(len(numDigit)):
result += numDigit[len(numDigit) - 1 - i] * pow(10, i)
return result
Starting backwards, keep track of a maxTable that stores the largest digit in the range [i:len(numDigit)]. Scan and compare each element in numDigit and maxTable from the right. If an element in maxTable is greater than its corresponding element in numDigit, execute the swap.