Given an integer n, you can swap any two digits at most once. Return the maximum value of the resulting number.
Constraints
0 ≤ n < 2 ** 31
Example 1
Input
n = 1929
Output
9921
Explanation
We swap the first and the last digits
Determine the Maximum Number After One Swap
The greedy strategy is to get the rightmost largest digit that is bigger than the current digit. We keep moving to right until we find such swap. If there is (the digits are already the biggest, digits in descending orders), we return it.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def solve(self, n): s = list(str(n)) for i in range(len(s)): x = i for j in range(i + 1, len(s)): if s[j] >= s[x]: x = j if s[x] != s[i]: s[i], s[x] = s[x], s[i] return int(''.join(s)) return n |
class Solution:
def solve(self, n):
s = list(str(n))
for i in range(len(s)):
x = i
for j in range(i + 1, len(s)):
if s[j] >= s[x]:
x = j
if s[x] != s[i]:
s[i], s[x] = s[x], s[i]
return int(''.join(s))
return nThe time complexity is O(N^2) where N is the size of the digits.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
231 wordsloading...
Last Post: Teaching Kids Programming - Depth First Search Algorithm to Check If Leaves are Same Level in Binary Tree
Next Post: Teaching Kids Programming - Breadth First Search Algorithm to Check if All Leaves in Same Level of Binary Tree
