贪心算法学习——最大数

目录

​编辑

一，题目

二，题目接口

三，解题思路级代码

一，题目

给定一组非负整数 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;
    }
};