Home

337. House Robber III Solution A house can be stolen or not stolen. Use a tuple to store money that the thief can rob when the house is steal and not. If a house is stolen, its neighbours CANNOT be stolen. Its neighbours money can be decided. If a house is not stolen, its neighbours CAN be stolen. We choose ...

96. Unique Binary Search Trees Solution For each number from 0 to n, set it as pivot, i.e. root of the tree. Find the number of left and right tree for each pivot. Consider right whose range is [pivot+1, n] as a tree whose range is [0, n-pivot-1]. Use a dictionary to avoid duplicate computing. def numTr...

78. Subsets Solution For each subsets up to i-1, append nums[i] to the end of it to find subsets up to i. def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ result = [[]] for num in nums: result += [i + [num] for i in result] return result

215. Kth Largest Element in an Array Solution Randomly choose a pivot. Let all elements on the left to it smaller than it, and all elements on the right to it larger than it. Return the index of the pivot after ‘sorting’. Select one of the partition to continue searching. def findKthLargest(self, nums, k): ""...

64. Minimum Path Sum Solution Use the grid to store the minimum path sum to the current block. Consider the corner case when i == 0 or j == 0. def minPathSum(self, grid): """ :type grid: List[List[int]] :rtype: int """ m, n = len(grid), len(grid[0]) start = grid[0][0] for i in range(m): ...

215. Kth Largest Element in an Array Solution Use divide and conquer. Change the problem to Kth smallest element in the array. Randomly select the pivot can make the process faster. def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ l, r, k = 0, len(n...

287. Find the Duplicate Number Solution Consider the array as a linked list. The existence of the duplicate number shows the existence of the cycle in the linked list. The entrance of the cycle is the duplicate number. def findDuplicate(self, nums): """ :type nums: List[int] :rtype: int """ sl...

39. Combination Sum Solution Note that one number can be used for multiple times. Once a number is greater than the target, it is confirmed that it cannot be used anymore. We should exclude it. Otherwise, continue using the same set and check target - c. def combinationSum(self, candidates, target): """ :...