剑指 Offer 46. 把数字翻译成字符串 C++

剑指 Offer 46. 把数字翻译成字符串 C++ 2022-05-22 620

先转成字符串再组合

思路描述：

首先我们要明白就是

无论这些数字怎么取排列，形成的数字的位数是不变的那么就是高位的数字肯定是越小越好。

我们先考虑一下怎么排列两个数字，比如 1 和 20，高位越小越好，放 1，组合成 120

我们再看一下三个数的情况，比如 36、38 和 5，首先肯定先放 36，剩下 38 和 5，然后对这两个数进行排列 385，所以最后的结果为 36385。

由上面的两个例子我们其实就可以知道，放数字的顺序肯定是先放第一位(最左边一位)最小的元素，如果第一位相等，比较第二位....，以此类推。

我们再思考一下，36 < 38 > 5 ，但是 "36" < "38" < "5"，

也就是我们如果把所有数字转换成字符串再排列，刚好就是我们希望的情况。

注意：我们这里说的排列大小比较和字符串大小有点区别，比如 3 和 30，明显 30 排在前面比较好，所以我们要重构比较，我们组合 s1 和 s2 ，如果 s1 + s2 > s2 + s1，那么 s1 > s2

至此，我们已经分析出来了。

class Solution {
public:
    string minNumber(vector<int>& nums) {
        auto compare = [](string a , string b ){return a+b < b+a; };    //函数对象，也可写在类外
        vector<string> str;
        string res;
        for(int num : nums){
            str.push_back(to_string(num));
        }
        sort(str.begin(),str.end(),compare);    //重构比较
        for(string s:str){
            res+=s;
        }
        return res;
    }
};