[leetcode] 670. Maximum Swap

[leetcode] 670. Maximum Swap

Description

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: 2736Output: 7236Explanation: Swap the number 2 and the number 7.

Example 2:

Input: 9973Output: 9973Explanation: No swap.

Note:

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

分析

题目的意思是：我们有一次机会可以置换该数字中的任意两位，让我们返回置换后的最大值，当然如果当前数字就是最大值，我们也可以选择不置换，直接返回原数。

将所有可能的置换都进行一遍，然后更新结果res，取其中较大的数字，这样一定会得到置换后的最大数字，这里使用了整型数和字符串之间的相互转换。

代码

class Solution {public: int maximumSwap(int num) { string str=to_string(num); int res=num; for(int i=0;i

代码二（python）

从后向前遍历，如果遇到更大的值maxValue，那么保存这个值的下标（index）和值（value）如果在这个值的左边遇到比maxValue小的数，那么保存对应的值leftValue和leftIndex，并将maxIndex赋予给rightiIndex，leftIndex和rightIndex这两个配对组成一组候选值从右向左遍历数组，遇到满足上述条件的值就覆盖更新对应的值，最后交换leftIndex和rightIndex下标对应的数即可

class Solution: def maximumSwap(self, num: int) -> int: s=list(str(num)) maxVal=-1 maxIdx=-1 n=len(s) leftIdx=-1 rightIdx=-1 for i in range(n-1,-1,-1): if(maxVal

参考文献

​​Maximum Swap 最大交换​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。