Share My 104ms C++ Solution


  • 0
    S
    class list1
    {
        vector<int> a;
        vector<vector<int>> f;
    public:
        list1() = delete;
        inline int size() {return a.size();}
        inline int next(int x,int d) {return f[x][d];}
        list1(vector<int>& a0)
        {
            a = a0;
            f = vector<vector<int>>(a0.size() + 1,vector<int>(10,INT_MAX));
            for (int i = 0;i<a0.size();i++)
            {
                f[i][a[i]] = i;
                for (int j = i-1;j>=0;j--)
                {
                    if (a[j] == a[i]) break;
                    f[j][a[i]] = i;
                }
            }
        }
    };
    
    //dmd for detect_max_digit
    // dmd(a,x,rem) -> (max_digit, pos) , where a[pos-1] == max_digit
    // list a , from x, need rem numbers, x not included.
        
    pair<int,int> dmd(list1& a,int x,int rem)
    {
        for (int d = 9;d >= 0;d--)
        {
            int pos = a.next(x,d);
            if (pos == INT_MAX) continue;
            if (a.size() - (pos + 1) >= rem)
            return make_pair(d,pos + 1);
        }
    }
    
    
    class Solution {
    public:
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            list1 a1 = list1(nums1);
            int N1 = nums1.size();
            list1 a2 = list1(nums2);
            int N2 = nums2.size();
            
            auto ret = vector<int>(k,0);
            auto f = vector<int>(N1 + 1,0); 
            //f[i] denote a1[0..i-1] need a2[0..f[i]-1] to reach the current maximal number, and can expand to length k
            // in other words, the state is : the number is current maximal and can be expanded, list1 begin with a1[i] and list2 with a2[f[i]] 
            for (int d = 1;d <= k;d++)
            {
                int maxDigit = -1;
                auto tmpf = vector<int>(N1 + 1,INT_MAX);
                for (int x = 0;x<=N1;x++)
                {
                    int y = f[x];
                    if (y == INT_MAX) continue;
                    auto m1 = dmd(a1,x,k-d-(N2-y)); 
                    auto m2 = dmd(a2,y,k-d-(N1-x));
                    maxDigit = max(maxDigit,m1.first);
                    maxDigit = max(maxDigit,m2.first);
                }
                ret[d-1] = maxDigit;
                for (int x = 0;x<=N1;x++)
                {
                    int y = f[x];
                    if (y == INT_MAX) continue;
                    auto m1 = dmd(a1,x,k-d-(N2-y));
                    if (m1.first == maxDigit)
                    tmpf[m1.second] = min(tmpf[m1.second],y);
                    auto m2 = dmd(a2,y,k-d-(N1-x));
                    if (m2.first == maxDigit)
                    tmpf[x] = min(tmpf[x],m2.second);
                }
                f = tmpf;
            }
            return ret;
        }
    };

Log in to reply
 

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