LeetCode 179. 最大数
题目描述
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2]
输出："210"
示例 2：
输入：nums = [3,30,34,5,9]
输出："9534330"
示例 3：
输入：nums = [1]
输出："1"
示例 4：
输入：nums = [10]
输出："10"
提示：
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 109
解题思路
显然这是一道排序题，肯定不能直接 dfs 枚举全部的结果进行比较，毕竟结果都需要用字符串存了，枚举数量太大。
排序的话，第一位数字就不同好说，大的在前；第一位相同看第二位，要是不同的话，还是大的在前；要是还相同就继续看，直到看到不同的位进行比较。
但是这里有一个问题，如果有一个数字比较短，另一个比他长，但是短数和长数的前面部分完全相同怎么比？
我们尝试举几个例子寻找灵感。[3,32] 是 3 在前，[3,35] 是 35 在前；[3,332] 是 3 在前，[3,335] 是 335 在前 ……
一位数字或许不够有代表性，换个两位数来看。[43,432] 是 43 在前，[43,435] 是 435 在前；[43,43432] 是 43 在前，[43,43435] 是 43435 在前 ……
可以看到，其实我们比较的时候，是先比较短数的位数，相同时再比较下一段短数的位数，还是相同就再比较下一段短数的位数，直到比较出结果。这不就是递归嘛！
注意：
- 想法的两个数，或者长数的每一段都和短数相同的两个数，谁在前谁在后都可以；
- 数组元素全 0 的时候，输出不应该是一串 0 而是一个 0。
参考代码
/*
* @lc app=leetcode.cn id=179 lang=cpp
*
* [179] 最大数
*/
// @lc code=start
class Solution {
public:
string largestNumber(vector<int>& nums) {
bool all0 = true;
for (int x : nums)
if (x != 0) all0 = false;
if (all0) return "0";
vector<string> strs;
for (int x : nums) {
strs.push_back(to_string(x));
}
sort(strs.begin(), strs.end(), cmp);
string res;
for (auto&& s : strs) {
res += s;
}
return res;
}
static bool cmp(const string& a, const string& b) {
size_t al = a.size(), bl = b.size();
size_t i;
for ( i = 0; i<al && i<bl; i++) {
if (a[i] > b[i]) return true;
if (a[i] < b[i]) return false;
} // 5 9
if (al == bl) return true; // a == b
if (i == al) return cmp(a, b.substr(i)); // 3 34 vs. 3 32
else return cmp(a.substr(i), b);
} // AC
};
// @lc code=end