C++ Solution 3ms (with Strange idea)


  • 0
    Q

    I have a strange idea, and it passed all the test cases.

    class Solution {
    public:
        struct twostr{
            string s1;
            string s2;
            twostr(string a, string b)
            {
                s1 = a;
                s2 = b;
            }
        };
        static bool compare(twostr a, twostr b)
        {
            return a.s2 < b.s2;
        }
        string largestNumber(vector<int>& nums) {
            int maxlen = 0;
            int maxval = 0;
            vector<twostr> strvec;
            for (int i = 0; i < nums.size(); i++)
            {
                string s = to_string(nums[i]);
                if (s.length() > maxlen) maxlen = s.length();
                if (nums[i] > maxval) maxval = nums[i];
                strvec.push_back(twostr(s,s));
            }
            if (maxval == 0) return "0";
            maxlen *= 2;
            for (auto &astr: strvec)
            {
                if (astr.s2.length() + astr.s1.length() <= maxlen)
                {
                    while (astr.s2.length() + astr.s1.length() <= maxlen)
                        astr.s2.append(astr.s1);
                }
                if (astr.s2.length() < maxlen)
                {
                    astr.s2.append(astr.s1, 0, maxlen - astr.s2.length());
                }
            }
            sort(strvec.begin(),strvec.end(),compare);
            string resstr = "";
            for (int n = strvec.size() - 1; n >= 0; n--)
                resstr.append(strvec[n].s1);
            return resstr;
        }
    };
    

    Key point is: in the struct named "twostr", s1 is original string, and s2 is a "possible extend" of s1. Then sort vector by comparing s2.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.