- 哈希表（Hash Table）
- 哈希表（Hash Table），也叫散列表，是根据关键码值（key value）而直接进行访问的数据，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫作散列函数（Hash Function），存放记录的数组叫哈希表（或散列表）
- 工程实践：电话号码薄、用户信息表、缓存（LRU Cache）、键值对存储(Redis)等。
- 参考链接
-
树
- 有环的树被称为图
-
二叉树
-
二叉树遍历方式
-
前序（Pre-order）：根 - 左 - 右
# 示例代码 def preorder(self, root): if root: self.traverse_path.append(root.val) self.preorder(root.left) self.preorder(root.right)
-
中序（In-order）：左 - 根 - 右
# 示例代码 def inorder(self, root): if root: self.inorder(root.left) self.traverse_path.append(root.val) self.inorder(root.right)
-
后序（Post-order）：左 - 右 - 根
# 示例代码 def postorder(self, root): if root: self.postorder(root.left) self.postorder(root.right) self.traverse_path.append(root.val)
-
-
-
二叉搜索树
- 二叉搜索树，也称二叉排序树、有序二叉树（Ordered Binary Tree）、排序二叉树（Sorted Binary Tree），是指一颗空树或者具有下列性质 的二叉树。（空树就是二叉搜索树）
- 左子树上所有节点的值均小于它的根节点的值；
- 右子树上所有节点的值均大于它的根节点的值；
- 以此类推：左、右子树也分别为二叉查找树。（这就是重复性）
- 中序遍历：升序排列
- 常见操作
- 查询，时间复杂度 O(logn)
- 插入新节点（创建），时间复杂度 O(logn)
- 删除，时间复杂度 O(logn) 二叉搜索树的特点就是大部分的操作的时间复杂度都是 O(logn)
- 二叉搜索树，也称二叉排序树、有序二叉树（Ordered Binary Tree）、排序二叉树（Sorted Binary Tree），是指一颗空树或者具有下列性质 的二叉树。（空树就是二叉搜索树）
-
其它
-
思考题
- 树的面试题解法一般都是递归，为什么？
- 堆（Heap）
- Heap：可以迅速找到一堆数中的最大或者最小值的数据结构物
- 将根节点最大的堆叫做顶推或大根堆，根节点最小的堆叫做小顶堆或者小根堆。常见的堆有二叉堆、斐波那契堆等
- 假设是大顶堆，则常见操作（API）：
- find-max: O(1)
- delete-max: O(logn)
- insert(creat): O(logn) or O(1)
- 不同实现的比较：https://en.wikipedia.org/wiki/Heap_(data_structure)
- 参考链接
- 二叉堆
- 二叉堆是通过完全二叉树来实现（注意：不是二叉搜索树）
- 二叉堆（大顶）它满足以下性质
- 是一颗完全树
- 树中任意节点的值总是 >= 其子节点的值
- 二叉堆的实现细节
- 二叉堆一般都是通过
数组来实现的 - 假设「第一个元素」 在数组中的索引未 0 的话，则父节点和子节点的位置关系如下：
- 索引为
i的左孩子的索引为2 * i + 1 - 索引为
i的右孩子的索引为2 * i + 2 - 索引为
i的父节点的索引为floor((i - 1) / 2)
- 索引为
- 二叉堆一般都是通过
- 常用操作
- Insert 插入操作，时间复杂度 O(logn)
- 新元素一律插入到堆的尾部
- 依次向上调整整个堆的结构（一直到根即可）HeapifyUp
- Delete Max 删除堆顶操作
- 将堆尾元素替换到顶部（即堆顶被替换删除掉）
- 依次从根部向下调整整个堆的结构（一直到堆尾即可）HeapifyDown
- Insert 插入操作，时间复杂度 O(logn)
- 图的属性和分类：待补充......
- 基于图相关的算法：待补充......
- 参考链接
-
写一个关于 HashMap 的小总结（Java）。参考 史上最全的 Java 容器集合之 HashMap（源码解读）
-
class Solution: def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == sorted(t) def isAnagram1(self, s: str, t: str) -> bool: d = collections.defaultdict(int) for _s in s: d[_s] += 1 for _t in t: if _t not in d: return False d[_t] -= 1 return not any(d.values()) def isAnagram2(self, s: str, t: str) -> bool: return collections.Counter(s) == collections.Counter(t)
-
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: # hash，O(n) d = {} for i, n in enumerate(nums): if target - n in d: return [d[target - n], i] d[n] = i return []
-
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution: def preorder(self, root: 'Node') -> List[int]: # 递归 if not root: return [] res = [root.val] for child in root.children: res.extend(seld.preorder(child)) return res # 或者，用一行代码搞定 # return root and sum([[root.val], *map(self.preorder, root.children)], []) or [] def preorder1(self, root: 'Node') -> List[int]: # 迭代 res, stack = [], root and [root] while stack: node = stack.pop() res.append(node.val) stack.extend(reversed(node.children)) return res
-
自学 HeapSort
-
class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: # 时间复杂度：O(NKlogK)，其中 NN 是 strs 的长度，而 K 是 strs 中字符串的最大长度。当我们遍历每个字符串时，外部循环具有的复杂度为 O(N)。然后，我们在 O(KlogK) 的时间内对每个字符串排序。 # 空间复杂度：O(NK)，排序存储在 ans 中的全部信息内容。 ans = collections.defaultdict(list) for s in strs: ans[tuple(sorted(s))].append(s) return list(ans.values())
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: # 递归 if not root: return [] res = [] res.extend(self.inorderTraversal(root.left)) res.append(root.val) res.extend(self.inorderTraversal(root.right)) return res def inorderTraversal1(self, root: TreeNode) -> List[int]: # 迭代 ans, stack = [], [] while stack or root: if root: stack.append(root) root = root.left else: _root = stack.pop() ans.append(_root.val) root = _root.right return ans
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: # 递归 if not root: return [] ans = [] ans.append(root.val) ans.extend(self.preorderTraversal(root.left)) ans.extend(self.preorderTraversal(root.right)) return ans # 或者，一行代码搞定 # return root and [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) or [] def preorderTraversal1(self, root: TreeNode) -> List[int]: # 迭代 ans, stack = [], root and [root] while stack: _root = stack.pop() if _root: ans.append(_root.val) stack.append(_root.right) stack.append(_root.left) return ans
-
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution: def levelOrder(self, root: 'Node') -> List[List[int]]: q, ans = [root], [] while any(q): ans.append([n.val for n in q]) q = [child for node in q for child in node.children if child] return ans