LC 670. Maximum Swap

时间:2023-01-30 10:28:50

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:

  1. The given number is in the range [0, 108]
 

Runtime: 4 ms, faster than 86.08% of C++ online submissions for Maximum Swap.

//
// Created by yuxi on 2019-01-18.
//
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std; class Solution {
private:
unordered_map<int,vector<int>> mp;
public:
int getret(vector<int>& a){
int ret = ;
for(int i=; i<a.size(); i++){
ret = ret * + a[i];
}
return ret;
}
int maximumSwap(int num) {
int savenum = num;
vector<int> numa;
while(num > ){
numa.push_back(num%);
num /= ;
}
reverse(numa.begin(), numa.end());
for(int i=; i<numa.size();i++) mp[numa[i]].push_back(i);
if(numa.size() == ) return numa[];
helper(numa, );
return getret(numa);
}
void helper(vector<int>& a, int idx) {
if(idx == a.size()) return ;
int maxval = INT_MIN, maxidx = ;
for(int i=idx; i<a.size(); i++) {
if(maxval < a[i]) {
maxval = a[i];
maxidx = i;
}
}
if(maxval != a[idx]) {
int tmp = a[idx];
a[idx] = maxval;
a[maxidx] = tmp;
if(mp[maxval].size() != && mp[maxval].back() > maxidx) {
a[mp[maxval].back()] = tmp;
a[maxidx] = maxval;
}
return;
} else {
helper(a, idx+);
}
}
};

LC 670. Maximum Swap的更多相关文章

  1. 670&period; Maximum Swap 允许交换一个数 求最大值

    [抄题]: Given a non-negative integer, you could swap two digits at most once to get the maximum valued ...

  2. &lbrack;LeetCode&rsqb; 670&period; Maximum Swap 最大置换

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

  3. 670&period; Maximum Swap

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

  4. &lbrack;LeetCode&rsqb; Maximum Swap 最大置换

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

  5. &lbrack;Swift&rsqb;LeetCode670&period; 最大交换 &vert; Maximum Swap

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

  6. Maximum Swap LT670

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

  7. LeetCode Maximum Swap

    原题链接在这里:https://leetcode.com/problems/maximum-swap/description/ 题目: Given a non-negative integer, yo ...

  8. 1095&period; Maximum Swap —— Weekly Challenge

    题目限定输入是[0, 10^8],因而不用考虑负数或者越界情况,算是减小了难度. public class Solution { /** * @param num: a non-negative in ...

  9. LC 918&period; Maximum Sum Circular Subarray

    Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty ...

随机推荐

  1. eclipse中egit插件使用

    这篇文章当时制作有点粗糙,建议阅读升级版:eclipse中egit插件使用--升级版 使用git作为项目的代码管理工具现在是越来越火,网上有各种各样的文章.博客.讨论,其中以命令行居多.使用eclip ...

  2. SQL IF ELSE

    if (条件)    begin        (执行模块)    endelse if (条件)    begin        (执行模块)    endelse    begin        ...

  3. hibernate配置文件hibernate&period;cfg&period;xml的详细解释

    <!--标准的XML文件的起始行,version='1.0'表明XML的版本,encoding='gb2312'表明XML文件的编码方式-->                 <?x ...

  4. 移动端自动化环境搭建-Appium Client的安装和AppiumLibrary库的安装

    A.安装依赖 appium client是配合原生的webdriver来使用的(特别是用java而不用maven的同学),因此二者必须配合使用缺一不可. B.安装过程 1.在线安装 pip insta ...

  5. 职责链模式,chain of responsibility

    定义: 使多个对象都有机会处理请求,从而避免请求的发送者和接收者之间的耦合关系.将这个对象连城一条链,并沿着这条链传递该请求,知道有一个对象处理它为止. 客户端并不知道哪个对象会最终处理这个请求,这样 ...

  6. js实现深拷贝和浅拷贝

    浅拷贝: 思路----------把父对象的属性,全部拷贝给子对象,实现继承. 问题---------如果父对象的属性等于数组或另一个对象,那么实际上,子对象获得的只是一个内存地址,不会开辟新栈,不是 ...

  7. 归并排序之python

    想更好的了解归并排序, 需先了解, 将两个有序列表, 组成一个有序列表 有两个列表  l1 = [1, 3, 5, 7] l2 = [2, 4, 6] 需要将 l1 和 l2 组成一个 有序大列表   ...

  8. phpMyAdmin 安装教程全攻略

    管理MYSQL数据库的最好工具是PHPmyAdmin,现在最新版本是phpMyAdmin 2.9.0.2,这是一个国际上开源的软件,一直在更新版本,你可以从 http://www.phpmyadmin ...

  9. UVA 10534 Wavio Sequence

    题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&p ...

  10. awk、sed、grep三大shell文本处理工具之awk的应用

    awk 1.是什么 是一个编程语言.支持变量.数组.函数.流程控制(if...else/for/while) 单行程序语言. 2.工作流程 读取file.标准输入.管道给的数据,从第一行开始读取,逐行 ...