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, 108]

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Mathematics

Greedy algorithms

Starter code: class Solution:
    def maximumSwap(self, num: int) -> int:
        

Solutions:
class Solution:

	def maximumSwap(self, num):
		s = str(num)
		nums = [int(_) for _ in s]
		dp = [-1] * len(nums)
		for i in range(len(nums) - 1, -1, -1):
			if i == len(nums) - 1:
				dp[i] = i
			else:
				dp[i] = i if nums[i] > nums[dp[i + 1]] else dp[i + 1]
		for i in range(len(nums)):
			if nums[i] != nums[dp[i]]:
				(nums[i], nums[dp[i]]) = (nums[dp[i]], nums[i])
				break
		res = 0
		for num in nums:
			res = res * 10 + num
		return res


class Solution:

	def maximumSwap(self, num):
		digits = ''
		while int(num):
			digits += str(int(num % 10))
			num /= 10
		digits = digits[::-1]
		lens = len(digits)
		mark = 0
		mark1 = 0
		flag = 0
		for i in range(lens):
			maxs = ord(digits[i])
			for j in range(i + 1, lens, 1):
				if ord(digits[j]) >= maxs:
					maxs = ord(digits[j])
					mark = j
			if maxs != ord(digits[i]):
				mark1 = i
				flag = 1
				break
		digit = list(digits)
		if flag == 1:
			tem = digit[mark1]
			digit[mark1] = digit[mark]
			digit[mark] = tem
		res = 0
		for i in range(lens):
			res *= 10
			res += ord(digit[i]) - ord('0')
		return res


class Solution:

	def maximumSwap(self, num):
		s = str(num)
		self.res = s

		def swap(i, j):
			(a, b) = (self.res[i], self.res[j])
			self.res = self.res[:i] + b + self.res[i + 1:]
			self.res = self.res[:j] + a + self.res[j + 1:]
		d = {}
		for (i, c) in enumerate(s):
			if c in d:
				d[c].append(i)
			else:
				d[c] = [i]
		c = 0
		for i in range(10)[::-1]:
			i = str(i)
			if i in d:
				arr = d[i]
				done = False
				for e in arr:
					if e != c:
						swap(c, arr[-1])
						done = True
						break
					c += 1
				if done:
					break
		return int(self.res)


class Solution:

	def maximumSwap(self, num):
		import itertools
		A = [c for c in str(num)]
		suff_max = list(itertools.accumulate(A[::-1], max))[::-1]
		last = {x: i for (i, x) in enumerate(A)}
		try:
			(i, x, y) = next(((i, x, y) for (i, (x, y)) in enumerate(zip(A, suff_max)) if x != y))
		except StopIteration:
			return num
		(A[i], A[last[y]]) = (A[last[y]], A[i])
		return int(''.join(A))


class Solution:

	def maximumSwap(self, num):
		import itertools
		A = [c for c in str(num)]
		suff_max = list(itertools.accumulate(A[::-1], max))[::-1]
		last = {x: i for (i, x) in enumerate(A)}
		for (i, x) in enumerate(A):
			if x < suff_max[i]:
				(A[i], A[last[suff_max[i]]]) = (A[last[suff_max[i]]], A[i])
				break
		return int(''.join(A))


class Solution:

	def maximumSwap(self, num):
		A = list(str(num))
		ans = A[:]
		for i in range(len(A)):
			for j in range(i + 1, len(A)):
				(A[i], A[j]) = (A[j], A[i])
				if A > ans:
					ans = A[:]
				(A[i], A[j]) = (A[j], A[i])
		return int(''.join(ans))


class Solution:

	def maximumSwap(self, num):
		arr = str(num)
		n = len(arr)
		posmax = [0] * n
		posmax[-1] = n - 1
		pow10 = [0] * n
		pow10[-1] = 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[posmax[i + 1]]:
				posmax[i] = i
			else:
				posmax[i] = posmax[i + 1]
			pow10[i] = pow10[i + 1] * 10
		for i in range(n):
			if arr[i] == '9':
				continue
			j = posmax[i]
			if arr[j] > arr[i]:
				x = int(arr[i])
				y = int(arr[j])
				return num + pow10[i] * (-x + y) + pow10[j] * (-y + x)
		return num


class Solution:

	def maximumSwap(self, num):
		arr = [int(c) for c in str(num)]
		n = len(arr)
		posmax = [0] * n
		posmax[-1] = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[posmax[i + 1]]:
				posmax[i] = i
			else:
				posmax[i] = posmax[i + 1]
		for i in range(n):
			if arr[i] == 9:
				continue
			j = posmax[i]
			if arr[j] > arr[i]:
				(arr[i], arr[j]) = (arr[j], arr[i])
				return int(''.join(map(str, arr)))
		return num


class Solution:

	def maximumSwap(self, num):
		array = list(map(lambda x: int(x), str(num)))
		stack = []
		l = float('inf')
		r = None
		for (i, d) in enumerate(array):
			while stack and array[stack[-1]] < d:
				l = min(l, stack.pop())
			stack.append(i)
			if l < float('inf'):
				if not r or array[r] <= d:
					r = i
		if l == float('inf'):
			return num
		else:
			basel = 10 ** (len(array) - 1 - l)
			baser = 10 ** (len(array) - 1 - r)
			return num + basel * (array[r] - array[l]) + baser * (array[l] - array[r])


class Solution:

	def swap(self, i, c):
		for ii in range(len(self.res))[::-1]:
			if self.res[ii] == c:
				(a, b) = (self.res[i], self.res[ii])
				self.res = self.res[:i] + b + self.res[i + 1:]
				self.res = self.res[:ii] + a + self.res[ii + 1:]
				break

	def maximumSwap(self, num):
		s = str(num)
		l = sorted(list(s), reverse=True)
		self.res = s
		for (i, char) in enumerate(s):
			if char != l[i]:
				self.swap(i, l[i])
				break
		return int(self.res)