Leetcode Largest Number c++ solution

Total Accepted: 16020 Total Submissions: 103330

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

会超过内存限制；把string改成char *就过了，但很难看!

    bool comp(const string& a, const string& b) {

        string x = a, y = b;

        int diff = x.length() - y.length();

        if (diff > 0) {

            char c = y[0];

            y.insert(y.end(), diff, c);

        } else if (diff < 0) {

            char c = y[0]; //lastChar(x);

            x.insert(x.end(), -diff, c);

        }

        for (int i = 0; i < x.length(); i++) {

            if (x[i] < y[i])    return false;

            if (x[i] > y[i])    return true;

        }

        return comp(a+b, b+a);

    }

class Solution {

public:

    string largestNumber(vector<int> &num) {

        int len = num.size();

        string* snum = new string[len];

        for (int i = 0; i < len; i++) {

            snum[i] = to_string(num[i]);

        }

        stable_sort(snum, snum + len, comp);

        string ret;

        int i = 0;

        for (; i < len && snum[i] == "0"; i++);

        for (; i < len; i++)

            ret += snum[i];

        return ret.empty() ? "0" : ret;

    }

};

把string改成char*

    #define MAX_BUF 10

    bool comp(char* a, char* b) {

        char* x = a,  *y = b;

        char *short_, c[2];

        int diff = strlen(x) - strlen(y);

        short_ = diff > 0 ? y : x;

        sprintf(c, "%c", short_[0]);

        for (int i = 0; i < abs(diff); i++)

            strcat(short_, c);

        int len = strlen(x);

        auto restore = [&]() {

            for (int i = 0; i < abs(diff); i++)

                short_[len - 1 - i] = '\0';

        };

        for (int i = 0; i < len; i++) {

            if (x[i] < y[i])    {

                restore();

                return false;

            }

            if (x[i] > y[i])    {

                restore();

                return true;

            }

        }

        restore();

        if (strlen(x) == strlen(y)) return false;

        char temp1[MAX_BUF*2], temp2[MAX_BUF*2];

        sprintf(temp1, "%s%s", a, b);

        sprintf(temp2, "%s%s", b, a);

        return comp(temp1, temp2);

    }

class Solution {

public:

    string largestNumber(vector<int> &num) {

        int len = num.size();

        char** snum = new char*[len];

        for (int i = 0; i < len; i++) {

            snum[i] = new char[MAX_BUF];

            sprintf(snum[i], "%d", num[i]);

        }

        sort(snum, snum + len, comp);

        string ret;

        int i = 0;

        for (; i < len && strcmp(snum[i],"0") == 0; i++);

        for (; i < len; i++)

            ret += snum[i];

        return ret.empty() ? "0" : ret;

    }

};

重点来了，用python只需要几行

class Solution:

    # @param num, a list of integers

    # @return a string

    def largestNumber(self, num):

        num = sorted([str(x) for x in num], cmp = self.compare)

        ans = ''.join(num).lstrip('0')

        return ans or '0'

    def compare(self, a, b):

        return [1, -1][a + b > b + a]

巴特西

Leetcode Largest Number c++ solution

最新文章

热门文章