Leetcode 179 Largest Number 贪心

时间:2021-01-26 11:56:16

此题主要是讲给你一组数,如何将数连在一起能得到最大值(最小值反之),注意局部最优,就是说如果 123 234两个连在一起怎么样最大,显然是234123比123234大,对于3个数我们可以找到类似的性质,4个数一样。。。因此我们得到这个局部最优的排序是全局最优的。因此这个实现最核心的代码就是函数cmp,其他的就是要注意全是0的情况和前导0的情况,这题就轻松解决。

 inline bool cmp(const std::string &a, const std::string &b)
{
return a + b > b + a;
}
class Solution
{
public:
Solution() = default;
~Solution() = default;
inline std::string inttostr_(int num)
{
char s[] = { };
sprintf_s(s,"%d",num);
return std::string(s);
} std::string largestNumber(std::vector<int>& nums)
{
std::vector<std::string> vstr;
for (std::vector<int>::size_type i = ; i < nums.size(); ++i){
vstr.push_back(inttostr_(nums[i]));
}
std::sort(vstr.begin(),vstr.end(),cmp);
std::vector<std::string>::size_type i = ;
for (; i < nums.size(); ++i){ //删除前导0
if (vstr[i] != "") break;
} if (i == nums.size()) return "";//全是0
else{ //前导0和其他情况
std::string ans("");
for (; i<nums.size(); ++i){
ans += vstr[i];
}
return ans;
}
}
};