Leetcode(8)Largest Number(剣指offer 33題配列を最小にする数)

タイトルの説明
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.
本題の要件は配列を与え,配列の要素に基づいて新しい数を構成し,その数を最大にすることである.剣指offerにも同じ問題があるが、本には最小の数が要求されているが、実はこの2つは同じだ.
問題を解く構想.
テーマの要求によって、配列の中の数字をソートすることに相当し、ここでのソートは簡単に数字の大きさでソートすることはできません.例えば、30>9ですが、組み合わせた後の309は明らかに903より小さいです.したがって、高位から低位へのソートに似ています.ブロガーの最初の考え方は基数ソート(Radix Sort)の方法で実現したが、これは面倒だった(「アルゴリズム導論」に詳しい学生は、基数ソートも低位から高位にソートされ、数字の長さは同じであることを知っているはずだ).
しかし、ブロガーの前の分析によると、子供靴があるのはすでに考えているはずだが、2つの数字の大きさについては、彼らの組み合わせの結果に基づいて比較的長いokayを行っているのではないだろうか.上記のように309<903でソートした結果は30<9(...これは奇抜な小号で、子供靴たちが分かればいいのに...).上記の考え方ができた後,配列全体を一度に並べ替えて,すべての文字列を大きい順から小さい順に並べ替えるだけで問題は解決した.
ここではsort()関数を使用し、比較する関数をカスタマイズします.

bool compare_str(const string& s1, const string& s2)
{
    string sa = s1 + s2;
    string sb = s2 + s1;

    return sa > sb;
}
class Solution {
public:
    string largestNumber(vector<int> &num) {
        vector<string> str;     
        for (size_t i = 0; i != num.size(); ++i)
        {
            stringstream ss;
            ss << num[i];
            str.push_back(ss.str());
        }

        sort(str.begin(), str.end(), compare_str);

        if (str.size() > 0 && str[0] == "0")
        {
            return "0";
        }

        string r;
        for (size_t i = 0; i != str.size(); ++i)
            r.append(str[i]);

        return r;
    }
};

剣指offerのさらなる解釈(to-do)
上の考え方は剣指offerで提供されているのと同じですが、剣指offerではさらなる分析が提供されています.上記のアルゴリズムでは,この新しい定義の正しさ(自己反転性,対称性,伝達性,および得られた結果が最小数)をofferで証明する2つの数値サイズを比較する関数を独自に定義した.