Easy to understand DP C++ implementation but with TLE


  • 0

    As we can see, this problem is really fuck!!!

    Using directly with THE DP idea will cause TLE problem !!

    But it is also good for us to use the traditional DP ideas to solve this kind of problem.

    You can get the recursion equation from my code implementation.

    Here is the DP code implemented by myself without referring any others' post.

    Welcome your advice !

    Code :

     class Solution {
    public:
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            /**
             * dp[k][i][j] = max(nums1[i-1]+10*dp[k-1][i-1][j], nums2[j-1]+10*dp[k-1][i][j-1], 
             *                    dp[k][i-1][j-1])
             * 
             **/
            vector<int> result;
            int len1=nums1.size(), len2=nums2.size();
            if(len1+len2<k)  return result;
            vector<vector<vector<int>>> dp(2, vector<vector<int>>(len1+1, vector<int>(len2+1, 0)));
            for(int kk=0; kk<=k; kk++){
                for(int i=0; i<=len1; i++){
                    for(int j=0; j<=len2; j++){
                        if(kk==0)    
                            dp[0][i][j]=0;
                        else if(i==0 && j==0)   
                            dp[kk&1][0][0]=0;
                        else if(i==0){
                            if(kk>j)  
                                dp[kk&1][0][j]=0;
                            else 
                                dp[kk&1][0][j]=max(dp[kk&1][0][j-1], 10*dp[(kk-1)&1][0][j-1]+nums2[j-1]);
                        }
                        else if(j==0){
                            if(kk>i)  
                                dp[kk&1][i][0]=0;
                            else 
                                dp[kk&1][i][0]=max(dp[kk&1][i-1][0], 10*dp[(kk-1)&1][i-1][0]+nums1[i-1]);
                        }
                        else{
                             dp[kk&1][i][j] = max(max(nums1[i-1]+10*dp[(kk-1)&1][i-1][j], 
                                nums2[j-1]+10*dp[(kk-1)&1][i][j-1]), dp[kk&1][i-1][j-1]);
                        }   
                    }
                }
            }
            int value=dp[k&1][len1][len2];
            while(value>0){
                result.push_back(value%10);
                value=value/10;
            }
            reverse(result.begin(), result.end());
            return result;
        }
    };

  • 0

    by solving this problem, I also find that we can only use one-dimensional-rolling-array to compress the memory cost.


  • 2

    Here is the top-voted based C++ implementation by myself.

    I think the key idea is how to divide the original problem into 2 easy problem.

    first, It is that how we can get max-number in one array of length k

    second, It is that how to merge all the number of 2 array to form max number

    third, it is that by loop all the N possible combination, we get the final solution.

    Here is the code:

    class Solution {
    public:
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            int len1=nums1.size(), len2=nums2.size();
            vector<int> result(k, 0);
            string result_str;
            for(int i=max(0,k-len2); i<=k && i<=len1; i++){
                vector<int> sub_1=help(nums1, i);
                vector<int> sub_2=help(nums2, k-i);
                vector<int> candidate=merge(sub_1, sub_2, k);
                ostringstream str_c;
                for(auto number:candidate) str_c<<number;
                if(result_str=="" || str_c.str().compare(result_str)>0){
                    result_str=str_c.str();
                    result=candidate;
                }
            }
            return result;
        }
        
        vector<int> help(vector<int>& nums, int k){
            int len=nums.size();
            int count=0;
            vector<int> result(k, 0);
            for(int i=0; i<len; i++){
                /** pop out the smaller number than nums[i] **/
                while(count>0 && len-i+count>k && nums[i]>result[count-1]) count--;
                if(count<k)  result[count++]=nums[i];
            }
            return result;
        }
        
        /** k=len1+len2 **/
        vector<int> merge(vector<int>& nums1, vector<int>& nums2, int k){
            vector<int> result(k, 0);
            ostringstream num_str1, num_str2;
            string str1, str2;
            for(auto num:nums1)  num_str1<<num;
            for(auto num:nums2)  num_str2<<num;
            str1=num_str1.str();
            str2=num_str2.str();
            for(int i=0, j=0, r=0; r<k; r++){
                result[r]=str1.substr(i).compare(str2.substr(j))>0 ? nums1[i++] : nums2[j++];
            }
            return result;
        }
    };

  • 0
    2

    2 times AC solution

    The key is to implement the 2 sub-function calls.

    class Solution {
    public:
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            int size_1 = nums1.size(), size_2 = nums2.size();
            vector<int> result(k, 0);
            string str_result;
            for(int i = max(0, k-size_2); i <= k && i <= size_1; i++) {
                vector<int> v_1 = maxKnumber(nums1, i);
                vector<int> v_2 = maxKnumber(nums2, k-i);
                vector<int> v_merge = merge(v_1, v_2, k);
                ostringstream str_merge;
                for(auto number : v_merge)  str_merge<<number;
                if(str_result == "" || str_merge.str().compare(str_result) > 0) {
                    str_result = str_merge.str();
                    result = v_merge;
                }
            }
            return result;
        }
        
        vector<int> maxKnumber(vector<int> &nums, int k) {
            int size_nums = nums.size();
            int count = 0;
            vector<int> result(k , 0);
            for(int i = 0; i < size_nums; i++) {
                while(count > 0 && size_nums - i + count > k && nums[i] > result[count-1])  count--;
                if(count < k)  result[count++] = nums[i];
            }
            return result;
        }
        
        vector<int> merge(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<int> result(k, 0);
            ostringstream num_str1, num_str2;
            string str1, str2;
            for(auto num : nums1)  num_str1<<num;
            for(auto num : nums2)  num_str2<<num;
            str1 = num_str1.str();
            str2 = num_str2.str();
            for(int i = 0, j = 0, r = 0; r < k; r++) {
                result[r] = str1.substr(i).compare(str2.substr(j)) > 0 ? nums1[i++] : nums2[j++];
            }
            return result;
        }
    };

  • 0
    H

    I like this analysis a lot! thanks


  • 0
    H

    /*my version, same idea as yours TLE version
    */

    string strMax(string s1, string s2) {
    while (s1.length() >= 1) {
    if (s1.front() == ' ')
    s1.erase(s1.begin());
    else
    break;
    }
    while (s2.length() >= 1) {
    if (s2.front() == ' ')
    s2.erase(s2.begin());
    else
    break;
    }

        if (s1.length() < s2.length())
            return s2;
        else if (s1.length() > s2.length())
            return s1;
        else {
            if (s1 >= s2)
                return s1;
            else    
                return s2;
        }
    }
    vector<int> maxNumber_3D_DP(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> res;
        int len1 = nums1.size();
        int len2 = nums2.size();
        if (len1 + len2 < k)
            return res;//impossible to consutrct such a result
        vector<vector<vector<string>>> dp(k+1, vector<vector<string>>(len1+1, vector<string>(len2+1, "")));
        
        cout << strMax("123", "340") <<  endl;
        
        for (int i = 0; i <= len1; i ++) {
            for (int j = 0; j <= len2; j ++) {
                dp[0][i][j] = "";//when k = 0
            }
        }
        for (int l = 1; l <= k; l ++) {
            dp[l][0][0] = ""; //take 0 digits from nums1 and nums2
        }
        for (int l = 1; l <= k; l ++) {
            for (int j = 1; j <= len2; j ++) {
                if (l <= j)
                    dp[l][0][j] = strMax(dp[l-1][0][j-1]+to_string(nums2[j-1]), dp[l-1][0][j-1]);//takes 0 digits from nums1
                else
                    dp[l][0][j] = "";
            }
        }
        for (int l = 1; l <= k; l ++) {
            for (int i = 1; i <= len1; i ++) {
                if (l <= i)
                    dp[l][i][0] = strMax(dp[l-1][i-1][0]+to_string(nums1[i-1]), dp[l-1][i-1][0]);//takes 0 digits from nums2
                else
                    dp[l][i][0] = "";
            }
        }
        for (int l = 1; l <= k; l ++) {
            for (int i = 1; i <= len1; i ++) {
                for (int j = 1; j <= len2; j ++) {
                    dp[l][i][j] = strMax(strMax(dp[l-1][i-1][j]+to_string(nums1[i-1]),
                                                dp[l-1][i][j-1]+to_string(nums2[j-1])),
                                         dp[l][i-1][j-1]);
                }
            }
        }
        string tmp = dp[k][len1][len2];
        for (auto c: tmp) {
            res.push_back(c-'0');
        }
        return res;
    }

Log in to reply
 

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