1.栈和队列的基本实现和特性1.1 基本性质Stack：先入后出；添加、删除为$O(1)$，查询为$O(n)$ Queue ：先入先出；添加、查询为$O(1)$ 栈 队列 1.2 双端队列 插入和删除是 $O(1)$，查询为 $O(n)$ 1.3 工程实现 Java 的 Stack 源码 Java 的 Queue 源码 Python 的 heapq 高性能的 container 库 1.4 优先队列Java 的 PriorityQueue 文档 插入操作： $O(1)$ 取出操作： $O(log~n)$，按照元素的优先级取出 底层具体实现的数据结构较为多样和复杂：heap、bst、treap 1.5 复杂度分析Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell (bigocheatsheet.com) 2.题目2.1 有效括号20. 有效的括号 - 力扣（LeetCode） 123456给定一个只包括 '('，')'，&# ...

1.树1.1 树的概念树和图的区别：有没有环； Linked List是特殊化的Tree；Tree是特殊化的Graph 1.2 二叉树结点定义 12345class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, None 123456struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}} 123456789public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = null; this.right = null; ...

1.基本特性1.1 Hash Table哈希表（Hash table），也叫散列表，是根据关键码值（Key value）而直接进行访问的数据结构。它通过把关键码值映射到一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（Hash Function），存放记录的数组叫做哈希表（或散列表）。 hash函数 hash冲突 2.示例2.1 有效字母异位词242. 有效的字母异位词 - 力扣（LeetCode） 123给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。 12345678910111213141516171819202122232425262728293031323334// 1.暴力 sort， sorted_str是否相等？ O(NlogN)// 2.hash, map --> 统计每个字符的频次// 第一个字符串，遇到一个字符加一，第二个字符串，遇到字符减一class Solution {public: // 1.暴力，排序 ...

递归 - 循环：通过函数体来进行循环 重复性 1.递归：盗梦空间1.1 特点 向下进入到不同梦境；向上又回到原来的一层； 通过声音同步回到上一层 每一层的环境和周围的人都是一份拷贝、主角等几人穿越不同层级的梦境（发生和携带变化） 1.2 计算 n!12345def Factorial(n): if n <= 1: return 1 return n * Factorial(n - 1) 递归栈 1.3 递归代码模板12345678910111213def recursion(level, param1, param2, ...): # 1.recursion terminator (递归终止条件) if level > MAX_LeVEL: process_result return # 2.process logic in current level (处理当前层逻辑) process(level, data, ...) # 3.drill down (下探到下一层) self.recursion(level + 1, p1, . ...

1.搜索1.1 遍历搜索在树（图/状态集）中虚招特定结点 每个结点都要访问一次 每个结点仅仅要访问一次 对于结点的访问顺序不同，分为DFS，BFS 1.2 深度优先搜索 (Depth First Search) 示例代码： 123456789101112def dfs (node): if node in visited: # already visited return visited.add(node) # process current node # ... dfs(node.left) dfs(node.right) 递归写法 123456789101112visited = set()def dfs(node, visited): visited.add(node) # process currend node here ... for next_node in node.children(): if not next_node in visited: dfs(next_node, visited) ...

1.分治本质上就是一种递归 找问题重复性，分解问题，组合每个子问题结果 递归状态树 1.1 分治 Divide & Conquer 1.2 分治代码模板1234567891011121314151617181920def divide_conquer(problem, param1, param2, ...): # 1.recursion terminator (递归终止条件) if problem is None: print_result return # 2.prepare data (拆分问题) data = prepare_data(problem) subproblems = split_problem(problem, data) # 3.conquer subproblems (调字问题的递归函数) subresult1 = self.divide_conquer(subproblems[0], p1, ...) subresult1 = self.divide_conquer(subproblems[0], p1, ... ...

1.贪心算法1.1 概念贪心算法是一种在每一步选择中都采取在当前状态下最好或最优 (即最有利)的选择，从而希望导致结果是全局最好或最优的算法。 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。 贪心：当下做局部最优判断 回溯：能够回退 动态规划：最有判断 + 回退 贪心法可以解决一些最优化问题，如: 求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案 一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。 1.2 举例：coin change322. 零钱兑换 - 力扣（LeetCode） 12345给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以 ...

1.二分查找1.1二分查找的前提 目标函数单调性（单调递增或递减） 存在上下界（bounded） 能够通过索引访问（index accessible） 1.2 代码模板1234567891011left, right = 0, len(array) - 1while left <= right: mid = (left + right) / 2 if array[mid] == target: # find the target break or return result elif array[mid] < target: left = mid + 1 else: right = mid - 1 1.3 示例在递增数组里 [10,14,19,26,27,31,33,35,42,44] 中， 查找31 2.题目2.1 x的平方根69. x 的平方根 - 力扣（LeetCode） 12345给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。注意：不允许使用任何内置指数 ...

1.复习分治、回溯、递归、动态规划，没有本质上的区别，主要是一些小细节不一样 1.1 递归递归代码模板： 12345678910111213def recursion(level, param1, param2, ...): # 1.recursion terminator (递归终止条件) if level > MAX_LeVEL: process_result return # 2.process logic in current level (处理当前层逻辑) process(level, data, ...) # 3.drill down (下探到下一层) self.recursion(level + 1, p1, ...) # 4.reverse the current level status if needed (清理当前层) 1.2 分治 分治代码模板： 1234567891011121314151617181920def divide_conquer(problem, param1, param2, ...): # 1.rec ...

1.字典树（Trie）1.1 字典树数据结构（1）树 Tree （2）二叉搜索树注意：是根节点大于左子树中的全部结点，小于右子树的全部结点，不是左儿子和右儿子。 （3）字典树字典树，即 Trie 树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。 它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。 结点可以存储额外信息： 如下图中，数字表示单词出现的频次 （4）结点的内部实现 1.2 核心思想Trie树的核心思想：空间换时间 利用字符串的公共前缀来降低查询时间的开销，以达到提高效率的目的 1.3 基本性质 结点本身不存完整单词 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串 每个结点的所有子结点路径代表的字符都不相同 1.4 字典树实现python代码模板 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647class Trie: ...

1.初级搜索 朴素搜索 优化方式：不重复（fibonacci）、剪枝（生成括号问题） 搜索方向： BFS：深度优先搜索 (depth first search)，栈 BFS：广度优先搜索 (breadth first search)，队列 高级搜索：双向搜索、启发式搜索（优先队列） Coin change（零钱置换）的状态树 DFS代码 - 递归写法 123456789101112131415visited = set()def dfs(node, visited): # terminator if node in visited: return visited.add(node) # process currend node here ... for next_node in node.children(): if not next_node in visited: dfs(next_node, visited) DFS代码 - 非递归写法 1234567891011121314151617def dfs(self, tre ...

0.复习树 二叉树 二叉树遍历 前序（pre-order）：根 → 左 → 右 中序（in-order）：左 → 根 → 右 后序（post-order）：左 → 右 → 根 123456def preorder(self, root): if root: self.traverse_path.append(root, val) self.preorder(root.left) self.preorder(root.right) 12345def inorder(self, root): if root: self.inorder(root.left) self.traverse_path.append(root, val) self.inorder(root.right) 12345def postorder(self, root): if root: self.postorder(root.left) self.postorder(root.right) self.traverse_path.append(root, v ...

1.位运算符 如何从十进制转换为二进制 机器里的数字表示方式和存储格式就是二进制 2.算数移位与逻辑移位 含义 运算符 示例 左移 << 0011 → 0110 右移 >> 0110 → 0011 按位或 \ 0011 \ 1011 → 1011 按位与 & 0011 & 1011→ 0011 按位取反 ~ 0011 → 1100 按位异或 (相同为0不同为1) ^ 0011 \ 1011 → 1000 3.位运算的应用3.1 XOR - 异或异或：相同为0，不同为1。也可用“不进位加法”来理解 异或的一些特点： x^0 = x x^1s = ~x (注意 1s = ~0， “全1”) x^(~x) = 1s x^x = 0 c = a ^ b → a^c = b, b^c = a (交换两个数) a^b^c = a^(b^c)=(a^b)^c (associative) 3.2 指定位置的位运算 将x最右边的 n位清零: x & (~0<< n) 获取x的第 n位 ...

1.布隆过滤器（Bloom Filter）1.1 HashTable + 拉链存储重复元素 实际应用时，更多需要存储 有还是没有，hashtable中存储有大量信息，比较占内存 1.2 Bloom Filter一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。 优点是空间效率和查询时间都远远超过一般的算法 缺点是有一定的误识别率和删除困难 插入AE元素，当测试B元素时，发现映射的二进制位为1，出现误识别； 当元素对应的二进制位为1时，此元素可能存在在布隆过滤器中； 当元素对应的二进制位有一个为0时，此元素不可能在布隆过滤器中； 布隆过滤器一般放在外面当一个缓存使用，做一个快速的判断；当B在布隆过滤器中查询到，会到DB中去查找数据。 1.3 案例 比特币 分布式系统（Map-Reduce） - Hadoop、search engin Redis缓存 垃圾邮件、评论过滤 布隆过滤器的原理和实现 使用布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重 1.4 实现 布隆过滤器 Python 实现示例 高性能布隆过滤器 Python 实现示例 ...

1.动态规划1.1 递归 & 分治递归：函数自己调用自己 12345678910111213def recursion(level, param1, param2, ...): # 1.recursion terminator (递归终止条件) if level > MAX_LeVEL: process_result return # 2.process logic in current level (处理当前层逻辑) process(level, data, ...) # 3.drill down (下探到下一层) self.recursion(level + 1, p1, ...) # 4.reverse the current level status if needed (清理当前层) 分治： 1234567891011121314151617181920def divide_conquer(problem, param1, param2, ...): # 1.recursion terminator (递归终止条件) if ...