贪心算法学习——最大数

目录

​编辑

一，题目

二，题目接口

三，解题思路级代码

---

一，题目

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

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

二，题目接口

class Solution {public:string largestNumber(vector<int>& nums) {}};

三，解题思路级代码

这道题其实很好解决，关键步骤如下：

1.将我们的每一个数字转换成string类型的元素（注意不要转换为char类型，因为char类型转换时看的是ASSICA码）。

2.在将我们的数字转换成为字符串以后，我们便可以使用sort函数重写一个比较函数便可以得到答案了。

比较规则：

    首先我们先设两个数：a,b。先组成一个数ab.如果ab>ba那我们便可以不改变字符a和b的位置。如果ab<ba那我们就要改变位置变为ba。对于每一个字符串，sort函数都会使用字典序的方式帮我们排序。

代码如下：

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string>num;for(int i = 0;i<nums.size();i++)//将数字转换成为string类型。{num.push_back(to_string(nums[i])) ;}sort(num.begin(),num.end(),[](const string& s1,const string& s2)//重新实现一个比较规则{return s1+s2>s2+s1;});string str;if(num[0] == "0")//如果第一个数字都是"0"的话那就肯定是一个0或者一串0的字符串。{return "0";//返回0}for(auto e:num)//如果不是那就取出str中的元素，给到str然后返回str。{str+=e;}return str;}
};

当然，在sort函数中重新实现的比较规则可能比较抽象，现在来个正常的：

class Solution {
public:static bool compare(const string& s1,const string s2)//重定义比较函数{return s1+s2>s2+s1;}string largestNumber(vector<int>& nums) {vector<string>ret;for(int i = 0;i<nums.size();i++){ret.push_back(to_string(nums[i]));}sort(ret.begin(),ret.end(), compare);//使用sort实现排序string str;for(auto& x:ret){str+=x;}if(str[0] == '0'){return "0";}return str;}
};