032. Longest Valid Parentheses

Difficulty: Hard

Frequency: N/A

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if (n <= 1) return 0;
        vector<int> dp(s.size(), 0);
        int maxL = 0;
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                    maxL = max(maxL, dp[i]);
                } else {
                    if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                        maxL = max(maxL, dp[i]);
                    }
                }
            }
        }
        return maxL;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

Advertisements

322. Coin Change

Difficulty: Medium

Frequency: N/A

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.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

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


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, -1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int c : coins) {
                if (i - c >= 0 && dp[i - c] != -1) {
                    dp[i] = dp[i] > 0 ? min(dp[i], dp[i - c] + 1) : dp[i - c] + 1;
                }
            }
        }
        return dp[amount];
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

309. Best Time to Buy and Sell Stock with Cooldown

Difficulty: Medium

Frequency: N/A

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

  • You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN, sell = 0, coolDown = 0, noOp = INT_MIN;
        for (int p : prices) {
            noOp = max(buy, noOp);
            buy = coolDown - p;
            coolDown = max(sell, coolDown);
            sell = noOp + p;
        }
        return max(sell, coolDown);
    }
};

Solution 2:

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


Submission errors:

 

Things to learn: