目录
一、题目
1、题目描述
2、接口描述
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
给定一个非负整数,你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736 输出: 7236 解释: 交换数字2和数字7。
2、接口描述
class Solution {
public:
int maximumSwap(int num) {
}
};
3、原题链接
670. 最大交换
二、解题报告
1、思路分析
贪心的考虑,肯定优先把高位跟大数字交换,我们从高位遍历,如果高位右边有数组比高位大,那么和右边最大数字且最靠右的那个交换即可文章来源:https://www.toymoban.com/news/detail-819200.html
2、复杂度
时间复杂度:O(log num) 空间复杂度:O(log num)文章来源地址https://www.toymoban.com/news/detail-819200.html
3、代码详解
class Solution {
public:
int maximumSwap(int num) {
int d[10] , pre[10]{0} , n = 0;
while(num) {
d[++n] = num % 10 , num /= 10;
pre[n + 1] = d[pre[n]] >= d[n] ? pre[n] : n;
}
for(int i = n ; i >= 1 ; i--)
if(d[pre[i]] > d[i]){
swap(d[i] , d[pre[i]]);
break;
}
for(int i = n ; i >= 1 ; i--)
num = (num << 3) + (num << 1) + d[i];
return num;
}
};
到了这里,关于LeetCode 670. 最大交换的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!