LintCode-最大数

给出样例 [1, 20, 23, 4, 8]，返回组合最大的整数为8423201

最后的结果可能很大，所以我们返回一个字符串来代替这个整数

分析：这个其实是一个排序问题，当然首字母越大肯定应该排在前面，注意【20，201】【20,203】两种情况，第一种201应该在20后面，第二种203应该在20前面。

代码：

bool cmp(string s1,string s2)
    {
        int i=0;
        while(i<min(s1.length(),s2.length()))
        {
            if(s1[i]>s2[i])
                return true;
            else if(s1[i]<s2[i])
                return false;
            i++;
        }
        if(i==s1.length())
            return s2[i]>s2[0]?false:true;
        if(i==s2.length())
            return s1[i]>s1[0]?true:false;
    }

class Solution {
public:
    /**
     *@param num: A list of non negative integers
     *@return: A string
     */
    
    string toString(int x)
    {
        if(x==0)
            return "0";
        string ret = "";
        while(x>0)
        {
            char c  = x%10+'0';
            ret = c+ret;
            x/=10;
        }
        return ret;
    }
    string largestNumber(vector<int> &num) {
        // write your code here
        int sum  = accumulate(num.begin(),num.end(),0);
        if(sum==0)
            return "0";
        vector<string> nums;
        for(int i=0;i<num.size();i++)
        {
            nums.push_back(toString(num[i]));
        }
        sort(nums.begin(),nums.end(),cmp);
        string ret = "";
        for(int i=0;i<nums.size();i++)
            ret+=nums[i];
        return ret;
    }
};