Huahua’s Tech Road

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

}

};

花花酱 LeetCode 117. Populating Next Right Pointers in Each Node II

By zxi on November 29, 2021

Given a binary tree

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 6000].
-100 <= Node.val <= 100

Follow-up:

You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Solution -2: Group nodes into levels

Use pre-order traversal to group nodes by levels.
Connects nodes in each level.

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

C++

// Author: Huahua

class Solution {

public:

Node* connect(Node* root) {

vector<vector<Node*>> levels;

dfs(root, 0, levels);

for (auto& nodes : levels)

for(int i = 0; i < nodes.size() - 1; ++i)

nodes[i]->next = nodes[i+1];

return root;

}

private:

void dfs(Node *root, int d, vector<vector<Node*>>& levels) {

if (!root) return;

if (levels.size() < d+1) levels.push_back({});

levels[d].push_back(root);

dfs(root->left, d + 1, levels);

dfs(root->right, d + 1, levels);

}

};

Solution -1: BFS level order traversal

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

C++

// Author: Huahua

class Solution {

public:

Node* connect(Node* root) {

if (!root) return root;

queue<Node*> q{{root}};

while (!q.empty()) {

int size = q.size();

Node* p = nullptr;

while (size--) {

Node* t = q.front(); q.pop();

if (p)

p->next = t, p = p->next;

else

p = t;

if (t->left) q.push(t->left);

if (t->right) q.push(t->right);

}

return root;

}

};

Solution 1: BFS w/o extra space

Populating the next level while traversing current level.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

Node* connect(Node* root) {

Node* p = root;

while (p) {

Node dummy;

Node* c = &dummy;

while (p) {

if (p->left)

c->next = p->left, c = c->next;

if (p->right)

c->next = p->right, c = c->next;

p = p->next;

}

p = dummy.next;

}

return root;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 117. Populating Next Right Pointers in Each Node II

Solution -2: Group nodes into levels

C++

Solution -1: BFS level order traversal

C++

Solution 1: BFS w/o extra space

C++