LeetCode [322] Coin Change

 322. Coin Change

Medium

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

 

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Example 4:

Input: coins = [1], amount = 1
Output: 1

Example 5:

Input: coins = [1], amount = 2
Output: 2

 

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; dp[0] = 0; for (int i = 1; i <= amount; ++i) { dp[i] = -1; for (int c : coins) { if (i >= c && dp[i - c] >= 0) { if (dp[i] == -1) dp[i] = dp[i - c] + 1; else dp[i] = Math.min(dp[i], dp[i - c] + 1); } } // System.out.println(Arrays.toString(dp)); } return dp[amount]; } }

LeetCode [321] Create Maximum Number

Ref
[1] https://leetcode.com/problems/create-maximum-number/
OJ
[2] https://leetcode.com/discuss/75756/share-my-greedy-solution

LeetCode [312] Burst Balloons

312. Burst Balloons

Hard

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:

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

Example:

Input: [3,1,5,8]
Output: 167 
Explanation: 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

 =============

Eg.
nums = 3  1  5  8
                                     0  1  2  3  4  5
after extended nums = 1  3  1  5  8  1

bottom up

0  1  2  3  4  5
1  3  1  5  8  1
step 1: burst balloon 2 => 3*1*5 = 15 => dp[2][2] = dp[2][1]+dp[3][2]+15 = 15


0  1  2  3  4  5
1  3  1  5  8  1
step 2: burst balloon 3 => 3*5*8 = 120 => dp[2][3] = dp[2][2]+dp[4][3]+120 = 135


0  1  2  3  4  5
1  3  1  5  8  1
step 1: burst balloon 1 => 1*3*8= 24 => dp[1][3] = dp[1][0]+dp[2][3]+24 = 159

0  1  2  3  4  5
1  3  1  5  8  1
step 1: burst balloon 4 => 1*8*1 = 8 => dp[1][4] = dp[1][3]+dp[5][4]+8 = 167


 Ref
[1] https://leetcode.com/problems/burst-balloons/
[2] https://leetcode.com/discuss/72186/c-dynamic-programming-o-n-3-32-ms-with-comments

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

//C++: TLE class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); if(n==0) return 0; int ret = 0; for(int i=0; i<n; ++i){ int tmp = (i==0?1:nums[i-1])*nums[i]*(i==n-1?1:nums[i+1]); vector<int> nums1 = nums; nums1.erase(nums1.begin()+i); tmp += maxCoins(nums1); ret = max(ret, tmp); } return ret; } }; class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); nums.insert(nums.begin(), 1); nums.insert(nums.end(), 1); //can be further optimized by removing all zeros //dp[s][e] is max coins by bursting all balloons from s to e vector<vector<int>> dp(n+2, vector<int>(n+2, 0)); for(int s = n; s>0; --s){ for(int e = s; e<=n; ++e){ int bestCoins = 0; for(int i = s; i<=e; ++i){ //coins is the max coins when balloon i is the last balloon int coins = dp[s][i-1] + dp[i+1][e] + nums[s-1]*nums[i]*nums[e+1]; bestCoins = max(bestCoins, coins); } dp[s][e] = bestCoins; } } return dp[1][n]; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public int maxCoins(int[] nums) { int n = nums.length; int[] numsExt = new int[n+2]; Arrays.fill(numsExt, 1); for(int i=1; i<=n; ++i) numsExt[i] = nums[i-1]; int[][] dp = new int[n+2][n+2]; for(int s=n; s>0; --s){ for(int e = s; e<=n; ++e){ int bestCoins = 0; for(int i=s; i<=e; ++i){ int coins = dp[s][i-1] + dp[i+1][e] + numsExt[s-1]*numsExt[i]*numsExt[e+1]; bestCoins = Math.max(bestCoins, coins); } dp[s][e] = bestCoins; } } return dp[1][n]; } }

LeetCode [309] Best Time to Buy and Sell Stock with Cooldown

Ref
[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
OJ
[2] https://leetcode.com/discuss/71354/share-my-thinking-process

LeetCode [304] Range Sum Query 2D - Immutable

 304. Range Sum Query 2D - Immutable

Medium

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

//C++: 
class NumMatrix {
    vector<vector<int>> mt;
public:
    NumMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size();
        if(m==0) return;
        int n = matrix[0].size();
        if(n==0) return;
        mt.resize(m+1, vector<int>(n+1, 0));
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                mt[i][j] += matrix[i-1][j-1] + mt[i-1][j] + mt[i][j-1] - mt[i-1][j-1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return mt[row2+1][col2+1] - mt[row2+1][col1] - mt[row1][col2+1] + mt[row1][col1];
    }
};

//Java
class NumMatrix {
    int[][] extMatrix;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        if(m==0) return;
        int n = matrix[0].length;
        if(n==0) return;
        extMatrix = new int[m+1][n+1];
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                extMatrix[i][j] = extMatrix[i-1][j]+extMatrix[i][j-1]+matrix[i-1][j-1]-extMatrix[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int r = extMatrix[row2+1][col2+1]-extMatrix[row2+1][col1]-extMatrix[row1][col2+1]+extMatrix[row1][col1];
        return r;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

//Java, BIT
class NumArray {
    int[] arr;
    int[] tree;
    int m;
    public NumArray(int[] nums) {
        m = nums.length;
        arr = new int[m];
        tree = new int[m+1];
        for(int i=0; i<m; ++i){
            update(i, nums[i]);
        }
    }
    
    //index for arr
    public void update(int k, int val) {
        int d = val-arr[k];
        arr[k] = val;
        for(int i=k+1; i<=m; i+=i&(-i)){
            tree[i]+=d;
        }
    }
    
    //index for tree
    public int sum(int k){
        int s = 0;
        for(int i=k; i>0; i-=i&(-i)){
            s += tree[i];
        }
        return s;
    }
    public int sumRange(int i, int j) {
        return sum(j+1)-sum(i);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

LeetCode [303] Range Sum Query - Immutable

 303. Range Sum Query - Immutable

Easy

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

 

Constraints:

• You may assume that the array does not change.
• There are many calls to sumRange function.
• 0 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5
• 0 <= i <= j < nums.length

//C++
class NumArray {
    vector<int> sum;
public:
    NumArray(vector<int> &nums) {
        for(auto n:nums){
            sum.push_back(n+(sum.empty()?0:sum.back()));
        }
    }

    int sumRange(int i, int j) {
        return sum[j]-(i==0?0:sum[i-1]);
    }
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

//Java
class NumArray {
    int[] nums;
    public NumArray(int[] nums) {
        int s = 0;
        this.nums = Arrays.copyOf(nums, nums.length);
        for(int i=0; i<nums.length; ++i){
            s += nums[i];
            this.nums[i] = s;
        }
    }
    
    public int sumRange(int i, int j) {
        return this.nums[j] - (i-1>=0?this.nums[i-1]:0);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

LeetCode [300] Longest Increasing Subsequence

300. Longest Increasing Subsequence

Medium

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n==0) return 0; vector<int> dp(n, 1); int ret = 1; for(int i=0; i<n; ++i){ for(int j=0; j<i; ++j){ if(nums[i]>nums[j]) dp[i] = max(dp[i], dp[j]+1); } ret = max(ret, dp[i]); } return ret; } }; //https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ class Solution1 { public: int lengthOfLIS(vector<int>& nums) { //al[L-1] is the last element of the min L-length sequence //for each number n in nums, find the first element al[L-1] in al greater (or equal) than n //replace al[L-1] by n (so we can keep the min property of the L-length subsequence) vector<int> al; for(auto n:nums){ if(al.size()==0 || n>al.back()) al.push_back(n); else{ int l = 0, r = al.size()-1; while(l<=r){ int m = l+(r-l)/2; if(n<=al[m] && (m==l || al[m-1]<n)){ al[m] = n; break; }else if(n<al[m]){ r = m-1; }else{ l = m+1; } } } } return al.size(); } }; class Solution2 { public: int lengthOfLIS(vector<int>& nums) { vector<int> al; for(auto n:nums){ auto it = lower_bound(al.begin(), al.end(), n); if(it==al.end()) al.push_back(n); else *it = n; } return al.size(); } };