我要招人

去企业版

首页 > 试题广场 >

最大数字交换

[编程题]最大数字交换

热度指数：1127 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串num，字符串由0~9的正整数组成，你至多可以交换一次字符串中的任意两位字符，使得交换后的num代表的正整数尽可能大。

1.给定的num不会含有前导0，是一个合法的正整数类型的字符串

2.可以不交换，但是最多只能交换一次

数据范围： $1 \le num.length \le 10^5 \$

示例1

输入

"4556"

输出

"6554"

说明

交换6和4，可以获得最大的正整数6554

示例2

输入

"5"

输出

"5"

示例3

输入

"8873"

输出

"8873"

说明

不需要交换

算法知识视频讲解

牛客386279289号

char* maximumSwap(char* num ) {
    // write code here
    char *ret = num;
    const char first = *num;
    char max = *num;
    int dmax = 0, replace = 0;
    num++;
    while (*num != 0) {
        dmax ++;
        if (*num >= max && *num > first) {
            max = *num;
            replace = dmax;
        }
        num++;
    }
    if (!replace) {
        ret ++;
        if (*ret != 0) {
            ret = maximumSwap(ret);
        }
        ret --;
        return ret;
    } else {
        *ret = ret[replace];
        ret[replace] = first;
    }

发表于 2022-08-30 23:10:24 回复(0)

牛客962313693号

从右往左找最大的存下来，然后，从左往右找到第一个比他小的替换

class Solution:

def maximumSwap(self, num: str) -> str:
# write code here
num = list(map(str,num))
maxI = len(num) - 1

maa = lambda maxI,r:r if num[r]>num[maxI] else maxI

for r in range(len(num)-2,0,-1):
maxI = maa(maxI,r)
maxV = num[maxI]

for j in range(maxI):
if num[j]<maxV:
temp = num[j]
num[j]=maxV
num[maxI]=temp
break
return ''.join(num)

发表于 2022-07-30 16:40:51 回复(1)

小谷围做题家

package main
import "strings"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num string字符串 
 * @return string字符串
*/
func maximumSwap( num string ) string {
    nums:=strings.Split(num,"")
    for i:=0;i<len(nums);i++{
        max:=i
        for j:=i+1;j<len(nums);j++{
            if nums[j]>=nums[max]{
                max=j
            }
        }
        if nums[max]>nums[i]{
            nums[max],nums[i]=nums[i],nums[max]
            break
        }
    }
    return strings.Join(nums,"")
}

发表于 2023-03-29 17:43:46 回复(0)

算帝

char* maximumSwap(char* num ) {
    int len = strlen(num);
    int index, tmp;

    for(int i = 0; i < len; i++) {
        index = i;
        for(int j = len - 1; j > i; j--) {
            if(num[j] > num[index]) {
                index = j;
            }
        }
        if(index != i) {
            tmp = num[i];
            num[i] = num[index];
            num[index] = tmp;
            break;
        }
    }
    return num;
}

发表于 2023-01-06 23:22:40 回复(0)

数学计算机王子

想问一下大家，我这个测试时显示段错误，我想问一下有人知道哪里写的有问题吗？

class Solution {
public:
    char max_char[100005];
    int max_index[100005];

    string maximumSwap(string num) {
        int lens = num.size();
        if (lens > 1) {
            max_char[lens - 1] = num[lens - 1];
            max_index[lens - 1] = lens - 1;
            for (int i = lens - 2; i >= 0; i--) {
                if (num[i] > max_char[i + 1]) {
                    max_char[i] = num[i];
                    max_index[i] = i;
                } else {
                    max_char[i] = max_char[i + 1];
                    max_index[i] = max_index[i + 1];
                }
            }
            for (int i = 0; i < lens - 1; i++) {
                if (i != max_index[i] && num[i] != num[max_index[i]]) {
                    char tmp = num[i];
                    num[i] = num[max_index[i]];
                    num[max_index[i]] = tmp;
                    break;
                }
            }
        }
        return num;
    }
};

编辑于 2022-07-16 14:31:24 回复(0)

C++

等一个offer！

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    string maximumSwap(string num) {
        int len=num.size();
        for(int i=0;i<len-1;i++){
            char maxBit=num[i];
            int index=0;
            for(int j=1;j<len;j++){
                if(maxBit<=num[j]){
                    maxBit=num[j];
                    index=j;
                }
            }
            if(maxBit!=num[i]){
                swap(num[i],num[index]);
                return num;
            }
        }
        return num;
    }
};

发表于 2022-04-27 11:28:38 回复(0)

C++

你能教我cpp吗

求大佬指导下为什么这么写不能通过呀，测试用例很长，也看不出来哪里有问题
string maximumSwap(string num) {
        // write code here
        int len=num.size();
        for(int i=0;i<len;i++){
            int index=i;
            for(int j=i+1;j<len;j++){
                if(num[j]>num[index]){
                    index=j;
                }
            }
            if(index!=i){
                swap(num[i],num[index]);
                return num;
                
            }
        }
        return num;
}

发表于 2022-03-02 15:52:05 回复(5)

Python 3

牛客343459580号

# @param num string字符串 
# @return string字符串
#
class Solution:
    def maximumSwap(self , num: str) -> str:
        # write code here
        max_value = num[-1]
        max_place = len(num)-1
        for i in range(len(num)-2,-1,-1):
            if(num[i] > max_value):
                max_value = num[i] 
                max_place = i
        num = list(num)
        for j in range(0,max_place):
            if(num[j] < max_value):
                num[j],num[max_place] = max_value,num[j]
                break
        return "".join(num)

发表于 2022-02-20 14:07:02 回复(2)

提交观点

问题信息

贪心

难度：

8条回答 9收藏 1622浏览

通过挑战的用户

查看代码

牛客94569...

2022-12-08 10:02:14
王小牛123

2022-09-15 09:50:56
就，很有意思

2022-09-12 10:35:39
外骨骼

2022-09-10 10:58:52
林子20190...

2022-09-08 15:49:42

最大数字交换

输入

输出

说明

输入

输出

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题