LeetCode ： 670. Maximum Swap 最大交换交换数中两位使之最大

Love The Way You Lie 2021-06-24 16:10 404阅读 0赞

**试题：**  
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\]  
**代码：**  
我们首先会想到，如果我们在第一位的后面能够找到比第一位大的数，那么是不是可以直接将他两交换，如果没找到的话我们是不是希望在第二位后面找到比第二位大的数来交换。简单方法是直接遍历。但复杂度高。如果我们可以先一次遍历找到数0-9出现的最后位置。可以使用一个简单hash方法。

class Solution {
        public int maximumSwap(int num) {
            char[] A = Integer.toString(num).toCharArray();
            int[] last = new int[10];
            for (int i = 0; i < A.length; i++) {
                last[A[i] - '0'] = i;
            }
    
            for (int i = 0; i < A.length; i++) {
                for (int d = 9; d > A[i] - '0'; d--) {
                    if (last[d] > i) {
                        char tmp = A[i];
                        A[i] = A[last[d]];
                        A[last[d]] = tmp;
                        return Integer.valueOf(new String(A));
                    }
                }
            }
            return num;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，404人围观）

还没有评论，来说两句吧...

相关阅读

相关【力扣 leetcode】670：最大交换

每日进步整数转字符串：int → \\rightarrow → String `String.valueOf(num)` 字符串转

深碍√TFBOYSˉ_/ 2023年10月09日 14:42/ 0 赞/ 81 阅读

相关 LeetCode_贪心算法_中等_670.最大交换

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。示

我会带着你远行/ 2023年10月06日 23:57/ 0 赞/ 21 阅读

相关 Java实现 LeetCode 670 最大交换（暴力）

670. 最大交换给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。示例 1 : 输入: 2736 输出: 7236 解释: 交

小咪咪/ 2023年07月22日 03:48/ 0 赞/ 17 阅读

相关 leetcode801 使序列递增的最小交换次数

我们有两个长度相等且不为空的整型数组 A 和 B 。我们可以交换 A\[i\] 和 B\[i\] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。在交换过一些元

素颜马尾好姑娘i/ 2023年07月02日 11:30/ 0 赞/ 5 阅读

相关 (必背)670. 最大交换(贪心法)

\\\ 解题思路把尽可能高位的最小数字和尽可能低位的最大数字进行交换 1.从低位到高位进行遍历,保存遍历到当前位为止的最大数的位置 2.从高位到低位进行遍历,找到第一个

今天药忘吃喽~/ 2023年01月08日 11:27/ 0 赞/ 45 阅读

相关最大交换

> leetcode 670 \[medium\] > 中：[最大交换][Link 1] > 英：[Maximum Swap][] > ![在这里插入图片描述][w

分手后的思念是犯贱/ 2022年12月27日 02:27/ 0 赞/ 189 阅读

相关 670 最大交换（找规律）

1. 问题描述：给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。示例 1 : 输入: 2736 输出: 7236 解释: 交换数字

快来打我*/ 2022年09月02日 11:37/ 0 赞/ 213 阅读

相关 LeetCode670. Maximum Swap

Brute-force Solution The question specifies that the upperbound of the number is `10^

桃扇骨/ 2022年06月07日 10:16/ 0 赞/ 162 阅读

相关 leetcode 670. Maximum Swap 交换2个位置获得最大值

Given a non-negative integer, you could swap two digits at most once to get the maximum

柔光的暖阳◎/ 2022年06月03日 07:40/ 0 赞/ 215 阅读

相关 LeetCode ： 670. Maximum Swap 最大交换交换数中两位使之最大

试题： Given a non-negative integer, you could swap two digits at most once to get the ma

Love The Way You Lie/ 2021年06月24日 16:10/ 0 赞/ 405 阅读