LeetCode-670. 最大交换-题解分析

题目来源

670. 最大交换

题目详情

给定一个非负整数,你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

  1. 给定数字的范围是 [0, 108]

题解分析

本题一开始看没有明确的解题思路,会感觉无从下手。其实,本题的关键是越往后找到一个最大的数与越靠前的最小的数进行交换。

核心思路是将最靠后的最大的数,与最靠前的小于它的数交换(若存在),得到最大结果。具体的解法是使用贪心法求解最优数字交换方案。

本题使用贪心法需要考虑的两个核心思路是:

  • 选择哪个数作为候选数与前面的数交换?——将最靠后的数定为候选数,若它之前出现了更大的数,则更新候选数为该数。
  • 选择哪个数与候选数交换?——只有当候选数之前存在更小的数时,才需要交换这两数。若更靠前的位置出现小于候选数的数,则将它与候选数交换。

本题可以同时设置一个最大索引maxIdx以及一个候选索引candidate分别来记录右边最大值以及左边的候选值。字符串的遍历方向从右往左,不断比较记录最大值的位置,当遇到小于最大值的位置时,将其置为候选位置。

需要注意的是,这里在记录candidate候选位置的时候,同时需要记录一个endIdx指针,该指针记录了最大值索引。之所以不直接使用maxIdx表示最终需要交换的最大值索引,是因为前面可能出现比后面最大值还大的数字,这些数字不应该被替换,只需要替换最小值之后的候选位置。

java实现

class Solution {
    public int maximumSwap(int num) {
        String str = String.valueOf(num);
        int len = str.length();
        int maxIdx = len - 1;
        int candidate = -1;
        int endIdx = -1;
        for (int i = len-1; i >= 0; i--) {
            int number = str.charAt(i) - '0';
            int maxs = str.charAt(maxIdx) - '0';
            if (number > maxs) {
                maxIdx = i;
            } else if (number < maxs) {
                candidate = i;
                endIdx = maxIdx;
            }
        }
        if (candidate < 0) {
            return num;
        }
        String res = swap(str, candidate, endIdx);
        return Integer.parseInt(res);
    }

    private String swap(String str, int i, int j) {
        StringBuilder sb = new StringBuilder(str);
        sb.setCharAt(i, str.charAt(j));
        sb.setCharAt(j, str.charAt(i));
        return sb.toString();
    }
}
Either Excellent or Rusty
本文转载于网络 如有侵权请联系删除

相关文章

  • 清华&旷视:让VGG再次伟大!

    丰色发自凹非寺 量子位报道|公众号QbitAICNN经典模型VGG自2014年诞生以来,由于相比于各种多分支架构(如ResNet)性能不佳,已渐“没落”……但来自清华大学和旷视科技等机构的研究人员,他们居然只用3x3卷积和ReLU激活函数的超级简单架构,通过结构重参数化(structuralre-parameterization),就让这个7年前的老架构再次“容光焕发”!GreatAgain!简单到什么程度?研究人员表示:下午5点看完文章,晚饭前就能写完代码开始训练,第二天就能看到结果。如果没时间看完这篇文章,只要点开GitHub上的代码,看完前100行就可以完全搞明白。新架构RepVGG结合了多分支架构和单路架构的优点,在速度和性能上直达SOTA,在ImageNet上精度超过80%!相关论文已被CVPR2021接收,开源预训练模型和代码在GitHub上也已收获1700+标星!兼顾多分支和单路架构的优点一个已经快要“没落”的老模型,为什么还要重新捡起利用?研究人员介绍道,因为简单的VGG式模型(单路架构、仅使用3x3卷积和ReLU激活函数)有五大现实优势:1、3x3卷积非常快。在GPU

  • Selenium工具的各个组件以及演变历史你都了解吗

    Selenium是一款用于Web应用程序测试的工具,支持多平台、多浏览器、多语言去实现自动化测试。Selenium的特点如下:开源,免费多浏览器支持:Firefox、Chrome、IE、Opera、Edge等多平台支持:Linux、Windows、Mac多语言支持:Java、Python、Ruby、C#、JavaScript等支持分布式执行Selenium到目前为止已经经历了三个版本,Selenium1.0、Selenium2.0和Selenium3.0。Selenium1.0SeleniumIDE:早期是嵌入到Firefox浏览器中的一个插件,现在也支持Chrome浏览器了,能够实现简单的浏览器操作的录制与回放功能,并支持导出成对应语言的测试脚本。 SeleniumGrid:负责运行脚本,支持多机器不同环境之间运行相同的用例,提升测试效率。SeleniumRC:分为Client和Server端,Client负责编写测试脚本,用来控制Server库。Server负责控制浏览器的行为。Server主要包含三部分:Launcher、HttpProxy和Core。Core是被嵌入到浏览器页面

  • 迎接双11,深度剖析高并发数据库Sharding的道与术

    迎接双11,高并发数据库设计,文末有福利~~ 01、为什么讨论分库分表之道?在服务器后端技术人员的成长路线上,分片(Sharding)思想的理解和把握是绕不过去的门槛,而数据库分库分表可能是讲述拆分思想最好的教材,大部分后端技术人员都会在成长过程中遇到数据库分库分表的问题。为什么讲道,因为道比术重要一万倍。技术浪潮一波一波在推动社会的前进,新的技术雨后春笋,简单且朴实的道理,更长久也更朴实且普适。正所谓有道无术术可求,有术无道止于术。02、为什么需要数据库分库分表?如何描述分库分表呢?可以这样定义分库分表,当业务的增长导致数据库瓶颈的时候,一种解决瓶颈的手段。 单机数据库很容易出瓶颈,包含性能、容量等。一方面是存在放大效应。比如:业务强要求所有的请求在100ms返回,这100ms分配到数据库,可能留的时间也就1-2ms,任何数据库的波动,会被放大10-20倍反应到上层服务;另一方面是存在单点问题,数据库保持了最新且最准确的状态,这个状态增长是随业务增长同步的,且业务的增长会导致业务的复杂性,复杂性最后反应到数据库的存储里代表的就是增量。数据库需要应对随业务增长指数上升的数据增量,且数据

  • MySQL集群高可用架构之MHA

    1前言导读记得之前发过一篇文章,名字叫《浅析MySQL高可用架构》,之后一直有很多小伙伴在公众号后台或其它渠道问我,何时有相关的深入配置管理文章出来,因此,民工哥,也将对前面的各类架构逐一进行整理,然后发布出来。那么今天将来发布的MHA的架构整体规划与配置操作。2架构简介MHA(MasterHighAvailability)目前在MySQL高可用方面是一个相对成熟的解决方案,作为MySQL高可用性环境下故障切换和主从提升的高可用软件。在MySQL故障切换过程中,MHA能做到在0~30秒之内自动完成数据库的故障切换操作,并且在进行故障切换的过程中,MHA能在最大程度上保证数据的一致性,以达到真正意义上的高可用。该软件由两部分组成:MHAManager(管理节点)和MHANode(数据节点)。MHAManager可以单独部署在一台独立的机器上管理多个master-slave集群,也可以部署在一台slave节点上。MHANode运行在每台MySQL服务器上,MHAManager会定时探测集群中的master节点,当master出现故障时,它可以自动将最新数据的slave提升为新的master

  • 聊聊skywalking的MemoryProvider

    序本文主要研究一下skywalking的MemoryProviderMemoryProviderskywalking-6.6.0/apm-sniffer/apm-agent-core/src/main/java/org/apache/skywalking/apm/agent/core/jvm/memory/MemoryProvider.javapublicenumMemoryProvider{ INSTANCE; privatefinalMemoryMXBeanmemoryMXBean; ​ MemoryProvider(){ this.memoryMXBean=ManagementFactory.getMemoryMXBean(); } ​ publicList<Memory>getMemoryMetricList(){ List<Memory>memoryList=newLinkedList<Memory>(); ​ MemoryUsageheapMemoryUsage=memoryMXBean.getHeapMemoryUsage(); Mem

  • AI不是万灵神药!看看普林斯顿大学的这份“假AI防骗报告”

    来源:cs.princeton.ed编辑:小芹、大明本文转自公众号:新智元【导读】普林斯顿大学教授最新报告《如何区分AI“万灵假药”》近日火了,很多宣称采用AI算法预测社会后果的技术,实际不比线性回归模型好多少。你怎么看AI“万灵假药”?AI不是万灵药,但越来越多的人把它说成是万灵药,在这些人的鼓吹下,更多的人可能真的会把AI当成万灵药。那么,如何在周围人都在吹的氛围下冷静下来,分辨真假?近日,普林斯顿大学计算机系ArvindNarayanan副教授撰写了一份报告,题目就是《如何区分AI“万灵假药”》。报告全文要点如下:1、有很多与AI无关的东西都被打上AI标签,目前已经诞生的真正的、有社会影响力的AI技术无意间充当了这些冒牌货的保护伞。2、很多宣称采用AI算法的技术涉及对社会后果的预测。事实是,我们并不能预测未来,但当涉及AI时,这个常识似乎就我们无视了。3、在风险行为预测上,手动评分要比AI评分靠谱得多。比如违规驾驶,人工计分,到一定程度吊销驾照,这个计分还是要交给人来做。作者首先举了个例子。下边这个网站宣称,只用一段30秒的短视频,就能评估出你的职业前途和工作的稳定程度。听起来是

  • Python人工智能-基于百度AI接口

    准备工作:支持Python版本:2.7.+,3.4+安装使用PythonSDK有如下方式如果已经安装了pip,执行pipinstallbaidu-aip即可。如果已安装setuptools,执行pythonsetup.pyinstall即可。登录百度ia网站:用百度账号登录进入左侧语言应用创建新应用选择应用创建完毕应用详情fromaipimportAipSpeech"""你的APPIDAKSK"""APP_ID='写注册的APP_ID'API_KEY='写注册的API_KEY'SECRET_KEY='写注册的SECRET_KEY'client=AipSpeech(APP_ID,API_KEY,SECRET_KEY)result=client.synthesis('空山新雨后天气晚来秋','zh',1,{'vol':5,#音量'spd':3,#语速'pit':9,#语调&

  • 一名普通java程序员如何成为一名高级架构师?

    现在普通的java程序员多如牛毛,但真正站在金字塔顶端的程序员少的可怜,可以称之为可遇不可求,要成为一个高级架构师需要很多因素,除了自身因素之外还要需要外界环境激发,一个架构师首先是一个优秀的程序员,从事十几年始终自我定位也不是一个什么优秀的程序员,但有幸的在技术生涯持续过程中遇到几位真正的技术高手,在这尝试总结归纳下编程的习惯。1.对编程极度热爱,没有丝毫的厌倦每个人都对编程充满无线的兴趣,无论做什么项目都是精神饱满,如果不是内心极度的热爱很难就这么高的工作热情,骨子里的东西有时候是装不出来的,兴趣是第一老师在他们身上有着非常明显的体现。记得有一次回老家休年假在老家做了一套升级程序给公司产品来用,根本不是在休假分明是在工作,因为没有人强迫他去工作或者开发软件产品,一次在一起吃饭讨论这个话题,说到这些细节他说除了写代码真不知道还能做点什么,只要在电脑旁边就想着琢磨点什么东西,而且有时候在电脑旁边一呆就是几个小时,还不会觉得很疲惫,而且有时候还觉得不过瘾,所以有时候加班到很晚,有一次光顾他家发现他们的家的投影仪给改装了,还从淘宝买了很多器件去组装,连硬件也一块给弄了。2.不停歇对新技术的

  • 全栈工程师必备:安卓移动端手机开发,第六课

    本系列课程致力于老手程序员可以快速入门学习安卓开发。系统全面的从一个.Net程序员的角度一步步学习总结安卓开发。上篇课程:安卓一步步从基础到精通自学教程,纯实战,纯干货(五)简单计算器程序前台界面如何与后台处理类联系在一起。上一课我们已经把计算器的前台页面搭建完成了,本次我们将实现真正的加法计算器功能。安卓程序的开发类似于我们学习过的ASP.Net和Winform,也有前台页面和后台处理程序之分。所对应的安卓处理程序在这里不知大家有没有发现。这两个对应的命名方式或有有些规律。是的。我们把后台处理类的名称要以:xxxxActivity前台界面按照activity_xxx的格式书写。那么什么是activity?官方的说法是Activity一个应用程序的组件,它提供一个屏幕来与用户交互,以便做一些诸如打电话、发邮件和看地图之类的事情。我们可以理解为,他是一个窗口界面程序。一个activity包括后台和前台。表示一个窗口组件我们打开MainActivity揭开她的神秘面纱:其实这只是一个特殊的继承自:AppCompatActivity的类。我们看到里面包含一个OnCreate方法。对的这个On

  • Python使用BeautifulSoup爬取妹子图

    最近突然发现之前写的妹子图的爬虫不能用了,估计是网站又加了新的反爬虫机制,本着追求真理的精神我只好又来爬一遍了!效果文件夹妹子图思路整理页面地址:http://www.meizitu.com/获取首页分类标签地址,传入下一步 image.png 获取每个分类下内容页面地址 image.png 获取内容页面图片地址以及标题,以页面标题作为文件夹名 image.png 最后保存图片就好了代码所需包importos importsys importurllib2 frombs4importBeautifulSoup importrequests importlxml importuuid复制获取地址首先说BeautifulSoup真的是爬虫利器,不过需要注意这里返回的list,还需要通过for循环读取每个地址。贴一段官方解释:BeautifulSoup提供一些简单的、python式的函数来处理导航、搜索、修改分析树等功能。它是一个工具箱,通过解析文档为用户提供需要抓取的数据,因为简单,所以不需要多少代码就可以写出一个完整的应用程序。 BeautifulSoup自

  • OpenStack Queens Cinder Multi-Attach 功能

    OpenStackQueens平台于2月28日正式发布,这是该开源云平台的第17版。OpenStackQueens增加了多项新功能,也优化增强了多项旧功能,包括虚拟GPU(vGPU)支持和容器集成的改进。几个新项目也在OpenStackQueens这一里程碑中露面,包括提供管理硬件和软件加速资源框架的Cyborg。 Queens发布了一些强大的面向企业的功能,其中最引人注目的是Cinder中的Multi-Attach功能。CinderMulti-Attach使运维者能够将相同的Cinder卷加载到多个VM中。如果一个节点关闭,另一个节点能够接管并访问该卷。 环境准备1.安装OpenStackQueens使用devstack安装openstack(stable/queens),这里不再赘述。2.Cinder需要满足的条件Multi-Attach功能在cindermicroversion>=3.50版本可用,查看stable/queens的cinder版本 复制#cinder--version 3.5.0复制3.Nova需要满足的条件novaapimicroversion版本高于或等

  • kubernetes 基础集群排障

    排错指南在排错过程中,kubectl是最重要的工具,通常也是定位错误的起点。这里也列出一些常用的命令,在后续的各种排错过程中都会经常用到。查看Pod状态以及运行节点[root@vm_0_10_centossysctl.d]#kubectlgetpods-owide NAMEREADYSTATUSRESTARTSAGEIPNODE nginx-2217866662-nhkqz1/1Running015s172.16.0.510.0.0.10 [root@vm_0_10_centossysctl.d]#kubectl-nkube-systemgetpods-owide NAMEREADYSTATUSRESTARTSAGEIPNODE kube-dns-3162619857-mmspm3/3Running040m172.16.0.210.0.0.10 l7-lb-controller-2881622555-0v0p41/1Running040m172.16.0.310.0.0.10复制查看Pod事件kubectldescribepod<pod-name> [root@vm_0

  • Centos下添加用户组

    近日,重新整理了下开发环境,重装了,nginx,但是这个时候却是报错了,报错信息如下: [root@hserver1php-7.0.5]#nginx-t nginx:[emerg]getpwnam("nginx")failedin/etc/nginx/nginx.conf:2 nginx:configurationfile/etc/nginx/nginx.conftestfailed 复制    喏,很明显了,缺少用户组信息,至于为什么会缺少呢?暂时不清楚,如果有知道原因的请评论区留言,万分感谢。 好了,既然缺少用户组,那么我们肯定是要创建一个用户组信息了: 创建用户组; [root@hserver1php-7.0.5]#groupadd-fnginx groupadd:cannotopen/etc/group 复制   嗯?打不开?没权限?通过用lsattr命令查看/etc/group的隐藏权限设定情况发现如下: [root@hserver1php-7.0.5]#lsattr/etc/group ----i-----------/etc/group 复制    

  • kuangbin_SegTree I (HDU 1540)

    做完D之后我信誓旦旦以为之后就只剩一个二维就能攻克线段树了看来也跟图论一样全是模板嘛 然后我打开了I题一眼看下去似乎直接用线段树记录sum然后跟区间长度比较然后处理一下实现也不难 两个小时后:特么的好像没那么简单啊 然后我百度了才知道原来这又是一个新题型...区间合并...啊啊啊啊啊 感谢kuangbin巨巨的blog让我学会了这个方法... 另外我WA了一天然后上机课时候打开来重新看的时候一眼瞟到build的时候l跟r写反了心痛   再多说一句这题hdu一如既往的坑明明有好多组数据input上非说只有一组 #include<cstdio> #include<cmath> #include<cstring> #include<stack> #include<algorithm> #defineINF0x3f3f3f3f #definemem(str,x)memset(str,(x),sizeof(str)) #defineSTOPputs("Pause"); #definelsonl,m,rt<<1 #

  • IPV6_路由重定向

    目录路由重定向路由重定向的概念路由重定向需要满足的条件报文分析 路由重定向 路由重定向的概念 路由重定向是基于路由器发送的,那肯定是使用RA报文。 当一个网关设备发现数据包进来的接口和出去的接口是一个接口的时候,网关设备意识到这个路径不是最优的,走了冤枉路,其实可以不用通过自己的,就通过重定向报文告诉发送这个数据包的主机,你下次再给目标IP发送报文的时候不用将目标IP填写成“我”,直接填写成最优的下一跳即可。 好,我们仔细想一下,这对网关设备的要求就高了,要求路由器能判断出数据包的转发路径不是最优的路径,这怎么判断呢?如上所说,其实很简单,就是收到这个数据包的接口与路由后发送这个数据的接口是一个接口。 对于主机而言收到重定向报文意味着什么? 其实对于主机而言收到重定向报文意味着向在自己的路由表上添加一条主机路由,下一跳就是重定向报文当中告诉主机的下一跳。 那你说,在这个报文是否可以采取一些攻击的机制,比如给主机一些错误的重定向报文,让主机瞎重定向,让主机无法正常使用?是可以的,在IPV4当中就用路由重定向攻击这一种攻击方式,其实主要是利用了IPV4当中路由重定向的时候缺乏安全验证机制,

  • Sequelize 基本操作

    sequelize基本操作 Sequelize是Node的一个ORM(Object-RelationalMapping)框架,用来方便数据库操作。 配置sequelize 以mysql为例 首先我们要引入npm包,sequelize依赖mysql2作为底层驱动,暴露出自己的API让我们调用,在转成mysql语句进行执行。 "mysql2":"^1.5.1", "sequelize":"^4.28.6" 复制 constSequelize=require('sequelize') //连接数据库 constsequelize=newSequelize('database','username','password',{ host:sqlconf.host, dialect:'mysql',//这里可以改成任意一种关系型数据库 pool:{ max:5, min:0, acquire:30000, idle:10000, }, }) //测试连接是否成功 sequelize .authenticate() .then(()=>{ console.log('Connectio

  • CPU亲和力

      http://blog.chinaunix.net/uid-27714502-id-3515874.html http://www.tuicool.com/articles/I7NFzy http://blog.chinaunix.net/uid-27714502-id-3515874.html    非统一内存访问(NUMA)是一种用于多处理器的电脑记忆体设计,内存访问时间取决于处理器的内存位置。在NUMA下,处理器访问它自己的本地存储器的速度比非本地存储器(存储器的地方到另一个处理器之间共享的处理器或存储器)快一些。  针对NUMA架构系统的特点,可以通过将进程/线程绑定指定CPU (一个或多个 ) 的方式,提高CPUCACHE的命中率,减少进程/线程迁移CPU 造成的内存访问的时间消耗,从而提高程序的运行效率。 1个进程可绑定到1个或多个CPU核,因为参数cpu_affinity的类型为uint64_t,其占用64位,所以可设置CPU核范围:第1~64个。 进程绑定CPU:

  • 跟我一起学Oracle 11g【2】----用户管理(转载)

    http://www.cnblogs.com/damonlan/archive/2012/07/14/2585583.html#4.1 ---------------------本期目录导航------------------ 一。为什么要学习Oracle二。SQL*Plus工具的使用    2.1打开SQL*Plus工具    2.2启动SQL*Plus三。用户操作    3.1默认用户    3.2创建用户    3.3授权(grant)     3.4收回权限    3.5修改用户密码    3.6删除用户四。Profile管理用户口令    4.1账户的锁定     

  • POJ 3258 最小值最大化 二分搜索

    题意:牛要到河对岸,在与河岸垂直的一条线上,河中有N块石头,给定河岸宽度L,以及每一块石头离牛所在河岸的距离,          现在去掉M块石头,要求去掉M块石头后,剩下的石头之间以及石头与河岸的最小距离的最大值。 首先去理解题意,去除一些石头之后,使得跳跃的最短距离是最大的,这个跳跃的距离一定是一个值而且一定小于总距离,同时我们可以知道的是,如果移除某几块石头,以某一最短距离跳跃都满足的话,小于这个最短距离的话一定都满足,大于这个最短距离便不一定,所以二分搜索的好处在于可以精准地通过之前的判断对下一次的范围进行锁定,进行判断,确保获得最大的最短距离。进行判断的时候我们可以通过不断地顺序试探,如果跳跃距离小于要求的最短距离,则需要将移除的石头加一。并且之后的距离就是将这块石头移除之后的距离,注意这里就有一个顺序。从前往后。我在做本题时主要对终点的那段距离抱有疑惑,其实终点那段虽然终点不能移除,但只要要移除的石头数小于等于n,就可以通过移除之前的石头实现。如果要移除n+1块石头那显然也不符合m&l

  • 微信公众号开发 (福利贴)(微信支付不得不说的坑)

      最近刚接触的微信公众号,看了半天的Api文档,直接就上手开发了,用了几天的时间,结束了公众号支付的任务。   首先,需要准备的东西是:1、微信公众号;2、支付申请;3、公众号配置(坑);4、开发。   微信公众号申请   一般开通就行了,https://mp.weixin.qq.com,度娘一下就行了;此处可以省略;   支付申请   要缴费才给开通,之后上传相关的资料,审核通过之后,一般一个多星期就能够搞定;   公众号配置   (1)【配置oAuth2网页授权】,这个需要申请公众号开发者【开发】-【接口权限】-【网页授权】-【修改】-【网页授权域名】注意,该域名填写,必须严格按照提示填写,目前的格式是:域名(不带http://或者https://),例如:www.baidu.com,对了,这里只要是备案过的域名,不分一二级域名;   (2)【支付目录配置】,这个分两种【支付授权目录】和【测试授权目录】,第一种是正式的支付授权目录,mvc框架的话,这种精确至Controller,例如:http://www.baidu.com/Pay/,第二种也跟前一种差不多,只是需要添加测试白名

  • PTA 统计一行文本的单词个数

    本题目要求编写程序统计一行字符中单词的个数。所谓“单词”是指连续不含空格的字符串,各单词之间用空格分隔,空格数可以是多个。 输入格式: 输入给出一行字符。 输出格式: 在一行中输出单词个数。 输入样例: Let'sgotoroom209. 复制   输出样例: 5复制 #include<bits/stdc++.h> usingnamespacestd; intmain(){ strings; intcnt=0,i,f=0; getline(cin,s); for(i=0;i<s.length();i++){ if(s[i]!=''){ f=1; }elseif(f==1&&s[i]==''){ f=0; cnt++; } } if(s[s.length()-1]!=''){ cnt++; } cout<<cnt; return0; }复制   本文来自博客园,作者:YEdifier,转载请注明原文链接:https://www.cnblogs.com/8023yyl/p/16156953.html

相关推荐

推荐阅读