Sunday, March 1, 2015

179. Largest Number -M

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