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;
原文：http://www.cnblogs.com/simplepaul/p/6671027.html