Leetcode 179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

【题意】

给定一个数组，这些数连在一起可以组成一个大数，求能组成最大数。

如 [3, 30, 34, 5, 9] 能组成的最大数为 9534330。

由于组成的数可能非常大，用字符串返回。

【解法】

关键是确定每个数在最后结果中的先后位置，比较直观的是个位数越大的越靠前，如例子中9在5, 4, 3之前；

个位相同的再看十位，如例子中34应当在30之前；

难点是位数不等时，先后关系怎么确定？如例子中3应当放在30和34之前、之后还是中间？

结果是3放在了34和30中间，为什么呢？这是因为十位上的4比个位上3大，所以34在3之前，而十位上的0比个数上的3小，所以30在3之后。

这样貌似可以找到规律，就是对于那些有包含关系的数，如1234包含12，那么只需看1234比12多出的部分34比12大还是小。

通过这样的方法，貌似也可判断出个先后顺序。只是这样需要考虑的情况太复杂了，如565656和56……

//正解如下：

可以换一下思路，要想比较两个数在最终结果中的先后位置，何不直接比较一下不同组合的结果大小？

举个例子：要比较3和34的先后位置，可以比较334和343的大小，而343比334大，所以34应当在前。

这样，有了比较两个数的方法，就可以对整个数组进行排序。然后再把排好序的数拼接在一起就好了。

class Solution {
public:
    static bool cmp(string a, string b) 
    {  
        return a + b > b + a;  
    }
    string largestNumber(vector<int>& nums) {
        vector<string> arr;  //定义一个string容器
        for(auto i:nums)     // 需要将int容器里的每一个数字转化为string
           arr.push_back(to_string(i));
        // 对string里的元素排序，依据是 任意两个string连接之后
        sort(begin(arr),end(arr),cmp);
        string res;         // 存放结果
        for(auto s:arr)
           res += s;        // 将结果进行连接起来
        while(res[0] == '0' && res.length()>1)// 对特殊情况的处理
           res.erase(0,1);  //每次删除第一位的0，注意erase的用法
        return res;
    }
};
//要使用cmp函数来排序 比较规则是x+y 和y+x的大小 而且要倒序
//同时要注意[0,0]这种特殊情况

public:
    string largestNumber(vector<int>& nums) {
        vector<string> arr;  //定义一个string容器
        for(auto i:nums)     // 需要将int容器里的每一个数字转化为string
           arr.push_back(to_string(i));
        // 对string里的元素排序，依据是 任意两个string连接之后
        sort(begin(arr),end(arr),[](string &s1, string &s2){return s1+s2 > s2+s1;});
        string res;         // 存放结果
        for(auto s:arr)
           res += s;        // 将结果进行连接起来
        while(res[0] == '0' && res.length()>1)// 对特殊情况的处理
           res.erase(0,1);  //每次删除第一位的0，注意erase的用法
        return res;
    }
};
//要使用cmp函数来排序 比较规则是x+y 和y+x的大小 而且要倒序
//同时要注意[0,0]这种特殊情况

其中，这两种写法都对。其中要注意几个点：

1. to_string()函数返回字符串形式

#include<iostream>
#include<string>
using namespace std;

int main()
{
    int i=123;

    //aastring s=to_string(134) + "abc";
    string s=to_string(i) + "abc";

    cout<<s<<endl;
    
    system("pause");
    return 0;
}

运行结果： 123abc

2. sort 函数入门：

（1）使用sort需要包含algorithm头文件，完整代码如下

#include<iostream>
#include<vector>
#include<algorithm>//貌似可以不用，但最好加上。
using namespace std;
int main()
{
    vector<int>v;
    v.push_back(13);
    v.push_back(23);
    v.push_back(03);
    v.push_back(233);
    v.push_back(113);
    sort(v.begin(),v.end());
    int i=0;
    for(i=0;i<5;i++)
    {
        cout<<v[i]<<endl;
    }
    system("pause");
    return 0;
}

运行结果如下：

3
13
23
113
233
请按任意键继续. . .

可以看到结果是从小到大排序，但如果我需要从大到小排序呢？

（2）改写comp从大到小排序。加入comp函数后代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool comp(const int &a,const int &b)
{
    return a>b;
}
int main()
{
    vector<int>v;
    v.push_back(13);
    v.push_back(23);
    v.push_back(03);
    v.push_back(233);
    v.push_back(113);
    sort(v.begin(),v.end(),comp);
    int i=0;
    for(i=0;i<5;i++)
    {
        cout<<v[i]<<endl;
    }
    system("pause");
    return 0;
}

运行结果：

233
113
23
13
3
请按任意键继续. . .

为什么会这样呢？比较时sort函数根据comp函数进行判断输的大小，系统默认a<b时返回真，于是从小到大排，而我的comp函数设定为a>b时返回为真，那么最终得到的排序结果也相应的从小到大变成从大到小。简单吧~~

（3）对结构体排序

有了comp函数我们就可以实现对任意结构体任意对象进行排序，只需要对应修改comp函数即可实现。代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct ss
{
    int a,b;
};
bool comp(const ss &a,const ss &b)
{
    return a.a<b.a;
}
int main()
{
    vector<ss>v;
    ss s1,s2,s3,s4,s5;
    s1.a=4;s1.b=23;
    s2.a=1;s2.b=213;
    s3.a=2;s3.b=231;
    s4.a=5;s4.b=123;
    s5.a=3;s5.b=223;
    v.push_back(s1);
    v.push_back(s2);
    v.push_back(s3);
    v.push_back(s4);
    v.push_back(s5);
    sort(v.begin(),v.end(),comp);
    int i=0;
    for(i=0;i<5;i++)
    {
        cout<<v[i].a<<" "<<v[i].b<<endl;
    }
    system("pause");
    return 0;
}

比如ss结构体中a代表的是索引号，b代表的是索引对应的值，那么我想按索引排序，通过改写comp函数即可实现。

结果：

1 213
2 231
3 223
4 23
5 123
请按任意键继续. . .

3. erase函数的原型如下：（1）string& erase ( size_t pos = 0, size_t n = npos );

（2）iterator erase ( iterator position );

（3）iterator erase ( iterator first, iterator last );也就是说有三种用法：

（1）erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符

（2）erase(position);删除position处的一个字符(position是个string类型的迭代器)

（3）erase(first,last);删除从first到last之间的字符（first和last都是迭代器）

#include <string>
#include <iostream>
using namespace std;
 
int main ()
{
    string str ("This is an example phrase.");
    string::iterator it;
    //第（1）种方法
    str.erase (10,8);
    cout << str << endl;        // "This is an phrase."
    //第（2）种方法
    it=str.begin()+9;
    str.erase (it);
    cout << str << endl;        // "This is a phrase."
    //第（3）种方法
    str.erase (str.begin()+5, str.end()-7);
    cout << str << endl;        // "This phrase."
    return 0;