179. 最大数（LeetCode）

2024-04-28 22:36

文章标签 leetcode 最大数 179

本文主要是介绍179. 最大数（LeetCode），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

前言
一、题目讲解
二、算法原理
三、代码编写
- 1.仿函数写法
- 2.lambda表达式
四、验证
五.总结

前言

在本篇文章中，我们将会带着大家采用贪心的方法解决LeetCode中最大数这道问题！！！

一、题目讲解

在这里插入图片描述

一组非负整数，包括0，要求把这些数合并起来，形成一个最大的整数。
我们具体来看看一下示例1：
两个整数，10，2。可以组成的情况有两种，102和210。
由于210大于102，所以我们返回210.

可能有很多数，拼接起来就非常大，超出整形的范围，所以要求我们最终按照字符串形式返回。

二、算法原理

本质：确定元素的先后顺序，谁在前，谁在后

我们首先来回顾一下我们之前学过的排序算法,我们以降序为例

两个数a和b：
🌟如果a>b，a在前，b在后
🌟如果a=b，a,b谁在前无所谓
🌟如果a<b，b在前，a在后

我们在来看一下本道题，也是一种排序规则，
两个数a和b:
🌟如果ab>ba，a在前，b在后
🌟如果ab=ba，a,b谁在前无所谓
🌟如果ab<ba，b在前，a在后
我们知道了这里，只需要把库里的排序函数按照我们的规则进行排序就可以实现了

贪心：谁比较好，把谁放在前面

三、代码编写

优化：把数转化成字符串，拼接字符串，比较字典序

我们可能遇到这种情况，nums[ ]={0,0,0};
最终我们拼接完成之后就是：“000”。

这时我们直接返回字符串0就可以。

1.仿函数写法

class Solution {
public://仿函数struct cmp{bool operator()(string&s1,string&s2){return s1+s2>s2+s1;}};string largestNumber(vector<int>& nums) {vector<string> v;//转化成字符串for(auto&e:nums){v.push_back(to_string(e));}//按照我们的升序规则进行排序//注意比较的cmp怎莫写sort(v.begin(),v.end(),cmp());//连接string str;for(auto&e:v){str+=e;}//特殊处理if(str[0]=='0'){return "0";}else {return str;}}
};

2.lambda表达式

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> v;//转化成字符串for(auto&e:nums){v.push_back(to_string(e));}//按照我们的升序规则进行排序//注意比较的cmp怎莫写sort(v.begin(),v.end(),[](string&s1,string&s2){return s1+s2>s2+s1;});//连接string str;for(auto&e:v){str+=e;}//特殊处理if(str[0]=='0'){return "0";}else {return str;}}
};

四、验证

我们从一堆数中任意选择两个元素，按照我们的规则，如果满足全序关系就可以排序。

首先介绍一下全序关系的三个性质
🌟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;

我们只要证明了我们的关系满足这三个性质，就可以进行排序
证明：
我们假设a有x位，b有y位
🌟1.完全性
在这里插入图片描述