321. Create Maximum Number

Difficulty: Hard

Frequency: N/A

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size(), m = nums2.size();
        vector<int> result;
        for (int i = max(0, k - m); i <= k && i <= n; i++) {
            vector<int> tmp = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
            if (greater(tmp, 0, result, 0)) result = tmp;
        }
        return result;
    }
    vector<int> merge(vector<int> nums1, vector<int> nums2, int k) {
        vector<int> result;
        for (int i = 0, j = 0, r = 0; r < k; r++) {
            if (greater(nums1, i, nums2, j)) result.push_back(nums1[i++]);
            else result.push_back(nums2[j++]);
        }
        return result;
    }
    bool greater(vector<int> nums1, int i, vector<int> nums2, int j) {
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        return j == nums2.size() || i < nums1.size() && nums1[i] > nums2[j];
    }
    vector<int> maxArray(vector<int> nums, int k) {
        int n = nums.size();
        vector<int> result(k, 0);
        for (int i = 0, j = 0; i < n; i++) {
            while (n - i + j > k && j > 0 && result[j - 1] < nums[i]) j--;
            if (j < k) result[j++] = nums[i];
        }
        return result;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

Advertisements

312. Burst Balloons

Difficulty: Hard

Frequency: N/A

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        vector<int> nums2(nums.size() + 2, 0);
        int n = 1;
        for (int num : nums) {
            if (num > 0) nums2[n++] = num;
        }
        nums2[0] = nums2[n++] = 1;
        
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int k = 2; k < n; k++) {
            for (int left = 0; left < n - k; left++) {
                int right = left + k;
                for (int i = left + 1; i < right; i++) {
                    dp[left][right] = max(dp[left][right], nums2[left] * nums2[i] * nums2[right] + dp[left][i] + dp[i][right]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn: