# 算法 ## 1. 算法复杂度 一些递归算法的复杂度 | 算法 | 时间复杂度 | | ---------- | ---------- | | 二分 | O(log n) | | 二叉树遍历 | O(n) | | 二维搜索 | O(n) | | 归并排序 | O(n longn) | ## 2. 数组与链表 ### [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/) 迭代解法 ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; ListNode help; while(cur!=null){ help = cur.next; // 记录下一个的节点 cur.next = pre; // 当前节点指向前面的节点 // 更新 cur 和 pre pre = cur; cur = help; } return pre; } } ``` 递归解法 ### [24. 两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs/) ### [141. 环形链表](https://leetcode-cn.com/problems/linked-list-cycle/) ### [142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/) ### [25. K 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/) ## 3. 堆栈和队列 ## 4.广度与深度搜索 ### BFS模板 ```python def BFS(graph,start,end): queuq = [] queue.append([start]) visited.add(start) while queue: node = queue.pop() visited.add(node) process(node) nodes = generate_related_nodes(node) queue.push(nodes) ``` ### DFS模板 #### 递归写法 ```python visited = set() def DFS(node,visited): visited.add(node) # process current node hear. for next_node in node.children(): if not next_node in visited: DFS(next_node,visited) ``` #### 非递归写法 ```python def DFS(self,tree): if tree.root is None: return [] visited,stack = [],[tree.root] while stack: node = stack.pop() visited.add(node) process(node) nodes = generate_related_nodes(node) stack.push(nodes) ``` ### [102.二叉树层次遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/) ```python class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: # BFS 解法 from collections import deque if root==None: return [] queue = deque() queue.append(root) # 结果 result = [] while queue: res_temp = [] for i in range(len(queue)): # 取元素 node = queue.popleft() # 本节点需要的操作 res_temp.append(node.val) # 获取下层的节点,并推入队列 if node.left != None: queue.append(node.left) if node.right != None: queue.append(node.right) result.append(res_temp) return result ``` ```python class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] # DFS 递归写法 self.result = [] self.__dfs(root,0) return self.result # 当前节点,当前层数 def __dfs(self,node,level): # 递归结束条件,当前节点为空 if not node: return # 当前节点操作 # 1. 当前层数为被访问过 if len(self.result) < level + 1: self.result.append([]) # 2. 添加到指定层数 self.result[level].append(node.val) # 下一步操作,递归 self.__dfs(node.left,level + 1) self.__dfs(node.right,level + 1) ``` ### [22. 括号生成](https://leetcode-cn.com/problems/generate-parentheses/) ```python class Solution: def generateParenthesis(self, n: int) -> List[str]: # 递归解法 self.res = [] self._gen('',n,n) return self.res # 递归函数 def _gen(self,now_s,l_rest,r_rest): if r_rest == 0: self.res.append(now_s) if l_rest > 0: self._gen(now_s+'(',l_rest-1,r_rest) if l_rest < r_rest: self._gen(now_s+')',l_rest,r_rest-1) ``` ## 5. 位运算 常用操作: - `x&1==1 OR ==0` 判断奇偶 - `x=x&(x-1)` 清零最低位的1 - `x&-x` 得到最低位的1的位置 ## 6. 动态规划 1. 递归+记忆化 - > 递推 2. 状态的定义: opt[n] dp[n] fib[n] 3. 状态转移方程: opt[n] = best_of(opt[n-1],opt[n-2], ......) 4. 最右子结构 - 回溯 - 重复计算 - 贪心 - 永远局部最优 - DP - 记录局部最优子结构 / 多种记录值 ## 7. 并查集 数据结构: 数组 初始化: 数组的每个元素指向自己 查询: 不断查询元素的父亲,直到找到rooter 合并: 将新的并查集的rooter指向旧的并查集的rooter rooter: 指向自己 ## 8. LRU Cache --- 转载至CSDN博主：[[李唐敏民](https://blog.csdn.net/qq_39041210 "李唐敏民")] --- 最后修改：2021 年 02 月 18 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
1 条评论
在畅想未来时需警惕乌托邦式理想化。