Huahua’s Tech Road

花花酱 LeetCode Ultimate DP Study Plan Day 6

By zxi on December 1, 2021

152. Maximum Product Subarray

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def maxProduct(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> Tuple[int, int]:

"""min / max subarray product ends with nums[i]."""

if i == 0: return nums[i], nums[i]

low, hi = dp(i - 1)

if nums[i] < 0: low, hi = hi, low

return min(low * nums[i], nums[i]), max(hi * nums[i], nums[i])

return max(dp(i)[1] for i in range(len(nums)))

1567. Maximum Length of Subarray With Positive Product

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def getMaxLen(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> Tuple[int, int]:

"""Max length of pos/neg product ends with nums[i]."""

if i < 0 or nums[i] == 0: return 0, 0

p, n = dp(i - 1)

if nums[i] > 0:

return p + 1, n + 1 if n else 0

else: # nums[i] < 0

return n + 1 if n else 0, p + 1

return max(dp(i)[0] for i in range(len(nums)))

花花酱 LeetCode Ultimate DP Study Plan Day 5

By zxi on December 1, 2021

53. Maximum Subarray

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxSubArray(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> int:

"""Max subarray ends with nums[i]."""

if i < 0: return 0 # Empty array.

return nums[i] + max(0, dp(i - 1))

# Try all possible ending positions.

return max(dp(i) for i in range(len(nums)))

918. Maximum Sum Circular Subarray

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxSubarraySumCircular(self, nums: List[int]) -> int:

n = len(nums)

@cache

def dp(i: int, s: int) -> int:

"""Max subarray ends with s * nums[i]."""

if i < 0: return 0 # Empty array.

# Append to max subbary ends with nums[i-1] or start a new one.

return nums[i] * s + max(0, dp(i - 1, s))

max_p = max(dp(i, 1) for i in range(n))

max_n = max(dp(i, -1) for i in range(n))

return max_p if max_p < 0 else max(max_p, sum(nums) + max_n)

花花酱 LeetCode Ultimate DP Study Plan Day 4

By zxi on December 1, 2021

55 Jump Game

Python3

# Author: Huahua

# Time complexity: O(n^2)

# Space complexity: O(n)

class Solution:

def canJump(self, nums: List[int]) -> bool:

n = len(nums)

@cache

def dp(i: int) -> bool:

"""Returns whether we can reach n - 1 from i."""

if i >= n - 1: return True

if i + nums[i] >= n - 1: return True

for s in range(1, nums[i] + 1):

if dp(i + s): return True

return False

return dp(0)

45 Jump Game II

Python3

# Author: Huahua

# Time complexity: O(n^2)

# Space complexity: O(n)

class Solution:

def jump(self, nums: List[int]) -> int:

n = len(nums)

@cache

def dp(i: int) -> int:

"""Min steps to reach n - 1 from i."""

if i >= n - 1: return 0

if i + nums[i] >= n - 1: return 1

ans = n

for s in range(1, nums[i] + 1):

ans = min(ans, dp(i + s) + 1)

return ans

return dp(0)

花花酱 LeetCode Ultimate DP Study Plan Day 1 – 3

By zxi on November 30, 2021

Day 1

509. Fibonacci Number

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

@cache

def fib(self, n: int) -> int:

return n if n <= 1 else self.fib(n - 1) + self.fib(n - 2)

1137. N-th Tribonacci Number

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

@cache

def tribonacci(self, n: int) -> int:

if n == 0: return 0

if n <= 2: return 1

return sum(self.tribonacci(n - i - 1) for i in range(3))

Day 2

70. Climbing Stairs

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

@cache

def climbStairs(self, n: int) -> int:

if n <= 1: return 1

return self.climbStairs(n - 1) + self.climbStairs(n - 2)

746. Min Cost Climbing Stairs

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def minCostClimbingStairs(self, cost: List[int]) -> int:

@cache

def dp(i: int) -> int:

if i <= 1: return 0

return min(dp(i - 1) + cost[i - 1],

dp(i - 2) + cost[i - 2])

return dp(len(cost))

Day 3

198. House Robber

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def rob(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> int:

if i < 0: return 0

return max(nums[i] + dp(i - 2), dp(i - 1))

return dp(len(nums) - 1)

213. House Robber II

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def rob(self, nums: List[int]) -> int:

n = len(nums)

if n == 1: return nums[0]

@cache

def dp(i: int, j: int) -> int:

if j < i: return 0

return max(nums[j] + dp(i, j - 2), dp(i, j - 1))

return max(dp(0, n - 2), dp(1, n - 1))

740. Delete and Earn

This problem can be reduced to LC 198 House Robber

Python3

# Author: Huahua

# Time complexity: O(m + n)

# Space complexity: O(m + n)

class Solution:

def deleteAndEarn(self, nums: List[int]) -> int:

houses = [0] * (10**4 + 1)

for x in nums:

houses[x] += x

@cache

def dp(i : int) -> int:

if i < 0: return 0

return max(houses[i] + dp(i - 2), dp(i - 1))

return dp(len(houses) - 1)

花花酱 LeetCode 76. Minimum Window Substring

By zxi on November 29, 2021

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10⁵
s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Solution: Hashtable + Two Pointers

Use a hashtable to store the freq of characters we need to match for t.

Use (i, j) to track a subarray that contains all the chars in t.

Time complexity: O(m + n)
Space complexity: O(m)

C++

// Author: Huahua

class Solution {

public:

string minWindow(string s, string t) {

const int n = s.length();

const int m = t.length();

vector<int> freq(128);

for (char c : t) ++freq[c];

int start = 0;

int l = INT_MAX;

for (int i = 0, j = 0, left = m; j < n; ++j) {

if (--freq[s[j]] >= 0) --left;

while (left == 0) {

if (j - i + 1 < l) {

l = j - i + 1;

start = i;

}

if (++freq[s[i++]] == 1) ++left;

}

return l == INT_MAX ? "" : s.substr(start, l);

}

};

Huahua's Tech Road

花花酱 LeetCode Ultimate DP Study Plan Day 6

152. Maximum Product Subarray

Python3

1567. Maximum Length of Subarray With Positive Product

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 5

53. Maximum Subarray

Python3

918. Maximum Sum Circular Subarray

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 4

55 Jump Game

Python3

45 Jump Game II

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 1 – 3

Day 1

Python3

Python3

Day 2

Python3

Python3

Day 3

Python3

Python3

Python3

花花酱 LeetCode 76. Minimum Window Substring

Solution: Hashtable + Two Pointers

C++