| type | average time complexity | worst case time complexity | best case time complexity | space complexity |
|---|---|---|---|---|
| bubbleSort | O(n^2) | O(n^2) | O(n) | O(1) |
| selectionSort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| insertionSort | O(n^2) | O(n^2) | O(n) | O(1) |
| quickSort | O(nlogn) | O(n^2) | O(nlogn) | O(nlogn) |
| mergeSort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) |
| type | average time complexity | worst case time complexity | best case time complexity | space complexity |
|---|---|---|---|---|
| binarySearch | O(logn) | O(logn) | O(1) | O(1) |
- two pointers
- sliding window
- binary search
- rotate
- kmp
- two pointers
- fast slow pointers
- binary search
- remove element（移除元素）
- binary search（二分查找）
- squares of a sorted array（有序数组的平方）
- minimum size subarray sum（长度最小子数组）
- implement linked list（实现链表及操作）
- reverse linked list（反转链表）
- remove nth from end（删除倒数第n个节点）
- cycle list（环形链表）
- implement stack using queues（用队列实现栈）
- sliding window maximum(滑动窗口最大值)
- top k frequent elements(前 K 个高频元素)
- implement queue using stacks（用栈实现队列）
- valid parentheses(有效的括号)
- evaluate reverse polish notation(逆波兰表达式求值)
-
Recursive Algorithm: it’s an Algorithm that calls itself repeatedly until the problem is solved.
- fibonacci
-
Divide and Conquer Algorithm: A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
- merge sort
-
Dynamic Programming Algorithm: a dynamic programming algorithm solves complex problems by breaking them into multiple simple subproblems and then it solves each of them once and then stores them for future use.
- climb stairs (fibonacci)
-
Greedy Algorithm: These algorithms are used for solving optimization problems. In this algorithm, we find a locally optimum solution (without any regard for any consequence in future) and hope to find the optimal solution at the global level.
- Kruskal's algorithm
-
Brute Force Algorithm: This is one of the simplest algorithms in the concept. A brute force algorithm blindly iterates all possible solutions to search one or more than one solution that may solve a function.
-
Backtracking Algorithm: It solves problems recursively and tries to solve a problem by solving one piece of the problem at a time. If one of the solutions fail, we remove it and backtrack to find another solution.
- N Queens problem
If input array is sorted then
- Binary search
- Two pointers
If asked for all permutations/subsets then
- Backtracking
If given a tree then
- DFS
- BFS
If given a graph then
- DFS
- BFS
If given a linked list then
- Two pointers
If recursion is banned then
- Stack
If must solve in-place then
- Swap corresponding values
- Store one or more different values in the same pointer
If asked for maximum/minimum subarray/subset/options then
- Dynamic programming
If asked for top/least K items then
- Heap
If asked for common strings then
- Map
- Trie
Else
- Map/Set for O(1) time & O(n) space
- Sort input for O(nlogn) time and O(1) space
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
| question | question link | category | description |
|---|---|---|---|
| 268. 丢失的数字 | https://leetcode-cn.com/problems/missing-number/ | Array | sort array, if(nums[i]!==i) return i |
| 136. 只出现一次的数字 | https://leetcode-cn.com/problems/single-number/ | Array | sort array, step in 2, if adjacent values are in pair |
| 70. 爬楼梯 | https://leetcode-cn.com/problems/climbing-stairs/ | dynamic programming | f(n) = f(n-1) + f(n-2), memo store f(n) value |
| 121. 买卖股票的最佳时机 | https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ | greedy | tracking and compare minPrice and maxProfit in one iteration |
| 53. 最大子数组和 | https://leetcode-cn.com/problems/maximum-subarray/ | dynamic programming | max sum of subArray end with nums[i], clear sum when sum < 0 |
| 141. 环形链表 | https://leetcode-cn.com/problems/linked-list-cycle/ | hashTable / slow&fast pointer | track head and comparing of exsistence / slow pointer will meet fast pointer if there is a loop (fast two steps, slow one step, break loop when fast |
| 203. 移除链表元素 | https://leetcode-cn.com/problems/remove-linked-list-elements/ | slow&fast pointer | dummy.next = head, iterate if node.next.val = val -> node.next = node.next.next |
| 100. 相同的树 | https://leetcode-cn.com/problems/same-tree/ | DFS | two stack dfs two trees compare each node |
| 53. 最大子数组和 | https://leetcode-cn.com/problems/maximum-subarray/ | dynamic programming | dp[i]=max{nums[i],dp[i−1]+nums[i]} |
| 704. 二分查找 | https://leetcode-cn.com/problems/binary-search/ | binary search | binary search sorted array |
| 27. 移除元素 | https://leetcode-cn.com/problems/remove-element/ | two pointer | remove and shift others upwards |
| 977. 有序数组的平方 | https://leetcode-cn.com/problems/squares-of-a-sorted-array/ | two pointer | two pointers from first and last then compare |
| 209. 长度最小的子数组 | https://leetcode-cn.com/problems/minimum-size-subarray-sum/ | sliding window | window on sub-array |
| 203. 移除链表元素 | https://leetcode-cn.com/problems/remove-linked-list-elements/ | linkedlist | loop node.next and compare node.next.val==target |
| 206. 反转链表 | https://leetcode-cn.com/problems/reverse-linked-list/ | linkedlist | let temp = cur.next；cur.next = pre；pre = cur；cur = temp |
| 19. 删除链表的倒数第 N 个结点 | https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/ | fast&slow pointer | fast n steps forward slow pointer,return slow when fast reach the end |
| 142. 环形链表 II | https://leetcode-cn.com/problems/linked-list-cycle-ii/ | fast&slow pointer | fast 2 steps, slow 1 step |
| 344. 反转字符串 | https://leetcode-cn.com/problems/reverse-string/ | two pointers | point to first and last element |
| 剑指 Offer 05. 替换空格 | https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/ | two pointers | increase size to result, move two pinters |
| 151. 颠倒字符串中的单词 | https://leetcode-cn.com/problems/reverse-words-in-a-string/ | two pointers | remove trailing space, reverse string, reverse each word |
| 剑指 Offer 58 - II. 左旋转字符串 | https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/ | array | reverse first k, reverse rest, reverse whole string |
| 28. 实现 strStr() | https://leetcode-cn.com/problems/implement-strstr/ | string kmp | kmp |
| 15. 三数之和 | https://leetcode-cn.com/problems/3sum/ | two pointers | for loop, sum=nums[i]+nums[left]+nums[right] |
| 232. 用栈实现队列 | https://leetcode-cn.com/problems/implement-queue-using-stacks/ | stack | use two stacks |
| 225. 用队列实现栈 | https://leetcode-cn.com/problems/implement-stack-using-queues/ | queue | use two queue, leave 1 element in main queue1 |
| 20. 有效的括号 | https://leetcode-cn.com/problems/valid-parentheses/ | stack | push open brackets to stack, return stack.length |
| 150. 逆波兰表达式求值 | https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/ | stack | push numbers to stack, calculate when math operations, push result to stack |
| 239. 滑动窗口最大值 | https://leetcode-cn.com/problems/sliding-window-maximum/ | queue | mono queue |
| 347. 前 K 个高频元素 | https://leetcode-cn.com/problems/top-k-frequent-elements/ | queue | priority queue |
| 226. 翻转二叉树 | https://leetcode-cn.com/problems/invert-binary-tree/ | recursive | swap node.left, node.right |
| 1091. 二进制矩阵中的最短路径 | https://leetcode.cn/problems/shortest-path-in-binary-matrix/ | bfs | queue structured bfs, shortest path is the first reach the end in tree |