lettcode179.最大数

问题描述:

给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例一:

输入nums = [10,2]
输出:"210"

示例二:

输入nums = [3,30,34,5,9]
输出:"9534330"

 问题解决:

这道题其实是一个自己指定排序规则的排序,而排序的过程就是贪心算法的体现,排序规则如下:

我们这里一数组里有两个数为例,分别是a和b

(1)ab  > ba(这里的ab是将数据b添加到数据a的前面) ——> a在前,b在后  

(2)ab = ba ——> 无所谓

(3)ab < ba——>b在前,a在后

其实这些比较就是贪心策略的体现。

那么这一个排序规则,为这么可以正确排序呢?

证明排序规则的排序是正确的:

证明方法:全序关系

什么事全序关系?

1.完全性:

设有两个元素a和b,一定要保证这两个元素是可以比大小的,

例如:a <= b 或者 a >= b

2.反对称性:

设有a,b两个元素,满足:

a <= b && a >= b ——> a = b

对应到本题中就是:

a在前 && b在后 ——>无所谓

3.传递性:

设有三个元素a,b,c,其满足:

a >= b && b>= c ——> a >= c

这个事最重要也是最难证明的一个。

接下来来使证明:

1.证明完全性:
2.证明反对称性:

3.证明传递性:

所以满足全序关系,说明我们规定的排序是正确的。

最后,题目要求输出的是字符串,所以有一个优化是可以在开始就将数组中的数字全部转化成字符

串,同时这样也有利于排序的比较,不用将整形数字拆分来比较,直接比较即可。

接下来就是代码的编写:

class Solution 
{
public:
    string largestNumber(vector<int>& nums) 
    {
        //优化:将所有的数转换成字符串
        vector<string> strs;
        for(int x :nums)
        {
            strs.push_back(to_string(x));
        }

        //排序:
        sort(strs.begin(),strs.end(),[](const string& s1,const string& s2)
        {
            return s1 + s2 > s2 + s1;
        });

        //提取结果;
        string ret;
        for(auto& s: strs)
        {
            ret += s;
        }
        if(ret[0] == '0')
        {
            return "0";
        }
        return ret;
    }
};

这就是这到题的详细解析。 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/555174.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

街景图片语义分割后像素类别提取,用于计算各种指标。

语义分割代码见之前博文&#xff08;免费&#xff09;&#xff1a;deeplabv3街景图片语义分割&#xff0c;无需训练模型&#xff0c;看不懂也没有影响&#xff0c;直接使用。cityscapes 语义分割之后&#xff0c;如下图&#xff0c;想要统计各类像素所占的比例&#xff0c;用于…

2024 MathorCup C 题 物流网络分拣中心货量预测及人员排班

一、问题重述 电商物流网络在订单履约中由多个环节组成&#xff0c;图1是一个简化的物流网络示意图。其中&#xff0c;分拣中心作为网络的中间环节&#xff0c;需要将包裹按照不同流向进行分拣并发往下一个场地&#xff0c;最终使包裹到达消费者手中。分拣中心管理效率的提升&…

初识 React:安装和初步使用指南

文章目录 前言一、React 是什么&#xff1f;1.组件化开发2.虚拟 DOM3.单向数据流4.生态系统丰富 二、安装1.准备工作2.下载react 三、探索 React 应用总结 前言 在当今的 Web 开发领域&#xff0c;React 已经成为了一个备受推崇的技术。它的组件化、灵活性和高效性使得它成为了…

MySQL中InnoDB的行级锁

InnoDB 实现了以下两种类型的行锁。 共享锁&#xff08;S&#xff09;&#xff1a;又称为读锁&#xff0c;简称S锁&#xff0c;共享锁就是多个事务对于同一数据可以共享一把锁&#xff0c;都能访问到数据&#xff0c;但是只能读不能修改。 排他锁&#xff08;X&#xff09;&am…

时间同步服务项目练习

一.配置server主机要求如下&#xff1a; 1.server主机的主机名称为 ntp_server.example.com 2.server主机的IP为&#xff1a; 172.25.254.100 3.server主机的时间为1984-11-11 11&#xff1a;11&#xff1a;11 4.配置server主机的时间同步服务要求可以被所有人使用 更改主机名…

Android开发基础:Activity之间的跳转 向下一个Activity传递数据 给上一个Activity返回数据

目录 一&#xff0c;使用Intent在Activity之间跳转 1.显示使用Intent 2.隐式使用Intent 二&#xff0c;携带数据的跳转 1.Bundle 三&#xff0c;返回数据给上一个Activity 1.registerForActivityResult 一&#xff0c;使用Intent在Activity之间跳转 一个Android应用中包…

APEX开发过程中需要注意的小细节5.5

oracle保留小数点后两位的函数 在日常开发中经常用到百分比做数据对比&#xff0c;但是有可能得到的数据是一个多位小数&#xff0c;结果如下所示&#xff1a; 如果想截取部分小数如保留小数点后两位可以怎么做呢&#xff1f; 在Oracle中&#xff0c;可以使用ROUND函数来四舍…

请警惕,这10本期刊已被SCI剔除,部分涉嫌灌水

科睿唯安于4月15日更新了SCIE、SSCI、AHCI、ESCI四大数据库最新收录期刊目录。 2024年第一版——2024年1月24日更新 2024年第二版——2024年2月19日更新 2024年第三版——2024年3月18日更新 2024年第四版——2024年4月15日更新 本次目录中共收录期刊23368本。 【SCIE数据…

档案集中管理的痛点怎么解决?

档案集中管理可能面临的痛点包括以下几个方面&#xff1a; 1. 档案分类和整理困难&#xff1a;档案集中管理会面临大量档案的分类和整理工作&#xff0c;可能导致混乱和困难。 解决方法&#xff1a; - 建立统一的档案分类规范和流程&#xff0c;确保所有档案都能按照规定的方式…

《QT实用小工具·二十九》托盘图标控件

1、概述 源码放在文章末尾 托盘图标控件 可设置托盘图标对应所属主窗体。 可设置托盘图标。 可设置提示信息。 自带右键菜单。 下面是demo演示&#xff1a; 项目部分代码如下&#xff1a; #ifndef TRAYICON_H #define TRAYICON_H/*** 托盘图标控件* 1. 可设置托盘图标…

Unity类银河恶魔城学习记录12-17 p139 In game UI源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili UI.cs using UnityEngine;public class UI : MonoBehaviour {[SerializeFie…

仿真科普|从设计到研发,CAE仿真技术为汽车智造保驾护航

2024年3月28日&#xff0c;对于汽车产业来说&#xff0c;是历史性的一天&#xff0c;作为近年汽车行业发布会流量最大的一次&#xff0c;小米SU7的发布让整个汽车圈为之沸腾&#xff0c;成功收割全平台热搜。时至今日&#xff0c;小米汽车依然热度不减。 随着“蔚、小、理、特…

Docker镜像,什么是Docker镜像,Docker基本常用命令【搜索,镜像下载,镜像删除,创建容器,导入到处镜像】及其镜像的分层

docker镜像 1.1什么是镜像&#xff0c;镜像基础 1.1.1 镜像的简介 镜像是一种轻量级&#xff0c;可执行的独立软件包&#xff0c;也可以说是一个精简的操作系统。镜像中包含应用软件及应用软件的运行环境&#xff0c;具体来说镜像包含运行某个软件所需的所有内容&#xff0c;…

4*5的矩阵(C语言)

一、N-S流程图&#xff1b; 二、运行结果&#xff1b; 三、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int i 0;int j 0;int result 0;//嵌套循环输出&#xff1b;for (i 1; i < 4; i){//列…

基于Python dlib的实时人脸识别,附源码

博主介绍&#xff1a;✌IT徐师兄、7年大厂程序员经历。全网粉丝15W、csdn博客专家、掘金/华为云//InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3…

Linux进程与管理,计划任务

1.虚拟内存统计 vmstat可以用来监控CPU使用&#xff0c;进程状态&#xff0c;内存使用&#xff0c;虚拟内存使用&#xff0c;硬盘输入输出状态等信息。 字段解释&#xff1a; procs进程信息&#xff1a;r&#xff1a;等待运行的程序数&#xff1b;b&#xff1a;不可被唤醒的进…

【电控笔记3.5】三相逆变器

基础 大小调变指标ma 频率调变指标mf 载波频率:pwm频率

wps导出pdf文献引用不能跳转解决办法

问题描述 本科论文参考文献使用wps设置交叉引用&#xff0c;但导出pdf后无法跳转引用 尝试 用office word打开文件word版跳转没有问题&#xff0c; 另存为pdf或导出pdf。 但是pdf版跳转完全错误。 16跳到14.但是总体而言都是跳到包含该序号的页 要求不高的话也可以&#x…

【IC前端虚拟项目】接口分析与agent组件生成

【IC前端虚拟项目】数据搬运指令处理模块前端实现虚拟项目说明-CSDN博客 到目前为止关于环境的准备工作都已经完成了,甚至验证环境的大体结构我们也已经画好了,再来看一下: 于是乎呢就可以大张旗鼓的开始咱们验证环境的搭建了!看上面这个结构图,里面除了mvu作为DUT,其他…

④【Shiro】Shiro框架进行敏感信息加密

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ ④【Shiro】Shiro框架进行敏感信息加密 实际系…