[toc]
范围
优先级队列，二分搜索，滑动窗口，双指针，单调栈
不会考动规了，贪心和BFS/DFS我考这么多次也没遇上过，主要集中在字符串、二分法、滑窗/双指针、二叉树上
LC上没啥设计题，推荐在3ms上搜过往的真题自己练习。总之就是多用OO，多建几个对象，不要用一堆List、Map存，不然到时候query、process、remove的时候要同时更新好几个集合，很痛苦还容易出错。
数据结构&算法
一、总体目标
功能上，实现CRUD，其中，查找是其他的基础；性能上，考虑时间复杂度和空间复杂度（内存和外存）。
排序问题还是查找问题，数据是静态还是动态的，数据有无重复的
指针&引用，都是指内存的地址
1.时间复杂度
平均时间复杂度就是加权平均期望时间复杂度，分析的时候要结合概率论的知识。
2.要学习它的由来、特性、适用的场景以及它能解决的问题。
工程常用：红黑树、跳表
3.性能升级
链表改成平衡二叉查找树
红黑树、跳表、有序动态数组还是散列表呢？
时空互换（查表，hashmap存储，缓存中间的计算结果）
- 海量数据小内存的处理
1.小内存，分流到不同的服务器上，分批处理的思路，借助临时的文件，处理使用散列表+排序等等实现一个文件，多个文件的处理结果再处理下。
2.硬盘，数据库存储
3.分治思想
- 大数值范围的数据处理，溢出
二、数据结构
1.数组&链表
数组，优秀的是随机访问（已知下标）,O(1)，针对查找一个数，综合来讲，还是依次遍历比较，还是O（n）
链表，单链表，循环环链表（头尾），双向链表（前后邻居都知道）
-
链表是否带一个哨兵结点（一个占位的空节点），避免插入删除对头尾结点的特别处理
实现LRU缓存淘汰算法，维护一个按照访问时间从大到小有序排列的链表结构
跳表，链表+多级索引（hash）,见下文，跳表中存储的数据本来就是有序的了
java初始化二维数组的三种方式
char[][] num={{'1','2','3'},{'3','5'}};
列表倒序
Collections.reverse(list);
2.栈&队列
栈（Stack），先进后出，左右括号一一匹配性，运算符计算
队列（Queue），先进先出，资源排队，循环队列，阻塞队列，并发队列（基于数组的循环队列，利用CAS原子操作，可以实现非常高效的并发队列）
Deque
Deques can also be used as LIFO (Last-In-First-Out) stacks. deque（双端队列）
PriorityQueue
LinkedList
LinkedList本质是双向链表，是可以当做队列或栈使用的。Queue q=new LinkedList();
- push pop（栈）
- addFirst、addLast、removeFirst、removeLast（队列）
- add/offer,remove/poll，peek取而不删，功能一致，前者抛异常
3.MAP
LinkedHashpMap
=>accssprder =true.天然的LRU
4.二叉树
可以数组存储（2i和2i+1是子节点的下标，根存在1）适合完全二叉树紧密排布；可以链表（常用）。
二叉搜索树
- 红黑树
二叉树前中后序遍历
preOrderTraverse(TreeNode root){
if root ==null
return;
print(root)；//根
preOrder(root.left);//左
preOrder(root.right);//右
}
inOrderTraverse(TreeNode root){
if root ==null
return;
inOrder(root.left);//左
print(root)；//根
inOrder(root.right);//右
}
postOrderTraverse(TreeNode root){
if root ==null
return;
postOrder(root.left);//左
postOrder(root.right);//右
print(root)；//根
}
N叉树遍历
Traverse(TreeNode root){
if root ==null
return;
前序：print(root)；//根
for child in root.childs:
preOrder(child);//子节点
}
后序：print(root)；//根
注意：树的遍历，根是在循环的外面；与回溯不同
堆
5.图
顶点&边（度）。无向图，度：一个顶点有多个条边（微信好友）；有向图，入度&出度（微博好友关系）；带权图。
存储方法：
- 邻接矩阵，如果顶点i与顶点j之间有边，我们就将A[i][j]和A[j][i]标记为1，对于带权图，数组中就存储相应的权重。清晰但容易稀疏图容易浪费空间。
- 邻接表，每个顶点的链表中存储的，是跟这个顶点有边相连的顶点。注意，有向图有出入的，需要多个实现。
三、要解决的问题
1.排序
选择影响因素：数组是否基本有序、时间复杂度（最好最差平均）、原地操作、是否能稳定（相同值的顺序排序后不变）
[图片上传失败...(image-6136eb-1692357029183)]
$$
O(n^2)，冒泡、插入、选择排序，时间复杂度 ,空间复杂度 原地操作，不需要额外申请空间，
优先插入排序（选择不稳定、冒泡每次交换要赋值4个，还需要辅助变量）
$$
冒泡
提前剪枝：当前一轮比较没有要交换的，说明已经有序，可以break了
√插入=》希尔排序
数组分为两部分，前面有序的，后面待排序的。从a[1]开始，将当前这个数插入到合适的位置。
涉及到数组插入元素
选择
数组分为两部分，每次待排序中选择最小的放到有序的下一个（与待排序的第一个交换）
归并
分治思想，分为两个子规模，处理它有序后+合并两个有序数组（需要辅助函数）。递归来实现。
虽然几乎任意O(nlogn)，但是合并费内存，使用得少。
合并多个有序的结构：我们从这100个文件中，各取第一个字符串，放入数组中，然后比较大小，把最小的那个字符串放入合并后的大文件中，并从数组中删除。我们将从小文件中取出来的字符串放入到小顶堆（插入、删顶O(logn)）中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。
√快速排序
快排核心思想就是分治和分区。partition函数（原地交换（选择排序思想，数组O(1)插入））选择一个分界点，将比它小的放它左边，将比它大的放它右边，（此时不用管左边各个元素有序），
[图片上传失败...(image-60e4e4-1692357029183)]
-
如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素？
——分区思想，保证左分区A[0,p-1]<privot,A[p]<右分区A[p+1,r]， 比较K与p+1的大小，可以确定 大致的哪个分区，再进行递归
都是递归实现。归并先分子问题，再合并，快排先确定分界，再分子问题。归并非原地操作，稳定；快排是原地的，但不稳定。但是考虑到分区点的选择，快排的时间复杂度就从O(nlogn)退化成了O(n2)=》合理选择分区点（左右分区差不多），随机法；三数取中法（每隔xx个数取一个数，再取平均值,头中尾）
堆排序
堆排序包含两个过程，建堆和排序。我们将下标从�22n到11的节点，依次进行从上到下的堆化操作，然后就可以将数组中的数据组织成堆这种数据结构。接下来，我们迭代地将堆顶的元素放到堆的末尾，并将堆的大小减一，然后再堆化，重复这个过程，直到堆中只剩下一个元素，整个数组中的数据就都有序排列了。
非常稳定，原地操作。性能略逊于快排（1.一个顺序访问，一个跳着访问；2.堆排序的交换次数多）
Glibc.qsort:输入数据量下，使用归并排序；否则使用快速排序，此过程中，如果区间数量《4，使用快排排这部分数（在小规模数据面前，O(n2)时间复杂度的算法并不一定比O(nlogn)的算法执行时间长）。
防止递归溢出，自己实现一个堆上的栈，手动模拟递归来解决的。
桶排序
11000数值内的所有数放到桶01，100012000数值内的所有数放到桶02……，每个桶内部使用快排。最后按桶的顺序组合起来。
适合外部排序的情况，十万个数，100M内存，分批排序。
分到不同的桶里，不需要比较？——hashmap等，O(1)
存放在不同的桶里，这里不需要内存吗？——可以写入到磁盘文件，每满就写个文件
如何确定数据范围、及大致的分布？
计数排序
特殊的桶排序。桶数=数据范围个数，那么可以统计出每个值的分布个数C[]，再累加这个数组，得到小于等于这个数值的数据的个数（也是排序后的下标）。扫描原始数组，取出C[元素]=排序后数组的下标，给新数组赋值后然后再C[元素]--=下一个相同数的下标。
此时，需要申请的内存比较大（1:1）
计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
基数排序
10万个11位电话号码，从低位整体一位位地比较，10万个数比较，用上面的O（n）稳定的排序算法，进行比较。
当字符串不等长时，可以使用'0'补齐。
API
`Stream.sorted`、`Collections.sort`、`List.sort`和`Arrays.sort`方法 + 比较器
Collections.reverse(news);
比较器：Comparator<Student> nameComp = (s1, s2) -> s1.getName().compareTo(s2.getName());
=Comparator.comparing(Student::getName, 可选(s1, s2) -> s2.compareTo(s1));
= Comparator.reversed()
list.sort(Comparator.comparingInt(String::length).reversed()
.thenComparing(Comparator.comparing(String::toLowerCase, Comparator.reverseOrder())));
取前10个=》堆
时间有序性
特性有序性，动态维护数据有序性，「优先队列」（堆）是可以胜任的
PriorityQueue的迭代遍历不是有序的，而是二叉树的保存结构
LinkedList，头插addFirst
2.查找
二分
数据集合得有序。内存空间连续，数据规模适中的场景，也不能太大。
二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用。
二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如今天讲的这几种变体问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。
[图片上传失败...(image-e5bcd3-1692357029183)]
链表实现二分，链表+多级索引=》跳表，Redis中的有序集合。动态数据结构，可以支持快速地插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树。多级索引，内存消耗大。空间换时间。实际开发中，比较的对象，我们只是索引要比较的数据，比起对象来，内存是可以忽略的。如果一直插入的话，索引之间的间距就会失衡，极端情况某一截特别长，退化成链表=》随机函数，随机函数生成了值K，那我们就将这个结点添加到第一级到第K级这K级索引中。
[图片上传失败...(image-e87c1a-1692357029183)]
按照区间来查找数据这个操作，红黑树的效率没有跳表高。代码可读性实现简单。可以动态重构节点。
针对动态数据集合=》二叉树？？？
http://3ms.huawei.com/km/blogs/details/10428257
散列Hash
利用了数组的随机读取的特性，实现近似“O(1)”的时间复杂度（冲突）。编号Key和数组下标的映射方法=》散列函数，f(key)=index,∈N，散列函数生成的值要尽可能随机并且均匀分布*。例如，Word文档中单词拼写检查功能
如何避免hash冲突(不同的key,可能通过hash函数指向同一个下标)。再好的散列函数也无法避免散列冲突。散列表碰撞攻击：引起严重的性能下降，比如十万倍，导致服务器无法响应其他请求，实现DoS攻击。
装载因子：设置冗余数组空间，降低冲突的概率。可以类似Vector，进行动态的扩容。区别是此处，可以’慢慢‘搬移：如果对排列顺序没有明显的要求，可以在每次插入新数据的时候，搬移一个老的数据到新的空间中，避免一次性搬移耗时大。查找的时候，就查两处。散列就是如此的。
-
开放寻址：idx=hash(key)+i，i∈N，依次往后查找可用空间插入；查找的时候，比较是否相等直到遇到空闲的下标；删除，需要将这个位置标记为deleted（避免查找的时候断链子）
- 二次探测：idx=hash(key)+i平方，i∈N
- 双重散列：有好多个散列函数，一个不行就换另一个
链表法：每个数组下标跟一个链表（或其他更高效的红黑树等等，JKD1.8的HashMap，8内用链表，8外用红黑树），执行链表的插入删除查找
LinkedHashMap：天然支持LRU算法，按访问顺序排列。实现是靠双向链表和散列表
哈希算法
实际上，散列函数也是哈希算法的一种应用。
任意长度的二进制值串映射为固定长度的二进制值。从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）。分别是安全加密、唯一标识（信息摘要，如何快速判断图片是否在图库中）、数据校验完整性和正确性、散列函数、分布式系统（一个机器的性能不够，通过hash将任务有规律得分配到xx号机器上）：负载均衡、数据分片、分布式存储。
针对常用的密码，大量重复出现在，是可以预先计算出来的，那就可以拿到密码了。怎么办呢？字典攻击，我们可以引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度
二叉查找树/二叉有序树
左子树<根<=右子树，重复数据插入到根的右子树
中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。
-
平衡二叉查找树，左右子树的高度差不大，树的高度接近logn，插入、删除、查找O(logn)，平衡二叉查找树在某些方面还是优于散列表，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。
- AVL树，AVL树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有点高了。
- Splay Tree（伸展树）、Treap（树堆）
- 红黑树，不严格的平衡二叉查找树
堆
其实就是一种完全二叉树，每个节点的值必现大于等于子树。最常用的存储方式就是数组。
堆顶元素存储的就是堆中数据的最大值或者最小值。相比于二叉查找树，弱化了左右子树间的大小约束，强化了二叉树的归左特性。
插入，从下往上堆化（插到最后子节点的位置，依次与父节点比较大小直至满足大小关系；删除堆顶，将最后一个叶子节点放到堆顶，再从下往上堆化。避免了空洞，不满足完全二叉树的特性。删除堆顶数据和往堆中插入数据的时间复杂度都是O(logn)。
堆的应用一：优先级队列
按优先级高的先出。比如，赫夫曼编码、图的最短路径、最小生成树算法等等。Java的PriorityQueue。归并排序的，合并多个有序数组。
堆的应用二：利用堆求Top K
我们可以维护一个大小为K的小顶堆，插入的时候，与堆顶比较，满足就更新。最后，返回这K个东西。
堆的应用三：利用堆求中位数，求xx位的数据
静态的数据结构，直接排序去中间下标；
动态数据结构，使用一个大顶堆和一个小顶堆，大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。插入，如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；否则，我们就将这个新数据插入到小顶堆。插入后，看下个数是否只相差1，否则移动一个
图的搜索算法
BFS
按层搜索，O(顶点数+边数)。从s顶点到t顶点，bfs找到的就是最短路径。空间复杂度是O(顶点数*3)，记录visited数组，当前层queue队列，结果路径存储的数组。
6度空间交友规则。
DFS
走分岔路，一条道直到黑，不撞南墙不回头（回头的条件，下一个顶点已经查过了）。从s顶点到t顶点，dfs找到的不一定是最短路径。时间O(边数*2)，空间同上。
回溯思想，递归实现，需要一个全局found标志位来中断递归。
连通图（图中的所有顶点都是连通的）
A、IDA
字符串匹配
单模式串匹配
BF暴力朴素搜索
双重循环，O(n*m)
Rabin-Karp算法
主串按模式串的长度切分查找，通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。
哈希算法的设计：将26字母转换成26进制（位权值26），将m位字符串位计算出十进制的数值。那么，右移一位的结果值跟上一次的结果值及两次差异的两个字符是有递推公式的。=》通过一次主串的扫描，就可以计算出所有待匹配串的哈希值。
Boyer-Moore算法
怎么样不匹配的时候多滑动几位？从模式串的末尾比起，
KMP算法
多模式串匹配（多个模式串和一个主串之间做匹配）
Trie树字典树
利用字符串之间的公共前缀，将重复的前缀合并在一棵树下，形成差异N叉数。如果有新的要插入了，是怎么扩展树的每一层的呢？二叉树的实现，是使用了pleft和pright。但是这里，分支数不是固定的，所以使用一个LinkedList？
实现搜索引擎的搜索关键字提示，IDE自动输入补全。此时，分支数有范围，0~26，可以使用一个数组来映射下一级的，这样插入也很方便，查找这里O(1)。显然，这种方式控件耗费打，且浪费。再考虑到工程实现，
Trie树比较适合的是查找前缀匹配的字符串。精确匹配查找，在工程中，更倾向于用散列表或者红黑树。
敏感词过滤，上面的多个模式串之间是有关联的（有共同的前置），敏感词可没有关联？？？
拼写纠错功能呢？量化两个字符串的相似度（编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符））。
208 纯纯Trie树（有可能已经插入了，先判空）
211 Tire树+BFS+DFS
AC自动机
借鉴KMP算法对BF算法进行改进（对Tire树构建失败指针），对Tire树进行多往后滑动几位。
四、算法思想
1.递归
核心3步：分解成小规模的问题（可能是几个，一次可以跨1级2级台阶），考虑问题之间的递推关系，确定最小规模的终止条件。
代码简洁，但时间复杂度高。实现依赖系统的栈，每次都要保存现场，内存要求高。
避免重复计算，使用一个数据结构保存中间的结果，每次都先查询有无以计算好的结果
警惕stackOverFlow=》尾递归？
如果避免环递归
2.贪心
霍夫曼编码（Huffman Coding）、Prim和Kruskal最小生成树算法、还有Dijkstra单源最短路径算法。
第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
第二步，我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。如果每一次的选择之间是独立的没有约束的，那么就可以。如果前面的选择会影响后面的选择，那么不能用。
第三步，我们举几个例子看下贪心算法产生的结果是否是最优的。
贪心即使显而易见最好的原则，又有可能不是最优的解。
物品可分割背包问题，可以使用贪心。
3.分治算法
将原问题划分成n个规模较小，并且结构与原问题相似的子问题，子问题之间独立（与动态规划的区别），递归地解决这些子问题，然后再合并其结果，就得到原问题的解。分治算法是一种处理问题的思想，递归是一种编程技巧。
归并排序的实现。MapReduce的本质就是分治，集群并行处理。MapReduce框架只是一个任务调度器，底层依赖GFS来存储数据，依赖Borg管理机器。它从GFS中拿数据，交给Borg中的机器执行，并且时刻监控机器执行的进度，一旦出现机器宕机、进度卡壳等，就重新从Borg中调度一台机器执行。
4.回溯算法
深度优先搜索、八皇后、0-1背包问题、图的着色、旅行商问题、数独、全排列、正则表达式匹配、编译原理中的语法分析，八皇后问题。适合用用递归来实现。
0-1背包问题模型（物品是不可分割的，要么装要么不装，无法贪心），我们可以把物品依次排列，整个问题就分解为了n个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。
正则表达式，
搜索剪枝
回溯算法和 DFS 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」
做选择，继续走，撤销选择再循环；全局变量结果集results，终止条件要深拷贝singleResult。
List<List<Integer>> results=new LinkedList<>();
solution(int[] nums){
List<integer> singleResult=new LinkedList<>();
backTrack(nums,singleResult);
}
backtrack(选择列表，路径){
if 终止条件满足：
result.add(路径深拷贝)//results.add(new LinkedList(singleResult));
return;
for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择再加入选择列表
}
[图片上传失败...(image-eee80d-1692357029183)]
全排列，选项数字数组
八皇后，选项一行的所有列的数字，校验布局二维数组，放置位置是一维
解数独，选项1-9数组，校验布局二维数组，放置位置是二维（先列后行回溯）
5.动态规划
求解最优问题。一个模型三个特征：多阶段决策最优解模型，经历多个决策阶段。每个决策阶段都对应着一组状态。最优子结构、无后效性和重复子问题。
0-1背包重量问题（物品不可分割），遍历所有物品，每次循环，当前物品可以取，也可以不取，记录每一轮所有可能的结果的值（重复的结果合并）。（每次在上一轮的结果上，+0，或+当前物品的值。） f(i)=f(i-1)+a[i]/0.
0-1背包问题，引入物品价值，数组中记录物品的价值。
- 状态转移表法：回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码。我们先画出一个状态表。状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。对于(i, j)重复的节点，我们只需要选择dist最小的节点，继续递归求解，其他节点就可以舍弃了。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。
- 状态转移方程：找最优子结构-写状态转移方程-将状态转移方程翻译成代码。
303 一维数据[left，right]求和
6.四大算法比较
贪心、回溯、动态规划可以归为一类多阶段决策最优解模型，，分治不是。
回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。 一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。区别，是否存在重复可合并的子问题。有重复的话，1.回溯加“备忘录”，2.动规状态转移表法 。
能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。
贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题，通过局部最优的选择，能产生全局的最优选择）。
“多阶段决策最优解模型”：
我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
要注意“阶段”是指的是什么，是每一选项选择，还是数目/步数。
最优子结构、无后效性和重复子问题：
1.最优子结构
最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。
2.无后效性
无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
3.重复子问题
这个概念比较好理解。前面一节，我已经多次提过。如果用一句话概括一下，那就是，不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
背包问题：
1.物品可分割——贪心
2.物品不可分割——动规
找零钱问题：
1.一元钱10张，二元钱5张，五元钱3张，一共付12元，最少多少张——贪心
2.一元钱N张，二元钱N张，五元钱N张，一共付12元，最少多少张——动规
路径/迷宫/二维数组，得到一个结果——动规
刷题
二分
[low,high]
while (left <= right)
low=mid+1;
high=mid-1;
- 右侧区间
- 左侧区间
- 左侧区间+右侧区间
- 两边之和大于第三边
- 排序后，两条边二重循环，第三条边可以二分查找，后面的都满足
- 一道简单题，5种解法，方法五：Boyer-Moore 投票算法
- 可以分治递归
- 次数哈希
- 堆PriorityQueue
- TODO学会手动建堆
合并区间/线段
- 左端点升序，右端点降序
- 二维数组排序及与list转换
- result.toArray(new int[result.size()][2]);
- List<int[]> stringList = Stream.of(intervals).collect(Collectors.toList());
- TODO 56&57的关系
- 左端点升序，右端点降序
- 因为左端点升序，不需要二重循环,一旦不满足，立刻以这个为基准，一遍扫描即可
- 贪心：先定右端点最小的区间，再找更小的左端点，右端点排序
- 动态规划：以当前区间i为最后一个区间，可以选出的区间数量的最大值。二重循环，超时
- 类似 预定最多的会议=》最先结束的会议，排序，才能排更多的会议
- TODO 300. 最长递增子序列
双指针
- 双指针标记3段前后的分段下标（经典的在线算法。适用于不知道数据量有多大，但用户一次只给你一个数。从任意时刻来看，数组都是有序的）
数个数重新构建数组（不讲武德）
- 频次哈希，重建StringBuilder
- HashMap排序？
- PriorityQueue,优于直接map排序
- 使用int[26+26+10][2],[key][cnt]来存储频次，Arrays.sort二重排序
-TODO 桶排序）
滑动窗
- 一段区域/窗口
- [left,right)避免边界单独计算
- right不断增大窗口直到找到可行解，开始left收缩窗口优化解，当不符合了，right再增，直到right达到末尾。过程中，不断更新解。
- 通过持有满足条件的一段公共区域，减少重复计算；
- 我写了首诗，把滑动窗口算法算法变成了默写题 | labuladong 的算法小抄
- 【宫水三叶】双指针实现滑动窗口
- 二重循环，超时,因为重复计算i,i+1,i+2
- 滑动窗口
- 前缀和(避免区间和重复计算)+二分:正数组，前缀和是递增的,查找sum[j]>=target+sum[i]的最小j-i+1
- 此处二分的类似611. 有效三角形的个数，有很多备选，不一定非要挨个判断是否满足=>逆向：当有序的时候，可以考虑使用二分折半查找
- 固定窗口大小的滑动窗口问题
- 字串<=> 字符种类相同，每种个数相同
- TODO 滑动窗口判断是否cnt满足=》cnt满足，查找n的区间，双指针
- Java相等不要直接使用==，使用equeals()
- 字符的频次统计，可以考虑int[26]
- 与567相同的题目，只是一个是找到即return,一个记录所有下标再返回。
前缀树
知识点：N叉树;子树，字母时往往使用int[26]，可以用HashMap
使用场景：浏览器提示联想，输入纠错
前缀树小结
- 有可能已经插入了，先判空
- isTail标记是否完整，匹配搜索时前缀
- TODO 宫水三千 数组实现Tire树
- Trie + dfs搜索（.通配，需要递归到底才能知道是否匹配）
TODO 各类「区间和」问题策略
前缀和
- 知识点：重复计算，可以缓存结果啊
- 简单的动态规划，类似斐波那契数列
- 二维看面积，（A-B）(C-D)=AC-AD-BC+BD。
差分数组
- 知识点：对差分数组做前缀和，得到原数组。差分<=>前缀和，互为逆操作。（求导和积分）
- 前缀和，不需要多一个来构建+1。原题是带0的，正常使用，否则起止下标都要减一。
- 提示：区间增减
- 小而美的算法技巧：差分数组 | labuladong 的算法小抄
- 任意站点，乘客人数之和不大于容量
- 坐车站[0,2），实际占有[0,1]区间
TODO 1674. 使数组互补的最少操作次数
给定数组A，任意连续区间[Ai,Aj]中，寻找最大Ai-Aj值。
- a2-a4= ( a2-a3)+ (a3-a4)。 缓存每次的差值，依次相加，遇0重新起点，比较最大的差值。一遍扫描。
int numCodeStats = codeStats.size(), ma = 0, Value = 0;
for(int i = 1; i < numCodeStats; i++){
Value = codeStats[i-1] - codeStats[i] + Value;
Value = max(0, Value);
ma = max(ma, Value);
}
return ma;
线段树
单调栈
- 单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。
- 处理「下一个更大元素」，「上一个更小元素」问题
-
labuladong
496. 下一个更大元素 I
- 存的是index差
- TODO DP
- 有些要回头查=》把数组复制一遍+单调栈,循环数组通用处理：%。如果一直失败，考虑是不是漏了=号，此时也要pop
