{{ message }}

Instantly share code, notes, and snippets.

# Ray liyunrui

Last active Apr 25, 2020
leetcode backtracking
View 52. N-Queens II.py
 class Solution: def totalNQueens(self, n: int) -> int: """ T: O(n!). There's n choices to put the first queen in first row, then not more than n(n-2) to put the second one, and etc. Therefore, time complexity is n factorial. We use two 1-D arrays to represetn diagonals because it's a vector. """ self.count = 0
Last active Apr 30, 2020
Priority Queue/ Min-Heap
View Priority-Queue.md
Data Structure Leetcode Problems Purpose Operation
Created Apr 30, 2020
leetcode-greedy
View 435. Non-overlapping Intervals.py
 class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: """ Greedy problem because of pattern: "Find minimum or maximum number of something to do something" T: O(nlogn) S: O(1). No extra space is used. Reference: https://leetcode.com/problems/non-overlapping-intervals/discuss/276056/Python-Greedy-Interval-Scheduling """
Created Apr 30, 2020
leetcode-greedy
View 452. Minimum Number of Arrows to Burst Balloons.py
 class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: n = len(points) # edge case if n == 0: return 0 ending_time, ans = float('-inf'), 0 # the earliest end time # sort the balloons by their end x-coordinate for i in sorted(points, key=lambda x: x[1]): start_time = i[0]
Last active May 1, 2020
leetcode-greedy
View 253. Meeting Rooms II.py
 class Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int: """ There're two major portions that take up time. One is sorting part, we sort the intervals based on starting time, which takes O(nlogn) time. Another one is we use min-heap. We have N operations of insertion or extraction totally. It takes O(n * log(n)) time. T: O(nlogn) S: O(n) because in the worse case, we might contains N elements in min-heap
Last active May 3, 2020
leetcode-backtracking
View 37. Sudoku Solver.py
 class Solution: def solveSudoku(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. Brute Force 1. Generate all possible boards 2. To check if it's a valid sudoku board. So, the operation is exponential amount. T(9**81), where 9 is # choices we can make to fill empty cell and 81 is number of cells we need to fill in the grid.
Created May 7, 2020
leetcode-dp
View 64. Minimum Path Sum.py
 class Solution: def minPathSum(self, grid: List[List[int]]) -> int: """ Brute force: We try to find all possible paths from upper-left to lower-right, and find minimum out of them. The time complexity is 2 raist to power of (m+n). T: O(2*m+n) DP: T: O(mn), where m is number of rows and n is number of columns S: O(mn)
Last active May 10, 2020
leetcode-dp
View 673. Number of Longest Increasing Subsequence.py
 class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: """ DP two-pass version, which it is often easier to think about recursive formulation than below one-pass version. T: O(2 * n**2) S: O(2*n) """ n = len(nums) # edge case
Last active May 11, 2020
leetcode-dp
View 416. Partition Equal Subset Sum.py
 class Solution: def canPartition(self, nums: List[int]) -> bool: """ After thinking in a way, whether it's able to find a subset of element could construct half of sum of all elments in the array. Then, it's a typical 0/1 knapsacks problem. Let's assume dp[i][j] means whether the specific sum j can be gotten from the first i numbers or not T: O(n*w), where n is number of elements in array and w is half of sum S: O(n*w) """
Created May 12, 2020
leetcode-dp
View 72. Edit Distance.py
 class Solution: def minDistance(self, word1: str, word2: str) -> int: """ It's a typical dp problem. Edit distance is the minimum number of editing operations needed to transform a string into another string. Given two strings and three operation allowed to operate on the string: 1.insert char 2.replace char 3.delete char , to find minimum number of operations required to transform word1 to word2.