Leet code 179 最大数
解题思路 贪心算法
贪心算法就是走一步看一步 每一步都取当前位置的最优解
这题我们该如何贪呢？
我们先把int数组转换为string数组
以示例2为例
3 30 34 5 9 排序哪个在前哪个在后？
3 + 30 （330）> 30 +3 （303） 那么3就在前 30在后
该题的贪心规律就是 a+b >b+a
通过sort 算法可以排序
然后还有一个特列处理 就是 全是0的情况下 只返回0
代码如下
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";
else return ret;
}
};