Home

236. Lowest Common Ancestor of a Binary Tree Solution If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is null/None/nil. def lowestCommonAncestor(self, root...

494. Target Sum Solution Store sums and # ways up to nums[i-1] into a dictionary dic. For nums[i], create a new dictionary. For each sum in dic up to nums[i-1], sum+k and sum-k can be created in dic[sum] MORE ways. This is because sum1-k can be equal sum2+k. def findTargetSumWays(self, nums, S): ...

309. Best Time to Buy and Sell Stock with Cooldown Solution There’re 3 states, hold, nohold, ‘cooldown’. Keep the max profit up to time i when we are in these three states. hold can be achieved by donothing (hold) or buy (nohold - p) nohold can be achieved by donothing (nohold) or sell (cooldown, because aft...

17. Letter Combinations of a Phone Number Solution Update results from the string up to i-1. dic = { '2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'], '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'], '7': ['p', 'q', 'r', 's'], '8': ['t', 'u', 'v'], '9': ['w', 'x', 'y', 'z'] } def letterC...

279. Perfect Squares Solution _dp stores the least number of perfect squares for index. When len(_dp) < n, we can update it using the previous results. For i, it can use results from _dp[i - perfect squares] + 1. Select the minimum of all results, it is the result for _dp[i]. _dp = [0] def n...

114. Flatten Binary Tree to Linked List Solution Only when root has left subtree, we need to flatten it. When root doesn’t have left subtree, update it to root.right. The left subtree need to be apppended to root’s right hand side. The right subtree need to be appended to the end of left tree. Flatten the l...

621. Task Scheduler Solution The tasks which appear more times is the bottle neck. We store the number of times each task appeared. Use heapq to sort it. Use the top tasks to fill in the time units we need between two same tasks. When there is not enough tasks, None is appended. We need to update t...

394. Decode String Solution Use a dictionary to store the decoded string. When replaceing, we should go from outside to inside. def decodeString(self, s): """ :type s: str :rtype: str """ clauses = self.get_clauses_idx(s) dic = [] for i in range(len(clauses)): left, right = clauses[i] ...