179. Largest Number ----- Medium !!!!!!!

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

 

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

 

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

A:

就是简单的两个int 按照string的方式对比。---------核心是如果前边相等，则取其substring，继续比较
因此自己写了一个 comparator method  (不能用通常的struct. 因为需要递归调用）

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        priority_queue<string, vector<string>, decltype(compare)*> queue(
            compare);
        for (auto a : nums)
            queue.push(to_string(a));
        string res;
        while (!queue.empty()) {
            auto top = queue.top();
            if (!(top[0] == '0' && res == ""))
                res += top;
            queue.pop();
        }
        return res == "" ? "0" : res;
    }
private:
    static bool compare(const string& a, const string& b) {
        if (a == b) {
            return true;
        }
        if (a.size() >= b.size()) {
            for (int i = 0; i < b.size(); i++) {
                if (a[i] == b[i]) {
                    continue;
                } else {
                    return a[i] < b[i];
                }
            }
            return compare(a.substr(b.size()), b);
        } else {
            return !compare(b, a);
        }
    }
};

------第二遍 。 关于comparator ，有更好的比较方法-------------------

class Solution {

public:

string largestNumber(vector<int>& nums) {

vector<string> V;

for (auto val : nums)

V.push_back(to_string(val));

sort(V.begin(), V.end(), [](const string& a, const string& b) {

return a + b < b + a; // in ascending order, since we pop from back

});

string res = "";

while (!V.empty()) {

auto s = V.back();

V.pop_back();

if (!(res == "" && s == "0"))

res += s;

}

return res == "" ? "0" : res;

}

};

Mistakes:
1 :  第一遍的时候， compare函数一开始没有没有注意，因为我们要的是max Heap， 因此要按照 a < b . 默认是max_heap

2：compare函数中，如果s1,s2 之前的都相同。那么要对比的是取下来的和 另外一个短的全部。

3:  In C++, "abb" < "abbc" evaluates to true.  Since, empty is less than anything

3：  输入是 0, 0 , 输出应该是0.  因此这里要检查最后结果的首位。(又错了，哎）



Learned:

In C++, to sort an array in reverse order, we do not need write our own Comparator (though we could)

See this page: https://www.geeksforgeeks.org/comparator-in-cpp/

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

int main() {

std::vector<int> nums{3, 4, 1, 8};

sort(nums.rbegin(), nums.rend()); // optimization: try big numbers first

for (auto a : nums) {

cout << a << " ";

}

return 0;

}

Will print : 8 4 3 1