This is the repository to record and share my LeetCode practice. It's the first step for me to become a software engineer.
The practice is listed based on different topics. I start from easy to medium, finally trying to get rid of the hard problems. The problems in each topic are listed in numerical order.
I use python to solve each answer. As the popular saying goes:
Life is short, you need python.
You can see my attempts for each problem in the Method section, as well as the final solution in Solution part.
Final solutions are mostly inspired from the discussion at LeetCode platform, with small
modifications based on my understanding and coding style.
I believe self-implementation is as important as coming up with great ideas in terms of solving a problem. Therefore it's highly recommended to write your own version of solutions instead of simply copying the codes. Coding style is another essential part to focus on :)
My harvests for each practice are summarized here.
- Array
- Backtracking
- Dynamic Programming
- Tree
- String
- Hash Table
- Math
- Divide and Conquer
- Design
- Order
- Leetcode Contest
- Tree traversal (pre/in/post/level order)
- sliding window (dict/counter + two pointers)
set(zip(*board)), set(map(tuple, board))
- binary search:
lo, hi=0, len(nums)-1
while lo<hi:
mid=(lo+hi)/2
if condition...:
lo=mid+1
else:
hi=mid
return lo
- contiguous subarray: preSum
- sum of same length: sliding window
| Number | Name | Date |
|---|---|---|
| 017 | Letter Combinations of a Phone Number | 2017.8.9 |
| 022 | Generate Parentheses | 2017.8.9 |
| 037 | Sudoku Solver | 2018.5.15 |
| 051 | N-Queens | 2018.3.27 |
| 060 | Permutation Sequence | 2017.8.10 |
| 077 | Combinations | 2017.8.10 |
| 089 | Gray Code | 2017.8.10 |
| 093 | Restore IP Addresses | 2017.8.13 |
| 131 | Palindrome Partitioning | 2017.8.13 |
| 357 | Count Numbers with Unique Digits | 2017.8.14 |
| 401 | Binary Watch | 2017.8.15 |
| 526 | Beautiful Arrangement | 2017.8.16 |
- zero
- base case
''.join(s)
s.split()
map(str/int/function, iterable)
ord(), chr()
string.upper()/lower()
zip()/zipped(*)
any()/all()
sorted(iterable, key=len/lambda..., reverse=True)
set()
collections.defaultdict(int/list/lambda...)
collections.Counter()
d.keys()/values()/items()/elements()
set1()/dict1() +/-/&/| set2()/dict2()
sorted(d.keys(), key=lambda i: (-d[i], i))[:k]
- Division
if token=='/':
if t2/t1<0 and t2%t1:
val=str(t2/t1+1)
else:
val=str(t2/t1)
- binary search
- mergesort and count/Binary indexed tree(bisect.bisect_right(s, num))
- defensive coding:
if not hp or hp[0]:
...
while hp:
hp.pop()
...
| Number | Name | Date |
|---|---|---|
| 327 | Count of Range Sum | 2018.2.5 |
| 084 | Largest Rectangle in Histogram | 2018.2.5 |
| 493 | Reverse Pairs | 2018.2.5 |
| 315 | Count of Smaller Numbers After Self | 2018.2.5 |
| 004 | Median of Two Sorted Arrays | 2018.2.7 |
| 023 | Merge k Sorted Lists | 2018.2.7 |
| 218 | The Skyline Problem | 2018.2.9 |
| 312 | Burst Balloons | 2018.2.9 |
- trade-off between functions
| Number | Name | Date |
|---|---|---|
| 155 | Min Stack | 2018.1.23 |
| 170 | Two Sum III - Data structure design | 2018.1.24 |
| 208 | Implement Trie (Prefix Tree) | 2018.1.26 |
| 211 | Add and Search Word - Data structure design | 2018.1.26 |
| 225 | Implement Stack using Queues | 2018.1.28 |
| 232 | Implement Queue using Stacks | 2018.1.28 |
| 244 | Shortest Word Distance II | 2018.1.30 |
| 251 | Flatten 2D Vector | 2018.2.1 |
| 146 | LRU Cache | 2018.2.20 |
| 297 | Serialize and Deserialize Binary Tree | 2018.2.20 |
| 341 | Flatten Nested List Iterator | 2018.2.21 |
| 295 | Find Median from Data Stream | 2018.2.21 |
- dummy node:
dummy=ListNode(0)
dummy.next=head
# code here
...
return dummy.next
- fast and slow(prev) (cycle, mid node)
- int(binary string, 2)
- bin(int) -> string
- dfs and bfs iteration:
while stack:
x, y=stack.pop()
for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if x+dx>=0 and x+dx<m and y+dy>=0 and y+dy<n and grid[x+dx][y+dy]=='1':
grid[x+dx][y+dy]='0'
stack.append((x+dx, y+dy))
- bit manipulation:
delete the last zero:
n&=n-1
| Number | Name | Date | Topics |
|---|---|---|---|
| 010 | Regular Expression Matching | 2018.2.14 | Dynamic Programming, String, Backtracking |
| 019 | Remove Nth Node From End of List | 2018.1.16 | Linked List, Two Pointers |
| 021 | Merge Two Sorted Lists | 2018.1.17 | Linked List |
| 024 | Swap Nodes in Pairs | 2018.1.17 | Linked List |
| 061 | Rotate List | 2018.1.16 | Linked List, Two Pointers |
| 072 | Edit Distance | 2018.2.14 | Dynamic Programming, String |
| 082 | Remove Duplicates from Sorted List II | 2018.1.19 | Linked List |
| 083 | Remove Duplicates from Sorted List | 2018.1.19 | Linked List |
| 085 | Maximal Rectangle | 2018.2.14 | Dynamic Programming, Array, Hash Table, Stack |
| 086 | Partition List | 2018.1.19 | Linked List, Two Pointers |
| *092 | Reverse Linked List II | 2018.1.19 | Linked List |
| 109 | Convert Sorted List to Binary Search Tree | 2018.1.20 | Linked List, Depth-first Search |
| 115 | Distinct Subsequences | 2018.2.18 | Dynamic Programming, String |
| *126 | Word Ladder II | 2018.2.3 | Array, String, Backtracking, Breadth-first Search |
| 127 | Word Ladder | 2018.1.20 | Breadth-first Search |
| 130 | Surrounded Regions | 2018.1.21 | Breadth-first Search, Depth-first Search |
| 133 | Clone Graph | 2018.1.21 | Breadth-first Search, Depth-first Search, Graph |
| 134 | Gas Station | 2018.1.21 | Greedy |
| 137 | Single Number II | 2018.1.21 | Bit Manipulation |
| 141 | Linked List Cycle | 2018.1.21 | Linked List, Two Pointers |
| 142 | Linked List Cycle II | 2018.1.22 | Linked List, Two Pointers |
| 143 | Reorder List | 2018.1.22 | Linked List |
| 147 | Insertion Sort List | 2018.1.23 | Linked List, Sort |
| 148 | Sort List | 2018.1.23 | Linked List, Sort |
| 149 | Max Points on a Line | 2018.7.16 | Hash Table, Math |
| 150 | Evaluate Reverse Polish Notation | 2018.1.23 | Stack |
| *156 | Binary Tree Upside Down | 2018.1.23 | Tree |
| 157 | Read N Characters Given Read4 | 2018.1.23 | String |
| 160 | Intersection of Two Linked Lists | 2018.1.23 | Linked List |
| 161 | One Edit Distance | 2018.1.24 | String |
| 163 | Missing Ranges | 2018.1.24 | Array |
| 186 | Reverse Words in a String II | 2018.1.24 | String |
| 190 | Reverse Bits | 2018.1.25 | Bit Manipulation |
| 191 | Number of 1 Bits | 2018.1.25 | Bit Manipulation |
| 200 | Number of Islands | 2018.1.25 | Breadth-first Search, Depth-first Search, Union Find |
| 201 | Bitwise AND of Numbers Range | 2018.1.25 | Bit Manipulation |
| 203 | Remove Linked List Elements | 2018.1.25 | Linked List |
| 206 | Reverse Linked List | 2018.1.22 | Linked List |
| 207 | Course Schedule | 2018.1.25 | Breadth-first Search, Depth-first Search, Graph, Topological Sort |
| 210 | Course Schedule II | 2018.1.26 | Breadth-first Search, Depth-first Search, Graph, Topological Sort |
| 215 | Kth Largest Element in an Array | 2018.1.27 | Divide and Conquer, Heap |
| 220 | Contains Duplicate III | 2018.1.28 | Binary Search Tree |
| 234 | Palindrome Linked List | 2018.1.28 | Linked List, Two Pointers |
| 237 | Delete Node in a Linked List | 2018.1.29 | Linked List |
| 240 | Search a 2D Matrix II | 2018.1.29 | Binary Search, Divide and Conquer |
| 241 | Different Ways to Add Parentheses | 2018.1.30 | Divide and Conquer |
| 243 | Shortest Word Distance | 2018.1.30 | Array |
| 245 | Shortest Word Distance III | 2018.1.30 | Array |
| 246 | Strobogrammatic Number | 2018.1.31 | Hash Table, Math |
| 247 | Strobogrammatic Number II | 2018.1.31 | Recursion, Math |
| 249 | Group Shifted Strings | 2018.2.1 | Hash Table, String |
| 250 | Count Univalue Subtrees | 2018.2.1 | Tree |
| 252 | Meeting Rooms | 2018.2.1 | Sort |
| 253 | Meeting Rooms II | 2018.2.1 | Heap, Greedy, Sort |
| 254 | Factor Combinations | 2018.2.1 | Backtracking |
| *255 | Verify Preorder Sequence in Binary Search Tree | 2018.2.2 | Stack, Tree |
| 256 | Paint House | 2018.2.2 | Dynamic Programming |
| 259 | 3Sum Smaller | 2018.2.8 | Array, Two Pointers |
| 265 | Paint House II | 2018.2.2 | Dynamic Programming |
| 266 | Palindrome Permutation | 2018.2.8 | Hash Table |
| 267 | Palindrome Permutation II | 2018.2.8 | Backtracking |
| 270 | Closest Binary Search Tree Value | 2018.2.8 | Binary Search, Tree |
| 272 | Closest Binary Search Tree Value II | 2018.2.8 | Stack, Tree |
| 292 | Nim Game | 2018.4.4 | Brainteaser |
| 305 | Number of Islands II | 2018.7.24 | Union Find |
| 307 | Range Sum Query - Mutable | 2018.2.26 | Binary Indexed Tree |
| 308 | Range Sum Query 2D - Mutable | 2018.2.27 | Binary Indexed Tree |
| 316 | Remove Duplicate Letters | 2018.5.7 | Stack, Greedy |
| 323 | Number of Connected Components in an Undirected Graph | 2018.3.22 | Breadth-first Search, Depth-first Search, Graph |
| 340 | Longest Substring with At Most K Distinct Characters | 2018.7.23 | Hash Table, String |
| 356 | Line Reflection | 2018.7.16 | Hash Table, Math |
| 359 | Logger Rate Limiter | 2018.7.23 | Hash Table, Design |
| 378 | Kth Smallest Element in a Sorted Matrix | 2018.2.18 | Binary Search, Heap |
| 387 | First Unique Character in a String | 2018.5.7 | Hash Table, String |
| 398 | Random Pick Index | 2018.7.8 | Reservoir Sampling |
| 399 | Evaluate Division | 2018.7.23 | Depth-first Search, Union Find |
| 402 | Remove K Digits | 2018.6.17 | Stack, Greedy |
| 406 | Queue Reconstruction by Height | 2018.5.7 | Greedy |
| 418 | Sentence Screen Fitting | 2018.7.23 | Dynamic Programming |
| 461 | Hamming Distance | 2018.4.4 | Bit Manipulation |
| 477 | Total Hamming Distance | 2018.4.4 | Bit Manipulation |
| 490 | The Maze | 2018.7.23 | Breadth-first Search, Depth-first Search |
| 496 | Next Greater Element I | 2018.7.23 | Stack |
| 499 | The Maze III | 2018.7.23 | Breadth-first Search, Depth-first Search |
| 503 | Next Greater Element II | 2018.7.23 | Stack |
| 505 | The Maze II | 2018.7.23 | Breadth-first Search, Depth-first Search |
| 684 | Redundant Connection | 2018.7.23 | Union Find |
| 685 | Redundant Connection II | 2018.7.23 | Union Find |
| 719 | Find K-th Smallest Pair Distance | 2018.2.18 | Binary Search, Heap |
| 737 | Sentence Similarity II | 2018.7.28 | Union Find, Depth-first Search |
| 753 | Cracking the Safe | 2018.7.23 | Depth-first Search |
| 763 | Partition Labels | 2018.5.7 | Two Pointers, Greedy |
| 864 | Random Pick with Blacklist | 2018.7.8 | Hash Table, Random |