字符串
- 几个库函数的时间复杂度：reverse/split, O(n);
- 双指针法：反转字符串、替换空格；在数组、链表中更常用
- 滑动窗口法，配合哈希表，计数器等：用于寻找子串相关的题目；
- KMP：用前缀表来对目标串的重复子串进行标记，减少滑动搜索时的后退步数；
链表
-
链表的种类主要为：单链表，双链表，循环链表
-
链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
-
链表是如何进行增删改查的。
-
数组和链表在不同场景下的性能分析。
-
链表的定义： python: class ListNode(object): self.val = val, self.next=next
-
多使用虚拟头结点；pre = ListNode(next=head)
-
多使用双指针：尤其是存在一个值index时，双指针多遍历几遍，就能O(n) 时间，O(1)空间中获得结果；
双指针法
使用双指针法能展现出效率的优势：通过两个指针在一个for循环下完成两个for循环的工作
- 使用场景：
- 数组：删除数字元素（都从0开始，fast!=val时，复制到slow），反转数组（双指针两边向中间），替换空格（从后向前替换），
- 链表：存在一个值index时，双指针多遍历几遍，就能O(n) 时间，O(1)空间中获得结果；
- N数之和篇：可以用哈希法，但是比较难，对空间占用更大；双指针注意a,b,c三个数字的去重操作；
- 常见使用方式：
- 快慢指针：快指针每次移动两步，慢指针每次移动一步，通过快慢指针的相对移动找到特定位置的节点。
- 题目：在链表中解决环形链表、链表中点、链表倒数第 k 个节点等问题时常用快慢指针，
- 对撞指针：在有序数组中！通过左右指针同时向中间移动，根据元素大小的比较来调整指针位置。
- 题目：解决两数之和、三数之和； 两数平方和
- 滑动窗口：通过维护一个窗口区间，通过移动左右指针来调整窗口大小。
- 在数组或字符串中解决子数组最大值、子字符串最大长度等问题时常用滑动窗口；
- LeetCode 209. 长度最小的子数组，LeetCode 76. 最小覆盖子串 ；找到字符串中不含重复字符的最长子串。
- 其他：
- 合并两个有序数组：将两个有序数组合并为一个有序数组时，可以使用双指针法，一个指针指向第一个数组的末尾，另一个指针指向第二个数组的末尾，根据元素大小的比较来合并数组。
- 回文字符串判断：判断一个字符串是否为回文字符串时，可以使用双指针法，一个指针从字符串头部开始，另一个指针从字符串尾部开始，同时向中间移动并比较对应位置的字符。
- 快慢指针：快指针每次移动两步，慢指针每次移动一步，通过快慢指针的相对移动找到特定位置的节点。
栈和队列
- 栈：可以用栈来实现递归：栈里面的相邻元素，符合一定条件时就消除（或者运算），持续到最后；
- 递归的实现是栈：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，
- 逆波兰表达式：输入的列表是后缀表达式，其实是用后序遍历的方式把二叉树序列化了；
- 数字元素放入栈，碰到运算符就pop2个进行运算；
- 顺序和优先级的问题：后缀表达式天然对计算机友好，不用处理；
- 单调队列：在动态数据流中维护一组元素，并保持元素的单调递增或单调递减；
- 用途：在解决一些需要在滑动窗口中找到最大值、最小值等问题时，单调队列可以帮助我们高效地维护窗口内的元素，并在O(1)时间复杂度内获取窗口的最大值或最小值。
- 其他题型也可用：计算窗口中元素的和、平均值；窗口的中位数、第k大元素
- 单调栈：解决一些需要维护栈中元素的单调性的问题时非常有用，
- 用途：找到每个元素左边或右边第一个比它大或小的元素等
- 堆 （heapq）：堆是一种特殊的树形数据结构（完全二叉树），常用于实现优先队列。在堆中，每个节点的值都大于等于/小于等于其子节点的值（最大堆/最小堆）。
- heapq 模块默认小顶堆：注意，插入堆的元素可以是元组(2,obj)，根据元组的第一个元素排序
- heapify(iterable)：将一个可迭代对象转换为堆，时间复杂度为 O(n)。
- heappush(heap, item)：向堆中插入一个元素。
- heappop(heap)：从堆中弹出并返回最小值（最小堆）或最大值（最大堆）。
- heapreplace(heap, item)：弹出并返回堆中的最小值或最大值，并将新元素插入堆中。
- nlargest(n, iterable)：返回可迭代对象中的前 n 个最大元素。
- nsmallest(n, iterable)：返回可迭代对象中的前 n 个最小元素。
- 使用场景：与优先级有关的场景
- 优先队列：可以使用堆来维护元素的优先级，使得插入和删除操作的时间复杂度为 O(log n)
- 需要找到最大值或最小值的场景中，可以使用堆来快速获取最大/最小元素，时间复杂度为 O(1)
- 在一些排序算法中，堆排序就是基于堆的一种排序算法。
- 求中位数、滑动窗口中的最大值等：可以使用堆来辅助处理
- 合并多个有序列表：如果有多个有序列表，可以使用堆来合并这些列表，实现一个整体有序的列表。通过维护一个大小为 k 的堆，每次从堆中弹出最小元素，并将其对应列表的下一个元素插入堆中，直到所有列表遍历完毕。
- 将任务按照优先级加入堆中，然后依次执行优先级最高的任务
- 求解最小的 k 个数（用小顶堆）：如果需要从一个很大的数据集中找到最小的 k 个数，可以使用堆来维护当前找到的最小的 k 个数。遍历数据集，将元素加入堆中，当堆的大小超过 k 时，弹出堆顶元素，保持堆中始终有 k 个最小元素
- 求解中位数：在动态数据流中，需要不断更新中位数时，可以使用两个堆来维护数据流的左半部分和右半部分，左半部分使用最大堆，右半部分使用最小堆，保持两个堆的大小差不超过 1。这样可以在 O(log n) 的时间复杂度内找到中位数
- 最小生成树算法：在最小生成树算法（如 Prim 算法、Kruskal 算法）中，可以使用堆来维护当前生成树与其他节点之间的最小边，从而高效地找到下一个要加入生成树的节点。
- heapq 模块默认小顶堆：注意，插入堆的元素可以是元组(2,obj)，根据元组的第一个元素排序
二叉树
- 分类：满二叉树、完全二叉树、二叉树搜索数；平衡二叉搜索树
- C++ 的mao/set/multimap,multiset的底层都是二叉树，unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表
- 存储方式：二叉树可以链式存储，也可以顺序存储（链表和数组存储，数组中用i, i2+1, i2+2）
- 遍历方式:这两种遍历是图论中最基本的两种遍历方式
- 深度优先遍历的递归法，可以用栈来实现；广度优先的递归法，用队列实现；
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 前序遍历（递归法，迭代法）:中左右
- 中序遍历（递归法，迭代法）：左中右
- 后序遍历（递归法，迭代法）：左右中
- 广度优先遍历：一层一层的去遍历。
- 层次遍历（迭代法）
二叉树递归写法的体系：三要素
- 确定递归函数的参数和返回值
- 确定终止条件：
- 确定单层递归的逻辑
二叉树迭代写法：用栈
- 普通写法：
- 前序：stack=[root],cur=stack.pop(),res.append(cur.val),stack.append(right),stack.append(left)
- 中序：while stack or cur:while cur: stack.append(cur), cur = cur.left ; else:cur = stack.pop() , res.append(cur.val), cur = cur.right
- 后序：前序改入账顺序，最后结果反转
- 统一写法：
- 在中节点入栈后，添加None标记，出栈遇到标记时，res.append(node.val)
if not root:
return []
result = []
st = [root]
while st: # 出栈顺序就是最终顺序；下面是后序
node = st.pop()
if node != None:
st.append(node) #中
st.append(None)
if node.right: #右
st.append(node.right)
if node.left: #左
st.append(node.left)
else:
node = st.pop()
result.append(node.val)
层序遍历可解决的问题：
- 二叉树的最近公共祖先（Lowest Common Ancestor）：在一个二叉树中找到两个节点的最近公共祖先。
- 二叉树的最大深度和最小深度：计算二叉树的最大深度和最小深度。
- 二叉树的层次遍历：按层级顺序遍历二叉树，常用队列实现。
- 二叉树的镜像：将二叉树镜像翻转。
- 二叉树的路径和：找到二叉树中路径和等于给定值的路径。