首页 > 代码库 > 【LeetCode】Largest Number
【LeetCode】Largest Number
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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
这次关键在于排序compare，也就是怎样比较a和b的拼接顺序。
这样来考虑：
如果完全相同，那么返回false。
如果在相同位数下已经比较出结果，比如12 vs. 131，由于2<3，因此13112比12131来的大，返回true。
如果在相同位数下无法判断，比如12 vs. 1213。记相同部分为s1，后续部分为s2，就变成比较s1s2s1和s1s1s2的大小关系，转化为比较s1与s2的大小关系。
由于12<13，因此12<1213，应为121312而不是121213，返回true。
排完序只要逆序加就可以了（大的在前面），注意全0时简写为一个0.
class Solution {public: static bool compare(int a, int b) { string as = to_string(a); string bs = to_string(b); int sizea = as.size(); int sizeb = bs.size(); int i = 0; while(i<sizea && i<sizeb) { if(as[i] < bs[i]) return true; else if(as[i] > bs[i]) return false; i ++; } if(i==sizea && i==sizeb) return false; //equal returns false else if(i==sizea) //as finished return compare(atoi(as.c_str()), atoi(bs.substr(i).c_str())); else //bs finished return compare(atoi(as.substr(i).c_str()), atoi(bs.c_str())); } string largestNumber(vector<int> &num) { sort(num.begin(), num.end(), compare); int size = num.size(); string ret; while(size--) ret += to_string(num[size]); if(ret[0] != ‘0‘) return ret; else return "0"; }};
【LeetCode】Largest Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。