开启刷题之路,这里会记录博主在LeetCode上刷题时写下的题解和代码(c++11) 建议先看以下文章:
博主对于所有的算法,尽可能地对运行时间进行了优化,即faster than 97.00% of C++ online submissions at least. 之所以有部分不是100%,是因为同样的代码在不同时间段提交,在LeetCode的runtime可能不同,即使是用别人beats 100%的代码提交也是一样
题解主要包括
- 解题思路
- 代码
- 时间/空间复杂度分析
- Corner Cases
Note:
- 题解中的时间复杂度和空间复杂度均是最坏情况下的
- 过于简单的题,博主不会写题解
- 由于github的repo更新,部分github链接已失效,可以点我查看
题目 | 难度 | topic |
---|---|---|
11. Container With Most Water | Medium | 数组、two pointers |
23. Merge k Sorted Lists | hard | 链表、分治、堆 |
210. Course Schedule II | Medium | 图、拓扑排序、深度优先遍历、广度优先遍历 |
218. The Skyline Problem | Hard | 分治、堆、线段树、树状数组、扫描线 |
268. Missing Number | Easy | 数组、数学、位运算 |
315. Count of Smaller Numbers After Self | hard | 数组、排序、分治、二叉搜索树、树状数组、线段树 |
349. Intersection of Two Arrays | Easy | 排序、哈希表、two pointers、数组 |
1218. Longest Arithmetic Subsequence of Given Difference | Medium | 数学、动态规划 |
Binary Search
- 34. Find First and Last Position of Element in Sorted Array(Medium)
- 300. Longest Increasing Subsequence(Medium)
Bit Operation
Sort
DFS
BFS
Linked List
- 2. Add Two Numbers
- 19. Remove Nth Node From End of List(Medium)
- 138. Copy List with Random Pointer(Medium)
- 141. Linked List Cycle(Easy)
- 142. Linked List Cycle II(Medium)
- 148. Sort List
- 160. Intersection of Two Linked Lists(Easy)
- 206. Reverse Linked List
- 234. Palindrome Linked List(Easy)
- 328. Odd Even Linked List(Medium)
Greedy
Divide and Conquer
- 21. Merge Two Sorted Lists(Easy)
- 108. Convert Sorted Array to Binary Search Tree(Easy)
- 240. Search a 2D Matrix II(Medium)
- 395. Longest Substring with At Least K Repeating Characters(Medium)
Dynamic planning
- 3. Longest Substring Without Repeating Characters(Medium)
- 5. Longest Palindromic Substring(Medium)
- 10. Regular Expression Matching
- 44. Wildcard Matching(Hard)
- 46. Permutations
- 53. Maximum Subarray (easy)
- 62. unique-paths (Medium)
- 70. Climbing Stairs(Easy)
- 91. Decode Ways(Medium)
- 121. Best Time to Buy and Sell Stock(Easy)
- 123. Best Time to Buy and Sell Stock III(Hard)
- 139. Word Break(Medium)
- 140. Word Break II(Hard)
- 198. House Robber(Easy)
- 279. Perfect Squares(Medium)
- 300. Longest Increasing Subsequence(Medium)
Backtracking
Math
Graph
Tree
- 94. Binary Tree Inorder Traversal(Medium)
- 101. Symmetric Tree(Easy)
- 102. Binary Tree Level Order Traversal(Medium)
- 104. Maximum Depth of Binary Tree(Easy)
- 116. Populating Next Right Pointers in Each Node
- 208. Implement Trie (Prefix Tree)
- 230. Kth Smallest Element in a BST(Medium)
- 236. Lowest Common Ancestor of a Binary Tree(Medium)
String
- 8. String to Integer (atoi)
- 13. Roman To Integer
- 14. Longest Common Prefix
- 387. First Unique Character in a String(修正:其中提到的时间复杂度为O(n))
- 395. Longest Substring with At Least K Repeating Characters(Medium)
Array
- 15. 3Sum(Medium)
- 41. First Missing Positive(Hard)
- 84. Largest Rectangle in Histogram(hard)
- 88. Merge Sorted Array(Easy)
- 189. Rotate Array(Easy)
- 380. Insert Delete GetRandom O(1)(Medium)
HashTable
Stack
- 42. Trapping Rain Water(Hard)
- 84. Largest Rectangle in Histogram(hard)
- 94. Binary Tree Inorder Traversal(Medium)
Two Pointers
- 15. 3Sum(Medium)
- 19. Remove Nth Node From End of List(Medium)
- 42. Trapping Rain Water(Hard)
- 141. Linked List Cycle(Easy)
- 142. Linked List Cycle II(Medium)
- 234. Palindrome Linked List(Easy)