数据结构与算法算是必考内容，如果能在笔试/面试的过程中快速找到算法题的解题思路，无疑会给面试官留下很好的印象，这类题目主要考察两个方面:
- 数据结构的掌握程度，能否熟练掌握各类数据结构的特点及操作
- 常见算法，比如贪心算法、动态规划、BFS/DFS等 面试官的考察一般是循序渐进的：
- 一般首先会考察一些数据结构的知识来看被面试者的数据结构基础
- 接下来会抛出一些常见算法，询问算法的实现细节、优缺点
- 最后从一道具体的算法题目出发，考察被面试者分析问题，对算法举一反三的运用能力，一定要多注意思考有没有更好的解法
- 上机编程，考察被面试者的编程实现功底
从上面的分析可以看出，前两项是后两项的理论基础，只有有了扎实的理论基础，后续在leetcode/牛客网刷题的时候才能事倍功半。
基础知识
编程语言
从大的层面来看，编程语言分为两类:
- 高级语言: 编译型语言、解释型语言
- 低级语言: 机器语言、汇编语言
编译型语言
编译型语言: C/C++、Pascal/Object Pascal、Golang
定义: 程序在执行之前需要一个专门的编译过程，把程序编译成为机器语言的文件，运行时则不需要重新编译，直接运行编译后的结果就可以。
- 优点: 程序执行效率高
- 缺点: 依赖于编译器，跨平台性差
解释型语言
解释型语言: Python、Matlab、Javascript、Java、Ruby、C#、PHP等
定义: 程序不需要编译，每次运行，都需要一边运行，一边翻译
- 优点: 跨平台性能好
- 缺点: 效率低
时间复杂度
算法复杂度： 输入数据为$N$时，算法运行所需花费的时间
- 统计的是算法的计算操作数量，而不是算法的运行绝对时间，计算操作数量与算法运行绝对时间成正相关，但并不相等，还受到编程语言、计算机处理器速度、运行环境等多种因素的影响。
- 体现的是计算操作随数据大小$N$变化时的变化情况，按照从小到大，常见的时间复杂度有:
空间复杂度
空间复杂度涉及的空间类型有:
- 输入空间: 存储输入数据所需的空间大小
- 暂存空间: 算法运行过程中，存储所有中间变量和对象等数据所需的空间大小
- 输出空间: 算法运行返回时，存储输出数据所需的空间
空间复杂度的计算一般只需要考虑 暂存空间 + 输出空间
根据不同来源，算法使用的内存空间分为三类：
- 指令空间: 编译后，程序指令所使用的内存空间
- 数据空间: 算法中的各项变量使用的空间
- 栈帧空间: 一般在递归时会需要考虑
按照从小到大排列，常见的算法空间复杂度有:
数据结构
在这一部分，我将回顾各种数据结构的概念以及优劣势
数组
数组一般用来存储相同类型的数据
- 特点
- 长度固定，一般不可以动态扩展
- 占据连续的内存空间
- 数据的访问方式为随机访问
- 优点: 查改效率高，通过数组名和下标进行访问，¬$O(1)$复杂度
- 缺点: 增删效率低，需要移动增删元素之后的所有元素
链表
链表相较于数组，除了数据域，还增加了指针域用于存储下一个节点的地址，链表中每一个元素都包含此节点的数据和指向下一节点地址的指针。
- 特点
- 长度可动态变化
- 非连续的内存空间
- 数据的访问方式为顺序访问
- 优点: 增删效率后，$O(1)$的时间复杂度
- 缺点: 查改效率低，只能通过遍历节点依次查询，$O(N)$的时间复杂度
栈
栈本身是一个线性表，但在这个表中只有一个口子允许数据的进出，其特点在于栈中元素的先进后出(FILO)，常用的操作有push()、pop()、top()
单调栈
单调栈是一种特殊的栈，栈中的元素是单调递增/递减:
- 单调递增栈: 可以找到元素向左遍历第一个比它小的元素
- 单调递减栈: 可以找到元素向左遍历第一个比它大的元素
借助单调栈可以在线性时间内完成左侧第一个小于/大于元素的搜索，下面介绍几个典型题目
- 接雨水
题目描述: 给定一个列表表示高度图，计算下雨后能接多少雨水
解题思路: 维护一个单调递减栈，一旦发现当前元素大于栈顶元素，当前元素便是右边界，栈顶元素出栈，此时单调栈的栈顶元素便成为了左侧边界，取两者最小值作为高度，乘以左右距离便得到了装水量。
- 求直方图中最大矩阵面积
题目描述: 给定一个列表表示直方图，求该直方图中最大矩阵面积
解题思路: 维护一个单调递增栈，当遇到大的元素时直接进栈，一旦发现当前元素小于栈顶元素，则当前元素便是栈顶元素的右边界，而栈顶元素出栈后，下一个栈顶元素便是左边界，由此便可计算矩阵面积，遍历一次找到最大的矩阵面积即可。
- 最大矩形
题目描述: 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
解题思路: 按行遍历，然后每次都堆叠列得到一个柱状图，然后通过单调栈算法，求最大矩形面积
单调栈算法总结:
单调栈是一个原理简单，但不太好想到的一种思路，在leetcode往往是以hard题目形式出现，线性时间复杂度是该数据结构最大的优势，对于此类题目往往会先考虑暴力解法，如果需要寻找各个元素的左边界/右边界，则考虑能否应用单调栈降低时间复杂度。
队列
队列是一种线性数据结构，与栈的后进先出相对应，队列是先进先出(FIFO)
import queue
q = queue.Queue()
q.put(1) #向队列中加入元素
q.get() #取出队列中最先进入的元素
q.empty() #判断队列是否为空
q.qsize() #获取队列长度
树
树作为一种树状的数据机构，其将有限个节点根据不同的层次关系进行排列，从而形成数据之间的父子关系，从某种角度来说，可以将树看作链表的高配版，对普通链表的指针域进行了扩展。
下面介绍一些常见的树的类型:
- 完全二叉树: 除了最后一层节点，其他层的节点数都达到了最大值，同时最后一层的节点都是按照从左到右依次排布
- 满二叉树: 除了最后一层，其他层的节点都有两个子节点
- 二叉排序树((二叉搜索树): 左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根结点，左右子树也分别时二叉排序树
- 平衡二叉树: 平衡二叉树又被称为AVL树，它是一个二叉排序树，且左右子树的高度差距不超过1，左右子树也都是二叉平衡树
- 优点: 平衡二叉树为了追求高度平衡，需要通过平衡处理使得左右子树的高度差必须小于等于1，高度平衡带来了更高的搜索效
- 缺点： 缺点则是对树中结点进行插入删除时需要经过多次旋转实现复衡，这导致AVL的插入和删除效率并不高。
- 红黑树:
- 每个结点要么是红的，要么是黑的
- 根结点是黑的
- 每个叶结点(None)都是黑的
- 如果一个结点是红的，那么它的两个儿子都是黑的
- 对于任意结点而言，其到叶结点树尾端None指针的每条路径都包含相同数目的黑结点
- 红黑树与平衡二叉树对比
树的遍历方式有四种:
- 前序遍历: 按照 根结点->左子结点->右子结点的顺序进行遍历
- 中序遍历: 按照 左子结点->根结点->右子结点的顺序进行遍历
- 后序遍历: 按照 左子结点->右子结点->根结点的顺序进行遍历
- 层次遍历: 从根结点开始，按结点所处层级进行遍历
堆
堆通常可以看做一棵树的数组对象，堆的实现一般不通过指针域，而是通过构建一个一维数组与二叉树的父子结点进行对应，因此堆总是一棵完全二叉树。 - 对于任意一个父结点的序号$n$来说，它的子结点的序号一定是$2n+1, 2n+2$，因此可以直接用一个数组表示一个堆
- 堆中某个结点的值总是不大于或者不小于其父节点的值: 根结点最大的堆称为最大堆;根结点最小的堆称为最小堆
- 堆常用来实现优先队列，比如堆排序、top$K$问题等
import heapq
pq = []
value = 1
heapq.heappush(pq, value) #向小根堆中加入元素
heapq.heapreplace(pq, value) #替换堆顶元素
heapq.pop(pq) #弹出堆顶元素
哈希表
哈希表也叫散列表，是一种通过键值堆直接访问数据的结构，借助于哈希表可以实现$O(1)$的数据访问效率。
哈希表实现的最关键就是哈希函数的定义和选择，一般常用的有以下几种：
- 直接寻址法: 取关键字或者关键字的某个线性函数作为哈希地址
- 数字分析法: 通过数据的特点，发现数据中冲突较少的部分，构造哈希地址。
- 平方取中法:
- 取随机数法: 通常适用于关键字长度不同的场合
- 除留取余法: 取关键字被某个不大于散列表的表长$n$的数$m$除后所得的余数$p$作为散列地址，一般取素数或者直接用$n$。
哈希冲突: 当不同的key值访问到同一个地址时，就发生了哈希冲突。
哈希冲突主要有以下解决方案：
- 链地址法: 在冲突的地方再做一个链表
- 开放寻址法: 探测后续未被占用的地址
- 再哈希: 使用关键字的其他部分继续计算地址，更换哈希函数
图
图一般包含顶点和边，可粗略分为有向图和无向图。
- 图的存储一般通过邻接矩阵实现
- 邻接矩阵往往是稀疏的，存储大量的0导致浪费了大量的空间，，一种只存储相连顶点关系的邻接表应运而生。
- 在邻接表中，图的每一个顶点都是一个链表的头结点，其后连接着该节点能够到达的相邻节点。
- 邻接表只包含个个结点的出度信息
- 逆邻接表: 包含结点的入度信息
- 十字链表
常见算法
动态规划
动态规划是算法与数据结构的重难点，其中包含了「分治思想」、「空间换时间」、「最优解」等多种算法思想，这部分将从以下三个方面对动态规划算法进行介绍:
- 动态规划问题特点，动态规划和分治算法的联系与区别
- 介绍重叠子问题与最优子结构分别是什么，以及动态规划是如何解决的
- 动态规划的解题框架总结
动态规划与分治
- 分治算法: 「分治」是算法中的一种基本思想，通过将原问题分解为子问题，不断递归地将子问题分解为更小的子问题，并通过组合子问题的解来得到原问题的解， e.g. 归并排序
- 动态规划: 与「分治」的相同点在于「动态规划」也是通过组合子问题的解来得到原问题的解，不同的是，能用「动态规划」解决的问题具有「重叠子问题」和「最优子结构」两大特性。
动态规划问题特性
- 重叠子问题: 动态规划的子问题是有重叠的，即各个子问题中包含重复的更小子问题，若使用暴力法穷举，求解这些相同子问题会产生大量重复计算，效率低下。
# 求第 n 个斐波那契数 def fibonacci(n): if n == 0: return 0 # 若求 f(0) 则直接返回 0 a, b = 0, 1 # 初始化 f(0), f(1) for i in range(2, n + 1): # 状态转移求取 f(2), f(3), ..., f(n) a, b = b, a + b return b # 返回 f(n) - 最优子结构: 如果一个问题的最优解可以由其子问题的最优解组合而成，并且这些子问题可以独立求解，那么称此问题具有最优子结构。
# 输入蛋糕价格列表 price_list ，求重量为 n 蛋糕的最高售价 def max_cake_price(n, price_list): if n <= 1: return price_list[n] # 蛋糕重量 <= 1 时直接返回 dp = [0] * (n + 1) # 初始化 dp 列表 for j in range(1, n + 1): # 按顺序计算 f(1), f(2), ..., f(n) for i in range(j): # 从 j 种组合种选择最高售价的组合作为 f(j) dp[j] = max(dp[j], dp[i] + price_list[j - i]) return dp[n]
动态规划解题框架
首先分析问题是否具有「重叠子问题」与「最优子结构」两个特性，若有则可以考虑用动态规划按照以下步骤进行求解:
- 状态定义: 构建问题最优解模型，包括问题问题最优解的定义、有哪些计算解的自变量
- 初始状态: 确定基础子问题的解，原问题和子问题的解都是以基础子问题的解为起始点，在迭代计算中得到
- 转移方程: 确定原问题与子问题之间的关系，以及使用何种选择规则从子问题最优解中组合出原问题的最优解
- 返回值: 确定应返回的问题的解是什么，即动态规划在何处停止迭代
示例: 斐波那契数列
- 状态定义: 一维$dp$列表，设第$i$个斐波那契数为$dp[i]$
- 初始状态: 已知第$0,1$个斐波那契数为$dp[0] = 0, dp[1] = 1$
- 转移方程: 后一个数字等于前两个数字之和
- 返回值: 第$n$个斐波那契数$dp[n]$
排序算法
概述
排序算法用作实现列表的排序，列表元素可以是整数，也可以是浮点数、字符串等其他数据类型，生活中有许多需要用到排序算法的场景:
- 数字排序: 对于一个数组，我们希望将所有数字从小到大/从大到小排序
- 字符串排序: 对于一个字符串列表，我们希望将所有单词按照字符先后排序
- 自定义排序: 对于任意一个已定义比较规则的集合，我们希望将其按规则排序
常见排序算法
常见排序算法包括「冒泡排序」、「插入排序」、「选择排序」、「快速排序」、「归并排序」、「堆排序」、「基数排序」、「桶排序」。如下图所示，为各排序算法的核心特性与时空复杂度总结
如下图所示，为在 「随机乱序」、「接近有序」、「完全倒序」、「少数独特」四类输入数据下，各常见排序算法的排序过程。
排序算法主要可根据稳定性、就地性、自适应性分类，理想的排序算法具有以下特征:
- 稳定性: 相等元素的相对位置不变化
- 就地性: 不使用额外的辅助空间
- 自适应性: 时间复杂度受元素分布影响
按照稳定性来分类:
- 稳定排序: 冒泡排序、插入排序、归并排序、基数排序、桶排序
- 非稳定排序: 选择排序、快速排序、堆排序
按照就地性进行分类:
- 原地排序: 不使用额外辅助数组，例如: 冒泡排序、插入排序、选择排序、快速排序、堆排序
- 非原地排序: 使用额外辅助数组，例如: 基数排序、桶排序等
时空复杂度
常见排序算法时空复杂度见下图
- 普通「冒泡排序」的最佳时间复杂度为$O(N^2)$，通过增加标志位实现提前返回 ，可以将最佳时间复杂度降低至$O(N)$
- 在输入列表完全倒序下，普通「快速排序」的空间复杂度劣化至$O(N)$通过代码优化 Tail Call Optimization 保持算法递归较短子数组，可以将最差递归深度降低至 $\log N$
- 普通「快速排序」总以最左或最右元素为基准数，因此在输入列表有序或倒序下，时间复杂度劣化至$O(N^2)$; 通过随机选择基准数, 可极大减少此类最差情况发生, 尽可能地保持$O(NlogN)$的时间复杂度。
- 若输入列表是数组，则归并排序的空间复杂度为$O(N)$; 而若排序链表, 则「归并排序」不需要借助额外辅助空间，空间复杂度可以降低至$O(1)$
快速排序
快速排序分为两步:
- 哨兵划分: 以数组某个元素为基准数，将所有小于基准数的元素移至其左边，大于基准数的元素移动至其右边
- 递归: 对左子数组和右子数组分别执行哨兵划分，直至子数组长度为1终止递归
def quick_sort(nums, l, r):
# 子数组长度为 1 时终止递归
if l >= r: return
# 哨兵划分操作
i = partition(nums, l, r)
# 递归左（右）子数组执行哨兵划分
quick_sort(nums, l, i - 1)
quick_sort(nums, i + 1, r)
def partition(nums, l, r):
# 以 nums[l] 作为基准数
i, j = l, r
while i < j:
while i < j and nums[j] >= nums[l]: j -= 1
while i < j and nums[i] <= nums[l]: i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[l], nums[i] = nums[i], nums[l]
return i
# 调用
nums = [3, 4, 1, 5, 2]
quick_sort(nums, 0, len(nums) - 1)
归并排序
归并排序体现了分治的算法思想，具体为:
- 分: 不断将数组从中点位置划分开，将原数组的排序问题转化为子数组的排序问题
- 治: 划分到子数组长度为1时，开始向上合并，不断将左右两个较短排序数组合并为一个较长排序数组，直至合并至原数组完成排序
代码实现
def merge_sort(nums, l, r):
# 终止条件
if l >= r: return
# 递归划分数组
m = (l + r) // 2
merge_sort(nums, l, m)
merge_sort(nums, m + 1, r)
# 合并子数组
tmp = nums[l:r + 1] # 暂存需合并区间元素
i, j = 0, m - l + 1 # 两指针分别指向左/右子数组的首个元素
for k in range(l, r + 1): # 遍历合并左/右子数组
if i == m - l + 1:
nums[k] = tmp[j]
j += 1
elif j == r - l + 1 or tmp[i] <= tmp[j]:
nums[k] = tmp[i]
i += 1
else:
nums[k] = tmp[j]
j += 1
# 调用
nums = [3, 4, 1, 5, 2, 1]
merge_sort(0, len(nums) - 1)
搜索与回溯算法
概述
- 搜索是计算机解题中的常用算法，其本质是通过某种规则实现对解空间的遍历
- 回溯搜索算法中的一种控制策略，它的基本思想是: 为了求得问题的解，先选择某一种可能的情况向前探索，在探索过程中，一旦发现上一步选择是错的，就退回一步重新选择，继续向前探索，直至得到解或者证明无解。
这类算法大致可以分为两类:
- 暴力搜索(无信息搜索算法): 广度优先搜索(BFS)、广度优先搜索(DFS)
- 启发式搜索(有信息搜索算法): 贪心搜索、A*搜索
广度优先搜索算法
BFS，类似地毯式搜索，以距离为层数逐层搜索，直到找到答案或者确认无解
广度优先搜索一般通过队列实现:
- 起始结点入队列
- 遍历与启示结点有连通的结点，入队列
- 起始结点出队列
- 重复以上步骤，直至找到目标点或者队列为空(无解)
深度优先搜索算法
深度优先搜索(DFS)会从第一个指定的顶点开始遍历图，沿着这条路径直到最后一个顶点被访问了，再原路折回(回溯)探索下一条路径。
深度优先搜索一般是通过递归回溯实现
贪心搜索
当边上有权值时，BFS便不适用了，此时需要加入松弛变量来表示结点与顶点之间的距离，这就是dijkstra算法，对于无权图/树，dijkstra算法就退化成了BFS
动态规划是贪心的泛化，贪心是动态规划的特例(贪婪解也恰好是Bellman最优时)
A*搜索
做到题目了再来补
位运算
概念
程序中的所有数在计算机内存中都是以二进制的形式存储的，位运算就是直接对整数在内存中的二进制位进行运算，常见的运算操作符有:
- 与(&)
- 或(|)
- 异或(^)
- 取反(~)
- 左移(<<)
- 右移(>>)
与运算
两位同时为1，结果为1，否则为0
与运算的特殊用途:
- 清零: 任何数字与0相与都是0
- 取指定位: 与一个特定位为1，其他位为0的数字进行与运算即可取原数字中该特定位
或运算
二进制对应位两两进行或运算(有1则1，无1则0)
或运算的特殊用途:
- 用来将数字的某些位置1
异或运算
二进制对应位两两进行异或运算(相同为1，不同为0)
异或运算的特殊用途:
- 将低位1置0(n&(n-1)将低位1置0)
- 使某些特定的位翻转(与指定位为1的数字进行异或运算)
- 判断两个值是否相等(相等则异或值为0)
- 实现两个值的交换(a = a^b, b = b^a, a = a^b)
按位取反
二进制的0变成1，1变成0
移位运算符
- 左移运算符$<<$: 左移后右侧补0
- 右移运算符$>>$: 右移后左边补原左位值
说明:
- 左移一位相当于整个数乘以二
- 右移一位相当于整数除以二
位运算小技巧
- 判断奇偶数
```python
if(n & 1 == 1){
// n 是个奇数。
}
- 交换两个数
```python
a=a^b; #a=a^b
b=a^b; #b=(a^b)^b=a^0=a
a=a^b; #a=(a^b)^(a^b^b)=0^b=0
经典问题
- 不用加减乘除做加法
- 二进制中1的个数
- 只出现一次的数字
….未完待续，后序刷题碰到未掌握的知识点后回来补充
