/leetcode-myself

leetcode-myself

Primary LanguageC++

leetcode

ny leetcode notebook

time space

c/c++

Time limite 1s - 2s

data scale (n=* ) time complesity( O(*) ) example
<=30 2^n expensial,dfs+cut
10^2 n^3 floyed
10^3 n^2, n^2*logn dijkstra
10^4 n*sqrt(n)
10^5 n*logn sort,线段树,树状数组,set/map,dijkstra+heap,spfa,求图包,半平面交,二分
10^6 n,n*logn hash,two pointer,kmp
10^7 n two pointer,kmp,ac自动机,线性筛数组,常数小的n*logn算法
10^9 sqrt(n)
10^18 logn 最大公约数,...,数论

Code use C/C++

# Title Notes Complexity Run time
001 Two Sum
001 brute force time O(N^2) space O(1) 10%
001_hashmap hashmap time:O(N),space:O(N) 70%
001_binarySearch sort+binary search time:O(NlogN)+O(N) space:O(N) 99%
002 Add Two Numbers math 100%
003 Longest Substring Without Repeating Characters
003 brute force time O(N^2) space O(N) 51%
003_hashmap hash table time O(N^2) space O(1) 51%
003_hashtable_twopointer hash table + two pointer time O(N) space O(N) 100%
004 Median of Two Sorted Arrays 004_BinarySearch binary search O(log(min(m+n))) 99%
005 Longest Palindromic Substring
005 brute force time O(N^3) space O(1) 23%
005_dp dp time O(N^2) space O(N^2) 48%
006 ZigZag Conversion time O(N) space O(N) 20 ms, 77.62%
007 Reverse Integer int time O(1) space O(1) 98%
008 String to Integer (atoi) string time O(N) space O(1) 100%
009 Palindrome Number math time O(N) space O(1) 244 ms, 10.78%
009 Palindrome Number string time O(N) space O(N) 212ms 20%
009 Palindrome Number stack time O(N) space O(N) 124 ms, 81.11%
010 Regular Expression Matching dp time:O(M*N) space:O(M *N) 72%
011 Container With Most Water
011 brute force time:O(N^2) 40%
011_twoPointer two pointer time:O(N) 100%
013 Roman to Integer string time O(N) space O(1) 20ms 100%
014 Longest Common Prefix string time O(N*M) space O(1) ~0 100%
015 3Sum two pointer time:O(N^2) space:O(N) 91%
017 Letter Combinations of a Phone Number dfs time O(3^n)~O(4^n),space O(n) ~0 100%
019 Remove Nth Node From End of List two pointer time:O(N) 100%
020 Valid Parentheses stack time O(N) space O(N) ~0 100%
021 Merge Two Sorted Lists list time O(N) space O(N) 4ms 100%
022 Generate Parentheses dfs ~0 100%
023 Merge k Sorted Lists queue time O(logM*N) space O(M) M:number of lists N:avg of lists length 24ms 58%
023 Merge k Sorted Lists not use queue time O(logM*N) space O(M) 20ms 70%
023 Merge k Sorted Lists heap time O(N) space O(1) 16ms 99%
026 Remove Duplicates from Sorted Array array time O(N) space O(1) 16ms 99%
028 Implement strStr()
028 brute force time O(N*M) space O(1) 4ms 98%
028 KMP time O(N+M) space O(M) ~0 100%
028 BM faster then kmp time O(N)~worst O(N*M) space O(1) ~0 100%
028 Sunday faster then BM time O(N)~worst O(M*N) space O(1) ~0 100%
029 Divide Two Integers math time:O(log(N)) space:O(1) 12ms 98%
033 Search in Rotated Sorted Array divide and conquer time:O(log(N)) space:O(1) 4ms 98%
034 Find First and Last Position of Element in Sorted Array divide and conquer time:O(log(N)) space:O(1) 8ms 63%
036 Valid Sudoku hash table time O(1) space O(1) 12ms 97%
038 Count and Say string time O(N) space O(N) ~0 100%
041 First Missing Positive math time O(N) space O(1) 4ms 86%
042 Trapping Rain Water greedy time O(N) space O(1) 8ms 72%
044 Wildcard Matching dp time O(M*N) space O(M *N) 16ms 99%
046 Permutations dfs time O(N!) space O(N) 8ms 99%
048 Rotate Image math time O(N^2) space O(1) 4ms 72%
049 Group Anagrams string hashtable stl time N*M * logM space N *M 16ms 99%
053 Maximum Subarray dp time O(N) space O(1) 4ms,100%
054 Spiral Matrix math time O(M*N) space O(1) ~0ms,100%
055 Jump Game greedy time:O(N) 100%
056 Merge Intervals greedy time O(NlgN) space O(1) 8ms 99%
062 Unique Paths dp time:O(M*N) space:O(M *N) 100%
066 Plus One math time O(N) space O(N) 4ms 36%
069 Sqrt(x) binary search time:O(NlogN) 98%
070 Climbing Stairs dp time O(N) space O(N) ~0ms 100%
073 Set Matrix Zeroes math time O(M*N) space O(1) 48ms 44%
075 Sort Colors two pointer time O(N) space O(1) 4ms 36%
076 Minimum Window Substring two pointer + greedy time O(N) space O(1) 4ms 99%
078 Subsets backtracking recursion time: O(2^N) space: O(N) 4ms 100%
079 Word Search dfs time O(M*N *(4^L)) space O(L) L=len(word) 20 ms,80.20%
084 Largest Rectangle in Histogram stack time O(N) space O(N) 12 ms, 44%
088 Merge Sorted Array merge time O(N) space O(1) 4 ms, 99%
091 Decode Ways
091_RecursionWithMemorization dfs+memorize time O(N^2),space:O(N^2) 31%
091_dp dp time:O(N) space:O(1) 100%
094 Binary Tree Inorder Traversal tree time O(N) space O(1) 0 ms, 100%
098 Validate Binary Search Tree recursion time O(N) space O(height) 8 ms, 65%
101 Symmetric Tree dfs/bfs time O(N) space O(1) 8ms, 25%
102 Binary Tree Level Order Traversal dfs/bfs time O(N) space O(height) 4ms, 98%
103 Binary Tree Zigzag Level Order Traversal stack + recursion time O(N) space O(N) 4ms, 49%
103 Binary Tree Zigzag Level Order Traversal queue + layerOrder time O(N) space O(N) 4ms, 49%
104 Maximum Depth of Binary Tree reursion dfs time O(N) space O(height) 4ms, 98%
105 Construct Binary Tree from Preorder and Inorder Traversal recursion time O(N) space O(N) 100%
108 Convert Sorted Array to Binary Search Tree recursion time O(N) space O(height) 12ms, 56%
116 Populating Next Right Pointers in Each Node dfs/bfs time O(N) space O(height) 16ms, 47%
118 Pascal's Triangle math time O(N^2) space O(N^2) ~0 100%
121 Best Time to Buy and Sell Stock dp time O(N) space O(1) ~0 100%
122 Best Time to Buy and Sell Stock II math time O(N) space O(1) 4ms 100%
124 Binary Tree Maximum Path Sum dfs time O(N) space O(height) 20ms 44%
125 Valid Palindrome string stl time O(N) space O(N) 8ms 61%
127 Word Ladder bidirectional bfs time O(N*26^(L/2)) space O(N) 28ms 93%
128 Longest Consecutive Sequence hash map time O(N) space O(N) 8ms 67%
130 Surrounded Regions dfs 12ms 99%
131 Palindrome Partitioning dp+dfs time O(N^2) space O(N^2) 4ms 100%
134 Gas Station greedy time O(N) space O(1) 4ms 99%
136 Single Number hash map time O(N) space O(N) 16 ms 35%
136 Single Number math time O(N) space O(1) 8 ms 98%
138 Copy List with Random Pointer list time O(N) space O(1) 44 ms 39%
138 Copy List with Random Pointer hashmap time O(N) space O(N) 36 ms 52%
139 Word Break dp time:O(N^2) space:O(N) 100%
140 Word Break II dp+dfs time O(N^2) space O(N^2) 8ms,81%
141 Linked List Cycle two pointer time O(N) space O(1) 4ms 100%
146 LRU Cache hash map list time O(1) space O(N) 84ms 55%
148 Sort List merge sort list time O(NlogN) space O(1) 28ms 100%
149 Max Points on a Line dp+math time O(N^2) space O(N) 8ms 67%
150 Evaluate Reverse Polish Notation stack time O(N) space O(N) 8ms 68%
152 Maximum Product Subarray dp time:O(N) space:O(1) 100%
155 Min Stack stack 16ms,99%
160 Intersection of Two Linked Lists two pointer time:O(N) space:O(1) 24ms 87%
166 Fraction to Recurring Decimal math 0ms 100%
162 Find Peak Element binary search time:O(logN) space:O(1) 4ms 99%
169 Majority Element BST time O(N) space O(N) 8ms 99%
169 Majority Element Boyer-Moore vote time O(N) space O(1) 8ms 99%
169 Majority Element randomization time O(N) space O(1) 8ms 99%
169 Majority Element bit vote time O(32*N) space O(1) 12ms 98%
169 Majority Element full sorting time O(NlgN) space O(1) 12ms 98%
169 Majority Element partial sorting time O(N) on avg space O(1) 12ms 98%
169 Majority Element divide and conquer time O(N)~O(NlgN) space O(NlgN) 16ms 65%
169 Majority Element divaideand conquer time O(N)~O(NlgN) space O(lgN) 8ms 99%
171 Excel Sheet Column Number math time O(N) sapce O(1) 4ms 98%
172 Factorial Trailing Zeroes math time O(logN) space O(1) 12ms 40%
179 Largest Number sort time O(NlogN) space O(N) 0ms 100%
189 Rotate Array math time O(N) space O(1) 12ms 100%
190 Reverse Bits math time O(1) space O(1) 4ms 88%
191 Number of 1 Bits math time O(1) space O(1) 0ms 100%
198 House Robber math time O(N) space O(1) 0ms 100%
200 Number of Islands dfs time O(2* V*E) sapce O(1) 8ms 99%
202 Happy Number math 0ms 100%
204 Count Primes math time O(N log log N) space O(n) 32ms 56%
206 Reverse Linked List list time:O(N) space:O(1) 8ms 33%
207 Course Schedule
207_dfs dfs, vector / map time:O(Node+Edge) 99%
207_bfs bfs,queue + vector time:O(Node+Edge) 99%
208 Implement Trie (Prefix Tree) trie time O(L) space O(n*l^2) 56ms 69%
210 Course Schedule II dfs time = space = O(V+E)~O(V^2) 12ms 87%
212 Word Search II dfs + trie 56ms 46%
215 Kth Largest Element in an Array heap/quick sort time O(N lgN) space O(N) 16ms 37%
217 Contains Duplicate set time O(N lgN) space O(N) 16ms
218 The Skyline Problem bst Time O(NlogN) sapce O(N) 16ms 92%
227 Basic Calculator II stack time O(N) space O(N) 4ms 100%
230 Kth Smallest Element in a BST inorder+stack time:O(N) space:O(N) 8ms 99%
234 Palindrome Linked List two pointer time O(N) 8ms 99%
236 Lowest Common Ancestor of a Binary Tree dfs time O(N) space O(height) 12ms 58%
237 Delete list time O(1) 8ms 36%
238 Product of Array Except Self time O(N) space O(N) 40ms 42
239 Sliding Window Maximum BST(multiset) time O(Nlogk) space O(K) 80ms 22%
239 Sliding Window Maximum monotonic queue time O(N) space O(K) 80ms 22%
239 Sliding Window Maximum optimzie monotonic queue -> deque time O(N) space O(K) 36ms 100%
240 Search a 2D Matrix II
240 brute force time:O(N*M) space:O(1) 964ms 1.4%
240 divide and conquer+ recursion time:O(n^1.58) 1284ms 0.3%
240 Smart alg time O(M+N) space O(1) 36ms 98%
242 Valid Anagram hash map time O(N) space O(1) 16ms 36%
268 Missing Number xor time O(N) space O(1) 4ms 100%
268 Missing Number sum time O(N) space O(1) 4ms 100%
268 Missing Number math time O(N) space O(1) 4ms 100%
279 Perfect Squares dp time: O(N^2) space:O(N) 73%
283 Move Zeroes math time: O(N) space:O(1) 8ms, 100%
287 Find the Duplicate Number
287 brute force time O(N^2) sapce O(1) 452ms 3.2%
287 binary search time O(NlogN) space O(1) 12ms 35%
287 Floyd alg time O(N) space O(1) 4ms 100%
289 Game of Life math time O(M*N) space O(1) 0ms, 100%
295 Find Median from Data Stream bst time add O(logN) find O(1) space O(N) 108ms, 67%
295 Find Median from Data Stream heap time add O(logN) find O(1) space O(N) 100ms, 91%
297 Serialize and Deserialize Binary Tree time O(N) space O(N) 24ms, 62%
300 Longest Increasing Subsequence
300 dp time:O(N^2) space:O(N) 16ms 55%
300 dp+binary search time:O(NlogN) space:O(N) ~0ms 100%
315 Count of Smaller Numbers After Self FenwickTree time O(NlogN) space O(N) 36ms 48%
322 Coin Change dp/dfs+greedy time:O(size_array*amount) space:O(amount) 4ms 99%
324 Wiggle Sort II time O(N) space O(1) 124ms 11%
326 Power of Three math time O(1) space O(1) 88ms 20%
329 Longest Increasing Path in a Matrix dp+dfs time O(COLS* ROWS) space O(COLS*ROWS) 32ms 67%
334 Increasing Triplet Subsequence math time O(N) space O(1) 8ms
341 Flatten Nested List Iterator stack 20ms 34%
344 Reverse String string time O(N) space O(N) 4ms 100%
347 Top K Frequent Elements hash map + heap time O(NlogK) space O(N) 20ms 44%
347 Top K Frequent Elements hash map + sort time O(NlogN) space O(N) 12ms 99%
349 Intersection of Two Arrays set time:O(M+N) space:O(M+N) 4ms 100%
350 Intersection of Two Arrays II
350 sort+two pointer time: O(max(NlogN,MlogM)) space:O(max(N,M)) 8ms 36%
350 map time:O(N+M) space:O(max(N,M)) 4ms 100%
371 Sum of Two Integers xor time = space = O(1) 0ms 100%
378 Kth Smallest Element in a Sorted Matrix binary search time O(log(max-min)* N*logN) space O(1) 32ms 57%
380 Insert Delete GetRandom O(1) hashmap + array 99%
384 Shuffle an Array time O(N) space O(N) 228ms,48%
387 First Unique Character in a String hasp map time O(N) space O(1) 24ms 98%
395 Longest Substring with At Least K Repeating Characters dfs time O(26*N) space O(N) 0ms 100%
412 Fizz Buzz math time O(N) space O(1) 4 ms 76%
454 4Sum II hashmap time O(N^2) space O(N^2) 100 ms 94.50%
593 Valid Square math 100%
771 Jewels and Stones hashtable time O(M+N) space O(1) 4ms,98%