Blog
DP Memo to Iteration
198 - House Robber class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) f0 = f1 = 0 for i, x in enumerate(nums): f0, f1 = f1, max(f0 + x, f1) return f1 # cahce = [-1] * n # def dfs(i): # if i < 0: # return 0 # if cache[i] != -1: # return cache[i] # cache[i] = max(dfs(i - 1), dfs(i - 2) + nums[i]) # return cache[i] class Solution { public: int rob(vector<int>& nums) { // int n = nums.size(); // int f0 = 0, f1 = 0; // for (int i = 0; i < n; ++i) { // int x = nums[i]; // int new_f1 = max(f0 + x, f1); // f0 = f1; // f1 = new_f1; // } // return f1; // Below is the optional recursive + memoized (DFS + cache) version int n = nums.size(); vector<int> cache(n, -1); return dfs(n - 1, nums, cache); } int dfs(int i, vector<int>& nums, vector<int>& cache) { if (i < 0) return 0; if (cache[i] != -1) return cache[i]; cache[i] = max(dfs(i - 1, nums, cache), (i >= 1 ? dfs(i - 2, nums, cache) : 0) + nums[i]); return cache[i]; } // // corner cases // if (nums.size() == 0) return 0; // if (nums.size() == 1) return nums[0]; // // dp // // f[i] represents: max money by robbing previous i houses // vector<int> f(3, 0); // f[0] = nums[0]; // f[1] = max(nums[0], nums[1]); // for (int i = 2; i < nums.size(); ++i) { // f[i % 3] = max(nums[i] + f[(i - 2) % 3], f[(i - 1) % 3]); // } // return f[(nums.size() - 1) % 3]; };
March 1, 2025
Partition
Partition Template Quick Sort Top K Split(Quick Selection): (n = k/1/n-k-1) Top Kth Smallest Top Kth Largest
April 15, 2024
Union Find
Coverd all topics of Union Find It’s a data structure that supports fast merging and searching of sets O(1) merge the two sets where x and y are located: Merge(x, y) – connect the roots O(1) find the set to which x belongs: Find(x) – find the root O(1) check wheter x and y are in the same set: IsConnected(x, y) – check if they have the same root
April 7, 2024