type
status
date
slug
summary
tags
category
icon
password
1、排序
常见排序算法
排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
直接选择排序 | O(n²) | O(n²) | O(n) | O(1) | 不稳定 |
直接插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
快速排序 | O(nlogn) | O(n²) | O(nlogn) | O(nlogn) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
希尔排序 | O(nlogn) | O(ns) | O(n) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
基数排序 | O(N*M) | O(N*M) | O(N*M) | O(M) | 稳定 |
1、核心思想记忆法
- 三种基本排序算法：冒泡排序、直接选择排序、直接插入排序，都是把数组分成未排序和已排序两部分，每次只需要把未排序数组的某一个元素放在正确的位置。按照升序排序：
- 冒泡排序：左边是未排序数组，右边是已排序数组，每次只关注未排序数组的最后一个位置的正确元素。未排序数组左右比较和交换位置，最后“冒出”最大的元素挪到未排序数组的最后一个位置，该位置就作为已排序数组的第一个位置。
- 直接选择排序：左边是已排序数组，右边是未排序数组，每次只关注未排序数组的第一个位置的正确元素。从未排序数组中“选择”出最小的元素放在未排序数组的第一个位置，该位置就作为已排序数组的最后一个位置。
- 直接插入排序：左边是已排序数组，右边是未排序数组，每次只关注把未排序数组的第一个元素放在已排序数组的正确位置。把未排序数组的第一个位置的元素依次和已排序数组的元素做比较和交换位置，最后把未排序数组的第一个位置的元素放在已排序数组的正确位置。
- 交换排序：基本思想是两两比较待排序元素，如果发现两个元素的次序相反时即进行交换，直到所有元素都没有反序时为止。
- 冒泡排序。在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。
- 快速排序。快速排序是对冒泡排序的改进方法。在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，速度较快。
- 选择排序：基本思想是每次从待排序数组中选出最小的元素，把它放到已排序数组的末尾。
- 直接选择排序。在直接选择排序中，每次都要经过 i - 1 次比较（i 是未排序数组的长度）才能找出最小的元素。
- 堆排序。堆排序是对直接选择排序的改进方法。堆排序借助最大堆，可以把 n 个元素的堆可以看成一棵高为[lgn]的完全二叉树，这样只需要进行 lgn 次比较即可找出最小的元素。
- 插入排序：基本思想是每次从待排序的数组取出一个元素插入到已排序数组中的正确位置。
- 直接插入排序：在直接插入排序中，最坏的情况是数组完全逆序，这种情况下的时间复杂度为O(N^2)。
- 希尔排序。希尔排序是对直接插入排序的改进方法。即将数组先分组，然后对各组进行排序，即预排序；当进行多次预排序以后数组近似有序，再进行直接插入排序。这样分组的目的是：当数组完全逆序或近似这种情况时，希尔排序会将大的数据近况向后面移动，小的数据会尽快向前面移动，其实也就是解决了直接插入排序的最坏情况。
- 合并排序：归并排序，采用分而治之思想的典型算法。
2、时间复杂度记忆
- 冒泡、选择、插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）
- 快速、归并、希尔、堆排序基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）
3、稳定性记忆：快希选堆是不稳定，其他四个是稳定的。
4、其他：
- 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。
- 归并排序可以通过手摇算法将空间复杂度降到O(1)，但是时间复杂度会提高。
- 基数排序时间复杂度为O(N*M)，其中N为数据个数，M为数据位数。
- 计数和基数排序日常考察比较少，简单了解即可。
算法思想
冒泡排序
基本思想是：通过相邻两个元素之间的比较和交换，使较大的元素逐渐从前面移向后面（升序），就像水底下的气泡一样逐渐向上冒泡，所以被称为“冒泡”排序。
直接选择排序
基本思想是：通过length-1 趟元素之间的比较，从length-i+1个元素中选出最小的元素，并和第i个元素交换位置。
直接插入排序
基本思想是：每次从无序序列中取出第一个元素插入到已经排好序的有序序列中，从而得到一个新的，数量加1的有序序列。
快速排序
冒泡排序的改进，在一个无序的序列中选取一个任意的基准元素pivot（通常为数组的第一个元素），利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素
- 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边。通常办法是在数组的头部和尾部分别设置一个哨兵，同时向对方走去。
- 尾部的哨兵如发现有比基准数小的数，停下。
- 头部的哨兵如发现有比基准数大的数，停下。
- 交换两个数。再重新走重复前面的交换过程。
- 直到两个哨兵相遇，交换基准数和尾哨兵（此时首尾哨兵相遇，两个哨兵位置相同）。
- 对于基准数左、右两边的数组，递归重复以上两个过程，直到每个子集只有一个元素，即为全部有序。
堆排序
堆排序(Heap Sort) 利用堆（一般为大根堆）进行排序的方法。它的基本思想是：将待排序的元素构造成一个大根堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将它与数组的末尾元素进行交换，此时末尾元素就是最大值），然后将剩余的length-1 个元素重新构造成一个大根堆，这样就会得到length个元素中的次大值。如此反复执行，便能得到一个有序的序列。
堆是具有下列性质的完全二叉树。假如某个节点索引为 i，满足条件：
- 父节点索引：
(i-1)/2
- 左节点索引：
2i+1
- 右节点索引：
2i+2
堆结构可以分为大顶堆和小顶堆，一般升序采用大顶堆，降序采用小顶堆。
- 大根堆：每个节点的值都大于或等于其左右孩子节点的值，满足
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
- 小根堆：每个节点的值都小于或等于其左右孩子节点的值，满足
arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的过程（以大顶堆为例）：
- 构建大顶堆。首先把待排序的记录序列对应成一棵完全二叉树，并把它转换成一个初始大顶堆。这时，堆顶的根节点具有最大值。
- 调整堆，从最后一个非叶子结点开始，从左至右，从下至上进行调整，保证满足堆序性质，即任意父节点大于其子节点。调整完毕后将堆顶元素与数组末尾元素进行交换，此时数组最后一个元素就是最大值。此时这个元素相当于处于有序队列中，其他的 n - 1 个元素处于为无序队列中。
- 将剩下的 n - 1 个元素重复第 1 和 2 步， 结束后堆顶的根节点是所有元素的第二大值，将堆顶节点和数组的倒数第二位置的节点进行交换。
- 重复以上步骤，最后得到一个有序队列。
希尔排序
插入算法的改进，基本思想是将数组先分组，然后对各组进行排序，即预排序；当进行多次预排序以后数组近似有序，再进行直接插入排序。
这样分组的目的是：当数组完全逆序或近似这种情况时，希尔排序会将大的数据近况向后面移动，小的数据会尽快向前面移动，其实也就是解决了直接插入排序的最坏情况。可能当数据比较少的时候，希尔排序的优势并不明显。但当数据量大的时候，并且这些数据完全逆序或近似逆序时（也就是插入排序最坏的情况），希尔排序就会优于插入排序，因为它的几趟预排序就使这些数据接近有序了。
希尔算法的过程：
- 对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；
- 对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。
- 减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，即所有记录放在同一组中进行直接插入排序为止，整个数列就是有序的。
归并排序
基本思想：假设初始序列有 n 个元素，则可以看成是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到 n/2 个长度为 2 或 1 的有序子序列；再两两归并，如此重复，直至得到一个长度为 n 的有序序列为止。
2、数组
数组结构
不管某种数据结构有多么复杂，最底层只有两种数据结构：数组或者链表。
- 数组是一块物理连续的内存空间，随机访问速度快，但是插入和删除元素速度很慢。
- 链表由多个非连续内存空间的节点组成，每个节点保存指向下一个节点内存地址的指针。链表的随机访问速度慢，但是插入和删除元素速度较快。
解题技巧
- 二分法：如果给定的数组是有序的，且要求时间复杂度是O(logn)，就是首先考虑二分法。
- 双指针法：普通双指针或者快慢指针，在一个for循环下完成两个for循环的工作，将枚举的时间复杂度从O(N^2)减低到O(N)。
- 滑动窗口：所谓的滑动窗口就是可以在一个序列上进行滑动的窗口。窗口大小可以根据问题类型设置固定长度或者可变长度，关键在于什么条件下移动窗口的起始位置，以及何时动态的扩展窗口。使用滑动窗口，我们可以减低算法是时间复杂度。
- 哈希表法：需要在数组中查找某个元素是否存在时，可以使用哈希表法将查找元素的时间复杂度从O(n)减低到O(1)。
- 摩尔投票： 投票法的核心思想是正负抵消。遇到相同的则票数 + 1，遇到不同的则票数 - 1。 且“多数元素”的个数> ⌊ n/2 ⌋，其余元素的个数总和<= ⌊ n/2 ⌋。 因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。 这就相当于每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。
常见问题 | 问题描述 | 解题思路 | 题目 |
操作数组 | 合并，旋转，翻转数组等 | 涉及到数组操作，排序 + 双指针是最常用的方法，可以解决大部分的数组问题。 | |
查找重复元素 | 查找两个数组的交集或者某个数组的重复元素 | 一般情况下用哈希表即可解决，如果明确指出某个重复元素的个数大于 n/2，这种情况下可以考虑摩尔投票法 | |
矩阵 | 给定一个矩阵，进行高效搜索、螺旋遍历、旋转等操作 | 矩阵相当于有序的二维数组，满足左边元素 < 右边元素，上边元素 < 下边元素的特点，所以我们在遍历的时候要利用这个有序的特点，从右上角或者左下角开始进行Z字型遍历，每次排除一行或者一列元素，减少遍历的时间。如果是旋转的题目，如果直接交换，需要同时找到上下左右四个点的坐标交换关系，这样会比较麻烦，需要数学公式推导。我们可以使用翻转代替旋转，通过左右翻转和上下翻转一定次数，这样每次只需要交换两个对称的元素。 |
3、链表
链表分类
- 单链表：单链表中每一个节点是由两部分组成，一个是数据域、一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域为空。
- 双链表：双向链表中的每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双向链表既可以向前查询也可以向后查询。
指针赋值
链表问题最难理解的是指针的赋值问题。等式分成两部分：
- 等号左边：被赋值的变量，如果是指针变量就相当于指针的移动，如果是指针变量.next就相当于画箭头。
- 等号右边：要赋的值，不管是指针变量还是指针变量.next，都统一找数据块的位置。
我们重点关注等号前面部分的变量，这个变量才是我们要操作的变量，指针是可以移动的，数据块是不会移动的。例如链表问题一定要手动画图，手动画清晰了，再写代码。例如
- 指针变量，可以理解为指针在数据块移动，画图的时候等于指针变量出现的数据块上的哪个位置。
- 指针变量.next，可以理解为数据块指向的哪一个数据块，画图的时候等于当前数据块的指向箭头怎么画。
- 指针变量.next.next，可以理解为数据块指向的下一个数据块指向哪一个数据块，画图的时候先找到当前数据块的下一个数据块，再确定该数据块的箭头怎么画，本质还是画箭头。
链表的操作
- 增加节点
- 删除节点
- 前后节点反转
解题技巧
- 虚拟头节点：涉及到链表反转、链表元素删除、链表合并，建议使用虚拟头节点，简化边界条件。
- 快慢指针：涉及到是否有环，使用快慢指针法。
容易出问题的地方：链表最容易出错的地方就是我们应该注意的地方。链表最容易出的错 90 % 集中在以下三种情况：
- 出现了环，造成死循环。
- 分不清边界，导致边界条件出错。
- 搞不懂递归怎么做
常见问题 | 问题描述 | 解题思路 | 题目 |
链表反转 | 给定单链表的头节点 head ，完全或者部分反转链表，并返回反转后的链表的头节点。 | 1. 虚拟头节点，把头节点进行统一处理
2. 画图，弄清楚指针的移动和指针.next的指向问题 | |
合并有序链表 | 将两个升序链表合并为一个新的 升序 链表并返回。 | 1. 虚拟头节点，把头节点进行统一处理
2. 双指针法，画图，弄清楚指针的指向问题
3. 迭代和递归注意终止条件 | |
链表删除元素 | 删除指定位置或者重复的元素 | 1. 虚拟头节点，把头节点进行统一处理
2. 指定位置使用双指针法
3. 重复元素，因为链表本身已经是有序，所以简单一次遍历即可删除。重点注意指针和指针.next的赋值问题 | |
判断链表是否有环 | 给链表的头节点 head ，判断链表中是否有环。 | 1. 虚拟头节点，把头节点进行统一处理
2. 快慢指针法，指针相遇表示有环 |
4、树
树的类型
树类型 | 结构 | 特点 |
二叉树 | 二叉树是每个结点最多有两个子树的树结构。特殊情况有会变成完全二叉树和满二叉树。
• 完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
• 满二叉树：：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。 | 二叉树：
• 每个结点最多有两颗子树，所以二叉树中不存在度(结点拥有的子树数目称为结点的度)大于2的结点
• 左子树和右子树是有顺序的，次序不能任意颠倒
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树
完全二叉树：
• 叶子结点只能出现在最下层和次下层。
• 最下层的叶子结点集中在树的左部。
• 倒数第二层若存在叶子结点，一定在左部连续位置。
• 如果结点度为1，则该结点只有左孩子，即没有右子树。
• 同样结点数目的二叉树，完全二叉树深度最小。
满二叉树：
• 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
• 非叶子结点的度(结点拥有的子树数目称为结点的度)一定是2 |
二叉查找树（BST） | 又称作二叉排序树、二叉搜索树，在二叉树的基础上，限制根节点大于左节点，小于右节点。
二叉查找树可以任意地构造，如果向一方倾斜的二叉树是不平衡的，查询效率就低了，在极端情况下，二叉查找树变成了一个链表。 | 二叉查找树：
• 若它的左子树不空，则左子树上的所有结点的值均小于根节点的值
• 若它的右子树不空，则右子树上的所有结点的值均大于根节点的值。
• 左右子树也分别为二叉排序树。 |
平衡二叉树 | 在二叉查找树的基础上，限制左右两边结点层级相差不大于1。具体实现有AVL、红黑树、Treap等。
• AVL：最先提出的平衡二叉树，严格要求平衡的二叉树。
• 红黑树：红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低， 其平均统计性能要强于 AVL。
平衡二叉树相比二叉查找树：
• 避免了二叉查找树在极端情况下变成线性查找的问题，查找效率更稳定，总体的查找速度也更快。 | 红黑树：
• 每个节点或者是黑色，或者是红色
• 根节点是黑色
• 每个叶结点是黑色
• 如果一个节点是红色的，则它的子节点必须是黑色的，红色节点的孩子和父亲都不能是红色。从每个叶子到根的所有路径上不能有两个连续的红色节点，任意一结点到每个叶子结点的路径都包含数量相同的黑结点。确保没有一条路径会比其他路径长出俩倍。
红黑树对比AVL：
红黑树不追求完全平衡，即不像AVL那样要求节点的 高度差的绝对值 <= 1，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。总结就是：
• AVL更平衡，结构上更加直观，时间效能针对读取而言更高；维护稍慢，空间开销较大。
• 红黑树，读取略逊于AVL，维护强于AVL，空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。
实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择红黑树 |
b树 | 又称平衡多路查找树，在平衡二叉树的基础上，每个根节点可以包含2个以上的子节点。
b树相比平衡二叉树：
• 每个节点存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子节点，树的高度也会很低，B树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。 | b树：
• 根结点至少有两个子女
• 每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
• 除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
• 所有的叶子结点都位于同一层。 |
b+树 | 在b树的基础上，数据只存在叶子节点上，非叶子结点只存索引，且所有叶子节点从小到大进行排序。
b+树相比b树：
• B+树所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同查询速度更稳定。
• B+树所有的叶子节点数据构成了一个有序链表，具有天然排序的功能
• 因为数据都在叶子节点上，遍历和范围查找更加方便。 | B+树：
• 有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
• 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有的非叶子结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。所以.不可能在非叶子结点命中。
• 通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。 |
树的遍历
树问题的核心就是树的遍历。树的遍历有两种方式：
- 深度优先遍历（DFS）：采用纵向遍历的方式，在数据结构上采用栈结构。DFS在遍历顺序上分为前序遍历、中序遍历和后序遍历。在写法上有两种：
- 调用系统栈，也就是递归；
- 使用自己实现的栈，也就是迭代。
- 广度优先遍历（BFS）采用横向搜索的方式，在数据结构上采用队列结构。在遍历顺序上分为带层的和不带层的。
解题技巧
- DFS：对于树的题目，我们基本上都可以使用 DFS 来解决，甚至我们可以基于 DFS 来做层次遍历，而且由于 DFS 可以基于递归去做，因此算法会更简洁。 建议在对性能有很高要求的场合使用迭代，否则尽量使用递归。不仅写起来简单快速，还不容易出错。
- BFS：BFS 比较适合找最短距离/路径和某一个距离的目标，直接使用上面两个模板。这两个模板可以解决所有的树的 BFS 问题。如果我需要求的是最短距离/路径，我是不关心我走到第几步的，这个时候可是用不标记层的目标。而如果我需要求距离某个节点距离等于 k 的所有节点，这个时候第几步这个信息就值得被记录了。
常见问题 | 问题描述 | 解题思路 | 题目 |
二叉树的遍历 | DFS：树的前序、中序、后序遍历BFS：层序遍历 | 每种遍历都有递归和迭代两种写法， DFS优先使用递归写法，在追求性能的情况下才使用迭代写法；BFS优先使用迭代写法，代码更简洁 | |
二叉树的各种操作 | 例如反转、平衡、对称二叉树等 | 实际上就是考核BFS和DFS，只要会这两种遍历方式，都可以解决 | |
岛屿问题 | 计算岛屿数量、面积、周长等 | 岛屿问题实际上是树问题的变种，树只需要遍历左右两个节点，而岛屿属于矩阵，需要遍历左右上下四个节点。 |
5、二分查找
二分查找基础
二分查找是对半查找的算法，涉及到的列表、数组是有序排列的，时间复杂度为 O(log n)，有递归和迭代两种写法。
二分查找一般由三个主要部分组成：
- 预处理 —— 如果集合未排序，则进行排序。
- 二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
- 后处理 —— 在剩余空间中确定可行的候选者。
二分查找模板，常用的查找属性：
- 初始条件：left = 0, right = length-1
- 终止：left > right
- 向左查找：right = mid-1
- 向右查找：left = mid+1
二分查找模板：
解题技巧
看到符合这些特征的题目，大概率可以用二分法
- 数组是有序的，包括整体有序或者局部有序
- 时间复杂度要求O(logn)，要么二分法，要么分治（递归）。
解题难点：
- 边界问题，例如中间节点放到左边区间处理，还是右边区间处理，还是直接跳过，这个要根据实际题目做应对
- 二分终止条件：例如到底是 left < right，还是 left <= right。
常见问题 | 问题描述 | 解题思路 | 题目 |
二分查找 | 给定一个有序数组，查找指定元素、重复元素、指定位置等 | 考核最基础的二分查找写法，尽量用迭代，思路更清晰，递归了解即可 | |
旋转数组 | 本来是有序数组，在某个位置上做前后旋转，形成局部有序的新数组，查找指定元素等 | 将数组一分为二，其中一定有一个是有序的，另一个可能是无序的。此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个一定无序。就这样循环。 |
6、字符串
解题技巧
经典解法：
- 双指针
- 栈
- reverse
- 回溯
- KMP算法
字符串要记住常用的api：
操作对象 | api |
字符串 String str | 字符串长度 str.length() 字符位置 str.charAt() |
字符串数组 String[] strs | 数组长度 strs.length |
字符串拼接 StringBuilder sb | 添加元素 sb.append() 取特定位置的元素 sb.charAt()计算长度 sb.length()翻转 sb.reverse()序列化输出 sb.roString() |
字符 char ch | 判断是否数字和字母 Character.isLetterOrDigit(ch) 转成小写字母和数字 Character.toLowerCase(ch) 把字符转成数字 ch - ‘0' |
常见问题 | 问题描述 | 解题思路 | 题目 |
字符串模拟数学运算 | 给定两个字符串，不能使用内置的数学库，执行数学运算，例如加减乘除等 | 一般就是把现实生活中的竖式运算的过程写出来，注意要使用一个add变量保存进位 | |
回文字符串 | 回文字符串是正着读和反着读都一样的字符串，判断某个字符串是否回文串和分割回文串 | 一般涉及到回，简单一点的问题双指针就可以解决，复杂的问题需要使用回溯。 | |
字符串操作 | 字符串匹配，反转、拆分等 | 涉及到字符串操作的，首先要熟悉字符串常用的api，然后要考虑算法，字符串匹配常用的要么回溯，要么KMP算法 |
7、哈希表
解题技巧
- Set：如果不需要保存val，可以使用简单的Set类型
- HashMap：如果需要保存val，就使用经典HashMap类型
- LinkedHashMap：如果需要保存val，而且需要元素按照一定的顺序排序，需要用到LinkedHashMap类型，例如LRU算法这种。
常见问题 | 问题描述 | 解题思路 | 题目 |
多数之和 | 最经典的题目，给定一个整数数组 nums 和一个整数目标值 target，求nums数组中两数或者更多数之和等于 target 的元素组合 | 两数之和经典解法是利用一个哈希表存储 num[i] 元素，然后去哈希表判断 target - num[i] 元素是否存在。三数之和也可以使用哈希表，先两遍循环使用哈希表存储a+b的结果，最后一次循环查找target - (a + b)，但需要去重的话这种解法会超时，最好是使用排序+ 双指针。 | |
找出连续、重复元素 | 给定一个数组，找出连续的元素序列或者重复的元素 | 先使用哈希表存储元素去到去重和O(1)查找的作用，然后遍历数组元素和哈希表进行对比，就可以找到重复的元素 | |
高效数据结构设计 | 设计一种高效的数据结构，支持O(1)查找的复杂度，也支持排序 | 一般看到O(1)查找的复杂度就需要考虑哈希表，经典解法是哈希表+双链表，即支持快速查找也支持排序。java的LinkedHashMap就是这样的数据结构 |
8、栈与队列
栈与队列基础
Deque接口提供的用于实现双端队列的方法：
- addFirst() - 在双端队列的开头添加指定的元素。如果双端队列已满，则引发异常。
- addLast() - 在双端队列的末尾添加指定的元素。如果双端队列已满，则引发异常。
- offerFirst() - 在双端队列的开头添加指定的元素。如果双端队列已满，则返回false。
- offerLast() - 在双端队列的末尾添加指定的元素。如果双端队列已满，则返回false。
- getFirst() - 返回双端队列的第一个元素。如果双端队列为空，则引发异常。
- getLast() - 返回双端队列的最后一个元素。如果双端队列为空，则引发异常。
- peekFirst() - 返回双端队列的第一个元素。如果双端队列为空，则返回null。
- peekLast() - 返回双端队列的最后一个元素。如果双端队列为空，则返回null。
- removeFirst() - 返回并删除双端队列的第一个元素。如果双端队列为空，则引发异常。
- removeLast() - 返回并删除双端队列的最后一个元素。如果双端队列为空，则引发异常。
- pollFirst() - 返回并删除双端队列的第一个元素。如果双端队列为空，则返回null。
- pollLast() - 返回并删除双端队列的最后一个元素。如果双端队列为空，则返回null。
Deque接口提供的用于实现堆栈的方法：
- push() - 在双端队列的开头添加元素
- pop() - 从双端队列的开头删除元素
- peek() - 从双端队列的开头返回一个元素但不删除
解题技巧
一般看到题目有两两消除的操作，例如括号之类，就可以考虑使用栈
- 辅助栈/队列：因为栈是不能遍历的，只有入栈和出栈两种操作，如果我们需要保存栈中的某一个特殊值，比如最大值/最小值/栈反转之类，通常就需要考虑使用辅助栈或者队列。
常见问题 | 问题描述 | 解题思路 | 题目 |
栈操作 | 操作一个栈，例如返回最大/最小值/反转栈 | 使用辅助栈 | |
对称元素消除 | 括号、数学表达式等有对称性的元素消除 | 关键是考虑入栈和出栈的条件 |
9、滑动窗口
滑动窗口基础
滑动窗口主要用来处理连续问题。从类型上说主要有：
- 固定窗口大小
- 窗口大小不固定，求解最大的满足条件的窗口
- 窗口大小不固定，求解最小的满足条件的窗口
后面两种我们统称为可变窗口。当然不管是哪种类型基本的思路都是一样的，不一样的仅仅是代码细节。
对于固定窗口，我们只需要固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点，并且保证：
- l 初始化为 0
- 初始化 r，使得 r - l + 1 等于窗口大小
- 同时移动 l 和 r
- 判断窗口内的连续元素是否满足题目限定的条件
- 如果满足，再判断是否需要更新最优解，如果需要则更新最优解
- 如果不满足，则继续。
对于可变窗口，我们同样固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点。r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。我们需要保证：
- l 和 r 都初始化为 0
- r 指针移动一步
- 判断窗口内的连续元素是否满足题目限定的条件
- 如果满足，再判断是否需要更新最优解，如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。
- 如果不满足，则继续。
滑动窗口算法模板
解题技巧
- 看到题目求解“连续子串 xxxx”，“连续子数组 xxxx”，就应该可以想到滑动窗口。
- 使用哈希表：滑动窗口题目里面可以使用哈希表快速判断元素是否重复，一般有两种情况；
- 充当滑动窗口的作用：如果哈希表和左右指针里面的元素始终保持一致，此时哈希表就相当于一个滑动窗口。哈希表可以快速判断元素是否存在窗口里面，把时间复杂度从O(n)降低位O(1)。
- 记录元素的最新出现下标：如果左右指针移动但不会从哈希表里面删除元素，哈希表就记录了所有曾经出现过的元素的最新下标。
常见问题 | 问题描述 | 解题思路 | 题目 |
固定窗口/可变窗口 | 一般题目中会要求连续子串、连续子数组等，这种就优先考虑滑动窗口。 | 滑动窗口题目的关键在于设置左右指针的移动条件，可以考虑使用 哈希表优化查找时间。 |
10、回溯算法
回溯算法基础
回溯是 DFS 中的一种技巧。回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。通俗上讲，回溯是一种走不通就回头的算法。
回溯的本质是穷举所有可能，尽管有时候可以通过剪枝去除一些根本不可能是答案的分支， 但是从本质上讲，仍然是一种暴力枚举算法。回溯法可以抽象为树形结构，并且是是一颗高度有限的树（N 叉树）。回溯法解决的都是在集合中查找子集，集合的大小就是树的叉树，递归的深度，构成树的高度。
回溯算法模板
另外元素分为可以回头重复使用和不能回头重复使用两种情况：
- 元素可以回头重复使用，例如全排列这种题目，需要使用一个boolean数组记录每个位置是否被使用过，并在出入栈的时候进行标记。
解题技巧
- 先画图，再编码。去思考可以剪枝的条件， 为什么有的时候用 used 数组，有的时候设置搜索起点 begin 变量，理解状态变量设计的想法。
- 回溯题目的另外一个考点是剪枝， 通过恰当地剪枝，可以有效减少时间，一个简单的原则就是避免根本不可能是答案的递归。
常见问题 | 问题描述 | 解题思路 | 题目 |
排列、组合、子集相关问题 | ㅤ | ㅤ | |
字符串中的回溯问题 | ㅤ | ㅤ | |
游戏问题 | ㅤ | ㅤ |
11、贪心算法
12、动态规划
动态规划的本质是递归 + 记忆化，等于缓存的递归。虽然本质是递归，但是题目不会真的写成递归的形式，而是找出状态方程后写成循环的形式。
动态规划三步骤：
- 状态定义：定义动态规划数组来保存历史状态，明确每一个数组元素表示什么内容。
- 转移方程：找出数组元素之间的状态关系，这是最关键的一步，也就是找出状态转移方程。
- 初始状态：确定数组元素初始值。
- 开始写循环。
常见问题 | 问题描述 | 解题思路 | 题目 |
简单应用 | ㅤ | 这些题目一般一眼就可以看出动态转移方程，比较简单 | |
复杂应用 | ㅤ | 这些题目需要自己定义状态数组的含义，并找出状态转移方程，需要积攒一定的经验才能做出来 | |
股票问题 | 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 N 笔交易。 | 只要能解决最后一道最难题，前面三道题都可以解决。定义三维数组dp[i][k][j]表示第i天的最大收益
• i表示是第i天
• k表示是否持有当天股票，1表示持有，0表示不持有
• j表示已经完成了j次交易状态转移方程：dp[i][k][0] = max{dp[i-1][k][0], dp[i-1][k-1][1] + prices[i]}dp[i][k][1] = max{dp[i-1][k][1], dp[i-1][k][0] - prices[i]} | |
背包问题 | ㅤ | ㅤ | ㅤ |
- Author:mcbilla
- URL:http://mcbilla.com/article/50386f83-4fca-497a-b8bf-87748e0ade95
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!