Huahua’s Tech Road

花花酱 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);

}

};

花花酱 LeetCode 81. Search in Rotated Sorted Array II

By zxi on November 29, 2021

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
nums is guaranteed to be rotated at some pivot.
-10⁴ <= target <= 10⁴

Solution: Binary search or divide and conquer

If current range is ordered, use binary search, Otherwise, divide and conquer.

Time complexity: O(logn) best, O(n) worst
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

bool search(vector<int>& A, int target) {

return search(A, 0, A.size() - 1, target);

}

private:

bool search(vector<int>& A, int l, int r, int target) {

if (l > r) return 0;

if (l == r) return target == A[l];

int mid = l + (r - l) / 2;

if (A[l] < A[mid] && A[mid] < A[r])

return (target <= A[mid]) ? search(A, l, mid, target) : search(A, mid + 1, r, target);

else

return search(A, l, mid, target) || search(A, mid + 1, r, target);

}

};

Huahua's Tech Road

花花酱 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++

花花酱 LeetCode 81. Search in Rotated Sorted Array II

Solution: Binary search or divide and conquer

C++