Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input:[10,2]
Output: "210"
Example 2:
Input:[3,30,34,5,9]
Output: "9534330"
Note: The result may be very large, so you need to return a string instead of an integer.
A:
就是简单的两个int 按照string的方式对比。---------核心是如果前边相等,则取其substring,继续比较因此自己写了一个 comparator method (不能用通常的struct. 因为需要递归调用)
class Solution { public: string largestNumber(vector<int>& nums) { priority_queue<string, vector<string>, decltype(compare)* > P(&compare); for(auto k : nums) P.push(to_string(k)); string res; while(not P.empty()) { res += P.top(); P.pop(); } return res[0]=='0'? "0" : res; } private: static bool compare(const string& a, const string& b) { for(int i =0;i<min(a.length(), b.length()); ++i) { if(a[i] != b[i]) return a[i] < b[i]; } if(a.length() == b.length()) // when two are the same, return false return false; else if(a.length() > b.length()) return compare(a.substr(b.length()), b); else return compare(a,b.substr(a.length())); } };
Mistakes:
1 : compare函数一开始没有没有注意,因为我们要的是max Heap, 因此要按照 a < b . 默认是max_heap
2:compare函数中,如果s1,s2 之前的都相同。那么要对比的是取下来的和 另外一个短的全部。
3: 输入是 0, 0 , 输出应该是0. 因此这里要检查最后结果的首位。(又错了,哎)
No comments:
Post a Comment