常用算法笔记
[TOC]
Algorithm
排序
选择排序
思路
对一个序列A中的元素A[1] ~A[n]，令i从1到n枚举，进行n趟操作，每趟从待排序部分[i,n]中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样会形成有序区间A[1] ~A[n]。n趟操作后，所有元素都是有序的。
实现
private void selectSort(int[] arr, int n) { for(int i=0;i<n;i++){ int k=i for(int j=i+1;j<n;j++){ if(arr[k]>arr[j])k=j; } int temp=arr[i]; arr[i]=arr[k]; arr[k]=temp; } }稳定排序算法，时间复杂度O(n^2^)。
插入排序
思路
对序列A的n个元素A[1]~ A[n]，令i从2到n，需要进行n-1趟操作。在某一趟，序列A的[1,i-1]已经有序，在其中寻找一位置j，使得A[i]插入后有序，A[j+1]~ A[i]需要后移一位。
实现
private void insertSort(int[] arr, int n) { for(int i=1;i<n;i++){ int temp=A[i]; int k=i; while(k>0&&temp<arr[k-1]){ arr[k]=arr[k-1]; k--; } arr[k]=temp; } }稳定排序算法，时间复杂度为O(n^2^)。
冒泡排序
思路
每次通过交换的方式，将当前剩余元素的最大值，移动到一端，每一趟从左到右依次比较相邻两个数，如果大的数在左边，则交换这两个数。
实现
private void sort(int[] arr, int n) { for(int i=0;i<n;i++){ for(int j=0;j<n-i;j++){ if(arr[j]>arr[j+1]){ int temp=arr[j+1]; arr[j+1]=arr[j]; arr[j]=temp; } } } }是一种稳定排序算法，时间复杂度为0(n^2^)。
归并排序
思路
将序列两两分组，将序列归并为[n/2]个组，组内单独排序，然后将这些组在两两合并，生成[n/4]个组，组内再单独排序，以此类推。
实现
1) 递归实现
int maxn=100; private merge(int[] arr, int l1, int r1, int l2, int r2) { int i=l1; int j=l2; int[] temp=new int[maxn]; int index; while(i<=r1&&j<=r2){ if(arr[i]<arr[j])temp[index++]=arr[i++]; else temp[index++]=arr[j++]; } while(i<=r1)temp[index++]=arr[i++]; while(j<=r2)tep[index++]=arr[j++]; for(int i=0;i<index;i++){ arr[l1+i]=temp[i]; //合并后序列赋值 } } private void mergeSort(int[] arr, int left, int right){ if(left<right){ int mid=(left+right)/2; mergeSort(arr,left,mid); mergeSort(arr,mid+1,right); merge(arr,left,mid,mid+1,right); } }2) 非递归实现
令步长setp初值为2，将数组内没step个元素作为一组，对其内部排序（左右step/2合并），然后step*2，重复上面操作，直到step超过元素个数n。
private void mergeSort(int[] arr, int n){ for(int step=2;step/2<=n;step*=2){ for(int i=0;i<n;i+=step){ int mid=i+step/2-1; if(mid+1<n){ merge(arr,i,mid,mid+1,min(i+step-1,n-1)); } } //此处可以输出归并排序的某一趟序列 } } private int min(int x, int y){ return x>y?y:x; }是一种稳定排序算法，时间复杂为O(nlongn)。
快速排序
思路
对于一个序列A[1]~ A[n]，调整序列中元素顺序，是的左侧的元素都不超过A[1]，右侧的元素都大于A[1]。
实现
private int Partition(int[] arr, int left, int right){ int temp=arr[left]; while(left<right){ while(left<right&&arr[right]>temp){ right--; } arr[left]=arr[right]; while(left<right&&arr[left]<=temp){ left++; } arr[right]=arr[left;] } arr[left]=temp; return left; } private quickSort(int[] arr, int left, int right){ if(left<right){ int pos=Partition(arr,left,right); quickSort(arr,left,pos-1); quickSort(arr,pos+1,right); }非稳定排序算法，时间复杂度为O(nlogn)。当序列接近有序是，会达到最坏时间复杂度O(n^2^)，主要在于主元没有吧当前区间划分成两个长度接近的子区间。
堆排序
思路：在建堆完毕后，堆排序就是取出堆顶元素，然后将堆的最后一个元素替换之堆顶，再进行一次针对堆顶元素的向下调整，直至堆中只有一个元素为止。
实现
private void heapSort(int[] heap,int n){ createHeap(); //0(n) for(int i=n;i>1;i--){ int temp=heap[1]; heap[1]=heap[i]; heap[i]=temp; downAdjust(1,i-1); //调整堆顶 } }非稳定排序算法，时间复杂度为O(nlogn)。
散列
除留余数法
H(key)=key%mod, TSize是一个素数，mod一般直接取成与TSize相等。
线性探查法
H(key)被占用时，检查H(key)+1，直至找到一个可用位置。
平方探查法
H(key)+1^2^，H(key)-1^2^，一直到H(key)+k^2^......，当k>TSize时，一定无法找到位置。
链地址法
设定Link[0]~ Link[mod]，Link[h]存放H(key)=h的一条单链表。
递归
分治
分治法将原问题划分成若干个规模较小而结构与原问题相同或者相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解。
递归
- 递归边界
- 递归式(递归调用)
全排列和n皇后
int n;
int maxN=10;
int[] P=new int[maxN];
boolean[] hashTable=new boolean[maxN];
private void generateP(int index){
if(index==n+1)return; //已经排完1~n
for(int i=1;i<=n;i++){
if(!hashTable[i]){
P[index]=i;
hashTable[i]=true;
generateP(index+1);
hashTable[i]=false; //返回最先状态
}
}
} 对于n皇后，实际上是对n行n列的一个关于n的全排列问题，解决办法如下：
int count=0;
private void generate(int index) //index列
{
if(index==n+1){
count++;
return; //合法方案
}
for(int x=1;x<=n;x++){ //遍历x行
if(!hashTable[x]){
boolean flag=true; //是否会冲突
for(int i=1;i<index;i++){ //之前列
if(abs(index-i)==abs(x-P[i])){
flag=false;
break;
}
}
if(flag){
hashTable[x]=true;
P[index]=x; //index列选择x行
generate(index+1);
hashTable[x]=false;
}
}
}
}
private int abs(int x)
{
return x>=0?x:-x;
} 贪心
在当前状态下局部最优的策略，来使全局结果达到最优。贪心算法用来解决的问题一定满足最优子结构，即一个问题的最优解可以由它的子问题的最优解有效构造出来。
查找
二分查找
时间复杂度为O(logn)
private int binarySearch(int[] arr, int left, int right, int x)
{
int mid;
while(left<right){
mid=left+(right-left)/2;
if(arr[mid]==x)return mid;
else if(arr[mid]>x){
right=mid-1;
}
else{
left=mid+1;
}
return -1; //查找失败
} 求出序列中第一个大于等于x的元素位置L以及第一个大于x的元素R，这样元素x在序列中存在区间就是[L,R)。
private int lower_bound(int[] arr, int eft, int right,int x)
{
int mid;
while(left<right){
mid=(left+right)/2;
if(arr[mid]>=x)right=mid;
else left=mid+1;
}
return left; //返回夹出来的位置
} 求序列中第一个大于x元素的位置。
private int upper_bound(int[] arr, int left, int right, int x)
{
int mid;
while(left<right){
mid=(left+right)/2;
if(A[mid]>x)right=mid;
else left=mid+1;
}
} 快速幂
private long binaryPow(long a, long b, long m)
{
if(b==0)return 1;
if(b%2)return a*binaryPow(a,b-1,m)%m;
else{
long mul=binaryPow(a,b/2,m);
return mul*mul%m;
}
} Two Pointers
查找序列和
private void findSum(int[] arr, int n, int sum) { int i=0,j=n-1; while(i<j){ if(arr[i]+arr[j]==sum){ i++; j--; } else if(arr[i]+arr[j]>sum)j--; else i++; } }
一些技巧
打表
空间换时间，在程序中一次性计算出所有需要用到的结果，之后查询直接取这些结果。
活用递推
随机选择算法
从无序数组中求出第K大的元素，可以先排序，然后取第K个元素，这样时间复杂度最好为O(nlogn)。
int randSelect(int A[], int left, int right, int K){
if(left==right)return A[left]; //边界
int p=Partition(A,left,right); //
int M=p-left+1;
if(K==M)return A[p]; //找到
if(K<M)return randSelect(A,left,p-1,K);
else return randSelect(A,p+1,right,K-M);
} 随机选择算法的最坏时间复杂度为O(n^2^)，但是对其任意输入的期望时间复杂度确是O(n)，这意味着不存在一组特定的数据使这个算法出现最坏情况。
数学问题
最大公约数与最小公倍数
int gcd(int a,int b){
if(b==0)return a;
else return gcd(b,a%b);
} 公倍数为ab/gcd(a,b)。
素数
素数筛法，时间复杂度为O(nloglogn)。
int maxn=101; //表长
int[] prime=new int[maxn];
int pNum=0;
boolean[] table=new boolean[maxn];
private void findPrime(){
for(int i=2;i<maxn;i++){
if(!table[i]){
prime[pNum++]=i;
for(int j=i+i;j<maxn;j+=i){
table[j]=true; //不是素数
}
}
}
} 质因子分解
组合数
求n!中有多少个质因子p
等于1~n中p的倍数的个数n/p加上(n/p)!中质因子p的个数。
int cal(int n, int p) { if(n<p)return 0; else return n/p+cal(n/p,p); }组合数计算
long C(long n,long m){ long ans=1; for(long i=1;i<=m;i++){ ans=ans*(n-m+i)/i; } return ans; }
搜索
深度优先搜索
n件物品的选择，每件物品有重量和价值，使得价值最大。
private void DFS(int index, int sumW, int sumC){
//index表示第index物品0~n-1
if(index==n)return;
DFS(index+1,sumW,sumC); //不选index件物品
if(sumW+w[index]<=V){ //不超过重量V
if(sumC+c[index]>ans)ans=sumC+c[index];
DFS(index+1,sumW+w[index],sumC+c[index]); //选择
}
} 广度优先搜索
求解矩阵中“1”块。
import java.util.LinkedList;
import java.util.Queue;
class Node{
int x;
int y;
public Node(int x, int y){
this.x=x;
this.y=y;
}
}
public class Solution{
int n,m; //n行m列
int maxn=10;
int[][] matrix=new int[maxn][maxn];
boolean[][] inq=new boolean[maxn][maxn];
int[] X={0,0,1,-1};
int[] Y={1,-1,0,0};
private boolean judge(int x, int y){ //(x,y)是否需要访问
if(x>=n||x<0||y>m||y<0)return false;
return matrix[x][y] != 0 && !inq[x][y];
}
private void BFS(int x, int y){
Queue<Node> Q=new LinkedList<>();
Node node=new Node(x,y);
Q.add(node);
inq[x][y]=true; //已经入队
while(!Q.isEmpty()){
Node top=Q.poll();
for(int i=0;i<4;i++){
int newX=top.x+X[i];
int newY=top.y+Y[i];
if(judge(newX,newY)){
Node temp=new Node(newX,newY);
Q.add(temp);
inq[newX][newY]=true;
}
}
}
}
} 栈
中缀表达式转后缀表达式
1) 设立一个操作符栈，用于临时存放操作符；设立一个数组或者队列，存放后缀表达式。
2) 从左到右扫描中缀表达式，操作数加入后缀表达式中。
3) 操作符，将其优先级与操作符的栈顶操作符的优先级比较：若高于，则将操作符压栈；否则弹出栈顶运算符到后缀表达式中，直到操作符优先级高于栈顶运算符。
4) 重复上述操作，直到中缀表达式扫描完毕，若操作符中仍有元素，则依次弹出至后缀表达式。
计算后缀表达式
从左到由扫描后缀表达式，如果是操作数，就压栈，如果是操作符，就连续弹出两个操作数(后弹出的第一操作数)，然后进行操作符的操作，生成的操作数压栈。
import java.util.*;
class Node{
double num; //操作数
char op; //操作符
boolean flag; //true表示操作数
}
public class Solution{
Deque<Node> deque1=new LinkedList<>(); //操作符栈
Deque<Node> deque2=new LinkedList<>(); //后缀表达式序列
Map<Character,Integer> map=new HashMap<>(); //操作符优先级
public Solution(){
map.put('+',1);
map.put('-',1);
map.put('*',2);
map.put('/',2);
}
String string;
private void Change(){
//转后缀表达式
double num;
char[] cs=string.toCharArray();
Node temp = new Node();
for(int i=0;i<cs.length;){
if('0' <= cs[i]&&cs[i]<='9'){
temp.flag=true;
temp.num=cs[i++]-'0';
while(i<cs.length&&cs[i]>'0'&&cs[i]<'9'){
temp.num=temp.num*10+(cs[i]-'0');
i++;
}
deque2.addLast(temp); //压入后缀表达式
}
else{
temp.flag=false;
assert deque1.peekFirst() != null;
while(!deque1.isEmpty()&&map.get(cs[i])<map.get(deque1.peekFirst().op)){
deque2.addLast(deque1.pollFirst());
}
temp.op=cs[i];
deque1.addFirst(temp);
i++;
}
}
while(!deque1.isEmpty()){
deque2.addLast(deque1.pollFirst());
}
}
double Cal(){ //计算后缀表达式
double temp1,temp2;
Node cur=new Node();
Node temp=new Node();
while(!deque2.isEmpty()){
cur=deque2.pollFirst();
if(cur.flag)deque1.addFirst(cur); //操作数压栈
else{
temp2= Objects.requireNonNull(deque2.pollFirst()).num;
temp1= Objects.requireNonNull(deque2.pollFirst()).num;
temp.flag=true; //临时操作数
if(cur.op=='+')temp.num=temp1+temp2;
if(cur.op=='-')temp.num=temp1-temp2;
if(cur.op=='*')temp.num=temp1*temp2;
if(cur.op=='/')temp.num=temp1/temp2;
deque1.addFirst(temp);
}
}
assert deque1.peekFirst() != null;
return deque1.peekFirst().num; //后缀表达式的值
}
} 静态链表
struct Node{
typename data; //数据域
int next;
}node[size];
node[1111]=2222;
node[2222]=3333;
node[3333]=-1; 树
树的定义与性质
1) 树可以没有节点，称为空树。
2) 树的层次从根节点开始算起，即根节点为第一层。
3) 节点的子树棵树称为节点的度，树中节点的最大的度称为树的度。
4) n个节点的树，边数为n-1。
5) 叶子节点被定义为度为0的节点。
6) 节点的深度是从根节点累加，节点的高度是从底层叶子节点累加。
7) 多棵树组成森林。
二叉树
1) 要么二叉树没有根节点，是一棵空树。
2) 要么二叉树由根节点、左子树、右子树组成，且左子树和右子树都是二叉树。
满二叉树：每一层节点个数都达到了当层能达到的最大节点数。
完全二叉树：除最下面一层外，其余层节点个数都达到了最大节点数。
完全二叉树存储结构：任何一个节点x，其左孩子编号一定是2x，而右孩子编号一定是2x+1。根节点从1开始存放，则数组中袁术存放顺序恰好为该完全二叉树层序遍历结果。
二叉树遍历
class TreeNode{
int val;
TreeNode left=null;
TreeNode right=null;
public TreeNode(int val){
this.val=val;
}
} 先序遍历
private void preOrder(TreeNode root){ if(root==null)return; System.out.println(root.val); preOrder(root.left); preOrder(root.right); }中序遍历
后序遍历
层序遍历
private void layerOrder(TreeNode root){ Deque<TreeNode> deque=new LinkedList<>(); if(root==null)return; deque.addLast(root); while(!deque.isEmpty()){ TreeNode p=deque.pollFirst(); System.out.println(p.val); if(p.left!=null)deque.addLast(p.left); if(p.right!=null)deque.addLast(p.right); } }
重建二叉树
根据先序遍历和中序遍历结果重建二叉树。
private TreeNode create(int[] pre, int preL,int preR, int[] in, int inL,int inR){
if(preL>preR)return null;
TreeNode root=new TreeNode(pre[preL]);
int k;
for(k=inL;k<=inR;k++){
if(in[k]==pre[preL])break;
}
int numLeft=k-inL;
root.left=create(preL+1,preL+numLeft,inL,k-1); //左子树
root.right=create(preL+numLeft+1,preR,k+1,inR); //右子树
return root;
} 必须有中序遍历才能重建二叉树，其他顺序的遍历只能提供根节点。
二叉查找树
1) 要么二叉查找树是一颗空树。
2) 要么二叉查找数由根节点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树的所有绩点数据域均小于等于根节点数据域，右子树均大于。
中序遍历结果有序。
插入操作：
private void insert(TreeNode root,int x){
if(root==null){
root=new TreeNode(x);
}
if(x==root.val)return; //已存在
else if(x<root.val)insert(root.left,x);
else insert(root.right,x);
} 删除操作：
二叉查找树中比节点权值小的最大节点称为前驱，比节点大的最小节点称为后继。
private void delete(TreeNode root, int x){
if(root==null)return; //不存在为x的节点
if(root.val==x){
if(root.right==null&&root.left==null)root=null; //叶子节点
else if(root.left!=null){
TreeNode left=root.left;
while(left.right!=null)left=left.right; //前驱
root.val=left.val; //前驱覆盖root
delete(root.left,left.val); //删除节点
}
else{
TreeNode right=root.right;
while(right!=null)right=right.left; //后继
root.val=right.val; //后继覆盖root
delete(root.right,right.val);
}
}
else if(root.val>x){
delete(root.left,x);
}
else delete(root.right,x);
} 平衡二叉树
左子树与右子树高度之差的绝对值不超过1，其中左子树与右子树高度之差称为该节点的平衡因子。
由于AVL树高度为O(logn)级别，因此查找操作时间复杂度为O(logn)。
class TreeNodeAVL{
int val=0,height=1;
TreeNodeAVL left=null;
TreeNodeAVL right=null;
public TreeNodeAVL(int val){
this.val=val;
}
}
private getHeight(TreeNodeAVL root){
if(root==null)return 0;
return root.height;
}
private getBalanceFactor(TreeNodeAVL root){
return getHeight(root.left)-getHeight(root.right);
}
private void updateHeight(TreeNodeAVL root) {
root.height=max(getHeight(root.left),getHeight(root.right))+1;
}
private int max(int x, int y){
return x>y?x:y;
}
//左旋
void LRotation(TreeNodeAVL root){
TreeNodeAVL temp=root.right;
root.right=temp.left;
temp.left=root;
updateHeight(root);
updateHeight(temp);
root=temp;
}
//右旋
void RRotation(TreeNodeAVL root){
TreeNodeAVL temp=root.left;
root.left=temp.right;
temp.right=root;
updateHeight(root);
updateHeight(temp);
root=temp;
} 插入后，节点平衡因子绝对值大于1（只能是+-2）。
| 树形 | 判定条件 | 调整方法 |
|---|---|---|
| LL | BF(root)=2,BF(root.left)=1 | root右旋 |
| LR | BF(root)=2,BF(root.left)=-1 | 对root.left左旋，对root右旋 |
| RR | BF(root)=-2,BF(root.left)=-1 | 对root左旋 |
| RL | BF(root)=-2,BF(root.left)=1 | 对root.right右旋，对root左旋 |
void insert(TreeNodeAVL root, int v){
if(root==null){
root=new TreeNodeAVL(v);
return;
}
if(v<root.val){
insert(root.left,v); //左子树
updateHeight(root);
if(getBalanceFactor(root)==2){
if(getBalanceFactor(root.left)==1){
//LL型
RRotation(root);
}
else{
LRotation(root.left);
RRotation(root);
}
}
}
else{
insert(root.right,v) ; //右子树
updateHeight(root);
if(getBalanceFactor(root)==-2){
if(getBalanceFactor(root.right)==-1){
//RR型
LRotation(root);
}
else{
RRotation(root.right);
LRotation(root);
}
}
}
} 只要把最靠近插入节点的失衡及节点调整到正常，路径上的所有节点就会平衡。
哈弗曼树
叶子节点的路径长度是指从根节点出发到达该节点所经过的边数，叶子节点的权值乘以其路径长度等于节点的带权路径长度。树的带权路径长度WPL等于它所有叶子绩点的戴荃路径长度和。
对同一组叶子节点来说，哈夫曼树可以是不唯一的，但是最小带权路径长度一定唯一。
private void HafTree(int[] arr, int n){
int x,y,ans=0;
PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
for(int i=0;i<n;i++){
priorityQueue.add(arr[i]);
}
while(priorityQueue.size()>1){
x=priorityQueue.poll();
y=priorityQueue.poll();
priorityQueue.add(x+y);
ans+=x+y;
}
} 哈夫曼编码是能使给定字符串编码成01串长度最短的前缀编码。
最小生成树
最小生成树是在一个给定的无向图G(V,E)中求一棵树T，使得这个数的边权之和最小。
1) 最小生成树是树，其边数等于顶点数减1，且树内一定不会有环；
2) 对于给定的图G(V,E)，其最小生成树可以不唯一，但其边权之和一定唯一。
3) 由于最小生成树在无向图上生成，则根节点可以是这棵树上任意节点。一般会指定根节点，求解。
prim算法
对图G(V,E)设置集合S，存放已被访问的顶点，然后每次从集合V-S的最短距离最小的一个顶点u，访问并加入集合S，令顶点u为中介点，优化所有从u能到达的顶点v与==集合S==之间的最短距离，这样操作执行n次，直到集合S已包含所有的顶点。与Dijkstra算法相比，将起点s改为集合S。
int n; int[][] G=new int[MAXV][MAXV]; boolean[] vis=new boolean[MAXV]; int[] d=new int[MAXV]; //与集合S的距离 private int prime(){ for(int i=0;i<n;i++)d[i]=INF; d[0]=0; //从0号顶点开始 int ans=0; //边权和 for(int i=0;i<n;i++){ int u=-1,MIN=INF; for(int j=0;j<n;j++){ //找到未访问中最小的 if(!vis[i]&&d[j]<MIN){ MIN=d[j]; u=-1; } } if(u==-1)return -1; //找不到 vis[u]=true; ans+=d[u]; //距离集合S距离最小边加入最小生成树 for(int v=0;v<n;v++){ if(!vis[v]&&G[u][v]!=INF&&d[v]>G[u][v])d[v]=G[u][v]; //将G[u][v]赋值给d[v] } } }kruskal算法
每次选择图中最小边权的边，如果边两端点的顶点在不同连通块中，就把这条边加入最小生成树。
1) 如何判断测试边的两个端点在不同的连通块。
2) 如何将测试边加入最小生成树。
int[] father=new int[N]; //并查集数组 ArrayList<edge> arrayList=new ArrayList<>(); private int kruskal(int n, int m){ //n个顶点，m为图的边数 int ans=0,numEdge=0; //numEdge为当前生成树的边数 for(int i=1;i<=n;i++){ father[i]=i; //并查集初始化 } //所有边按边权排序,从小到大 arrayList.sort(new Comparator<edge>() { @Override public int compare(edge o1, edge o2) { return o1.cost-o2.cost; } }); //枚举所有边 for(int i=0;i<m;i++){ int faU=findFather(arrayList.get(i).u); int faV=findFather(arrayList.get(i).V); if(faU!=faV){//如果不在同一个集合中 father[faU]=faV; //合并集合 ans+=arrayList.get(i).cost; numEdge++; if(numEdge==n-1)break; } } if(numEdge!=n-1)return -1; //无法连通 else return ans; }时间复杂度为O(ElogE)，E为边数。kruskal适合顶点数较多，边数较少，与prim算法相反。即稠密图用prim算法，稀疏图用kruskal算法。
并查集
1) 合并：合并两个集合。
2) 查找： 判断两个元素是否在同一集合。
查找：
//返回元素x所在集合的根节点
private findFather(int x){
while(x!=father[x])x=father[x];
return x;
} 合并两个集合：
private void Union(int a, int b)
{
int faA=findFather(a);
int faB=findFather(b);
if(faA!=faB)father[faA]=faB; //合并
} 路径压缩
将当前查询节点的路径上的所有节点的父亲都指向根节点。
1) 获得x的根节点x。
2) 重新从x开始走一遍寻找根节点的过程，将路径上经过的所有父亲节点全部指向根节点r.
private int findFather(int v){
if(v==father[v])return v; //找到根节点
else{
int F=findFather(father[v]); //递归寻找到根节点F
father[v]=F;
return F; //返回根节点F
}
} 路径压缩后查询效率为O(1)。
堆
堆是一颗完全二叉树，树中每个节点的值都不大于（不小于）其左右孩子节点的值。分为大顶堆和小顶堆。堆一般用于优先队列的实现。
向下调整：将当前节点V与他的左右孩子节点比较，假如孩子节点的权值比节点V的权值答大，就交换；交换完毕后让节点V和孩子比较，直到节点V的孩子权值都比节点V的权值小或是无孩子节点。
int maxn=100;
int[] heap=new int[maxn];
int n=10; //n为元素个数
private downAdjust(int low,int hight)
{
int i=low,j=i*2; //j为i的左孩子
while(j<=high){
if(j+1<=high&&heap[j+1]>heap[j])j=j+1;
if(heap[j]>heap[i]){
int temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
i=j;
j=i*2;
}
else{
break; //调整结束
}
}
} 建堆：
完全二叉树叶子节点个数为[n/2]，因此数组下标在[1,n/2]范围内的都是非叶子节点。可以从[n/2]号位倒着枚举节点。这样能保证每个节点都是以其为根节点的子树中权值最大的节点。
void createHeap(){
for(int i=n/2;i>=1;i--)downAdjust(i,n);
} 时间复杂度为O(n)。
删除堆顶元素：
void delete(){
heap[1]=heap[n--]; //覆盖堆顶元素
downAdjust(1,n); //向下调整
} 时间复杂度O(logn)。
添加元素：
void upAdjust(int low, int high){
int i=high,j=i/2; //j为其父亲
while(j>=low){
if(heap[j]<heap[i]){
int temp=heap[j];
heap[j]=heap[i];
heap[i]=temp;
i=j;
j=i/2;
}
else{
break; //调整结束
}
}
}
void insert(int x)
{
heap[++n]=x;
upAdjust(1,n);
} 时间复杂度为O(logn)。
动态规划
一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划区解决。
1) 分治与动态规划。分治法分解出的子问题是不重叠的，如归并排序和快速排序都是分别处理其左右序列。
2) 贪心与动态规划。贪心法计算方式类似于自定向下，并不等待子问题求解完毕再去决定使用哪一个，而是通过一种策略直接去选择一个子问题求解，没被选择的则直接抛弃，总在上一步选择的基础上继续选择，这种所谓的最优选择的正确性需要证明。而动态规划则是自底向上或者自顶向下都是从边界问题开始向上求得目标问题的最优解。
数塔问题
import java.util.*;
public static void main(String[] args){
int maxn=100;
int[][] f=new int[maxn][maxn];
int[][] dp=new int[maxn][maxn];
int n=10;
Scanner sc=new Scanner(System.in);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j]=sc.nextInt(); //输入数塔
}
}
//边界
for(int j=1;j<=n;j++)dp[n][j]=f[n][j];
//从n-1层向上计算
for(int i=n-1;i>=1;--i){
for(int j=1;j<=i;++j){
//状态转移方程
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
}
}
System.out.println(dp[1][1]); //答案
} 使用递推是自底向上，使用递归是自顶向下。
最大连续子序列
给定一个数字序列A1,A2,....An,求i,j上的Ai+....+Aj最大，输出最大和。
1) 令状态dp[i]表示以A[i]结尾的连续序列最大和
2)状态转移方程dp[i]=max(A[i],dp[i-1]+A[i]),边界dp[0]=A[0]
private int findLargeSequence(int[] arr, int n)
{
int[] dp=new int[n];
dp[0]=arr[0];
for(int i=1;i<n;i++){
dp[i]=max(A[i],dp[i-1]+A[i]);
}
int k=0;
for(int i=1;i<n;++i)if(dp[i]>dp[k])k=i;
return dp[k];
} 状态的无后性：当前记录了历史信息，一旦当前状态确定，就不会改变，且未来决策只能在已有的一个或若干个状态的基础上运行，历史信息只能通过已有的状态去影响未来的决策。
最长不下降子序列
在一个数字序列中，找到一个最长的子序列使得这个子序列是非递减的。
令dp[i]表示以A[i]即为的最长不下降序列长度和：
1) 存在A[i]之前的元素j使得A[j]<=A[i]，则dp[i]=dp[j]+1;
2) 不存在，则这个子序列中只有A[i]，即dp[i]=1。
状态转移方程： dp[i]=max{1,dp[j]+1},(j=1,2,...,i-1&&A[j]<A[i])
边界条件dp[i]=1(1<=i<=n)。
private int findSequence(int[] arr, int n)
{
int ans=-1;
for(int i=1;i<=n;i++){
dp[i]=1; //初始边界条件
for(int j=1;j<i;j++){
if(A[i]>=A[j]&&(dp[j]+1>dp[i]))dp[i]=dp[j]+1;
}
ans=max(ans,dp[i]);
}
} 最长公共子序列
给定两个字符串A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）。
令dp[i] [j]表字符串A的i号位和字符串B的j号位之前的最长公共子序列的长度：
1) 若A[i]==B[j]则dp[i] [j]=dp[i-1] [j-1]+1;
2) 若A[i]!=B[j]，dp[i] [j]=max{dp[i-1] [j], dp[i] [j-1]}。
边界dp[i] [0]=dp[0] [j]=0(0≤i≤n,0≤j≤m)。
private int findLargestCommonSequence(char[] A, char[] B, int n, int m )
{
int[][] dp=new dp[n+1][m+1];
//边界
for(int i=0;i<=n;i++)dp[i][0]=0;
for(int j=0;j<=m;j++)dp[0][j]=0;
//状态转移方程
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(A[i]==B[j])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[n][m];
} 最长回文子串
给定一个字符串S，求S的最长回文子串长度。
令dp[i] [j]表示S[i]到S[j]所表示的子串是否为回文子串，若是则为1，否则为0：
1) 若S[i]==S[j]，则只要S[i+1]至S[j-1]是回文串，S[i]至S[j]就是；
2)若S[i]!=S[j]，那么S[i]至S[j]不是。
边界dp[i] [i]=1，dp[i] [i+1]=(S[i]==S[i+1])?1:0;
private int find Sequence(char[] S, int n)
{
int ans=1;
int[][] dp=new int[n][n];
//边界
for(int i=0;i<n;i++){
dp[i][i]=1;
if(i<n-1){
if(S[i]==S[i+1]){
dp[i][i+1]=1;
ans=2;
}
}
}
//状态转移方程
for(int L=3;L<=n;L++){
for(int i=0;i+L-1<n;i++){
int j=i+L-1;
if(S[i]==S[j]&&dp[i+1][j-1]==1){
dp[i][j]=1;
ans=L;
}
}
}
} 背包问题
多阶段动态规划问题：每个阶段的状态只和上一个阶段状态有关。
01背包问题
有n件物品，每件物品重量为w[i]，价值为c[i]。现有一个容量为V的背包，选择物品使背包内物品总价值最大。每种物品都只有一件。
暴力枚举的时间复杂度为O(2^n^)，动态规划则是O(nV)。
令dp[i] [v]表示将前i件物品放入v容量背包获得的最大价值：
1) 不放入第i件物品，那么问题变为求解dp[i-1] [v];
2) 放入第i件物品，转化为dp[i-1] [v-w[i]]+c[i].
枚举i从1到n,v从0到V，边界条件dp[0] [v]=0(0≤v≤V)。dp[n] [v]中最大值即为结果。
for(int i=1;i<=n;i++){ for(int v=w[i];v<=V;v++){ dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]); } }由于计算dp[i] [v]只用到了其左上方的数据和正上方的数据，因此可以开一个一维数组，令i从1到n枚举，令v从从V到0枚举，这样每计算一个dp[i] [v]相当于把dp[i-1] [v]抹消。这种技巧又称为滚动数组。
private int getPackageMaxValue(int[] arr, int n, int V) { int[] dp=new int[V+1]; //边界 for(int v=0;v<=V;v++)dp[v]=0; //状态转移方程 for(int i=1;i<=n;i++) { for(int v=V;v>=w[i];v--)dp[v]=max(dp[v],dp[v-w[i]]+c[i]); } //寻找最大答案 int max=0; for(int v=0;v<=V;v++)if(dp[v]>max)max=dp[v]; return max; }对能够划分阶段的问题来说，都可以尝试把阶段作为状态的一维，这样更方便的得到满足无后效性。如果当前设计的状态不满足无后效性，那么不妨将状态进行升维，即增加一维或若干维来表示相应的信息，这样就可能满足无后效性了。
完全背包问题
每种物品都有无穷件。
状态转移方程：
dp[i] [v]=max(dp[i-1] [v],dp[i] [v-w[i]]+c[i]).
改写成一维：
dp[v]=max(dp[v],dp[v-w[i]]+c[i]),(1≤i≤n,w[i]≤v≤V)。
边界dp[v]=0(0≤v≤V)。
for(int i=1;i<=n;i++){ for(int v=w[i],v<=V;v++)dp[v]=max(dp[v],dp[v-w[i]]+c[i]); }
DAG最长路
令dp[i]表示从i点点出发能获得的最长路径长度，这样dp[i]的最大值就是整个DAG的最长路径长度。如果从i号顶点出发能直接到达顶点j1、j2、....、jk，而dp[j1]、dp[j2]等均一致，那么dp[i]=max{dp[j]+length[i->j]}。
由于从出度为0的顶点出发的最长路径的长度为0，因此边界为这些顶点的dp值为0，具体实现中，不妨对整个dp数组初始化为0。
为了求解最长路径，设置choice数组记录最长路径上顶点的后继顶点。
int DP(int i){
if(dp[i]>0)return dp[i]; //dp[i]已经计算到
for(int j=0;j<n;j++){
if(G[i][j]!=INF){
int temp=DP(j)+G[i][j]; //单独计算
if(temp>dp[i]){
dp[i]=temp;
choice[i]=j; //i号顶点后继顶点为j
}
}
}
return dp[i];
}
//调用前，需要先得到最大的dp[i]，然后将i作为起点传入
void printPath(int i){
System.out.println(i);
while(choice[i]!=-1){
i=choice[i];
System.out.println(i);
}
} 固定终点，求DAG的最长路径：
令dp[i]表示从i号顶点出发到达终点T所能获得最长路径长度。将dp数组初始化为一个负大数，来保证“无法到达终点”；然后设置一个vis数组表示顶点是否被计算。
int DP(int i){
if(vis[i])return dp[i]; //已经计算到
vis[i]=true;
for(int j=0;j<n;j++){
if(G[u][j]!=INF){
dp[i]=max(dp[i],DP(j)+G[i][j]);
}
}
return dp[i];
} 矩形嵌套问题：将每个矩形都堪称一个顶点，并将嵌套关系视为顶点之间的有向边，边权为1，于是转换为DAG的最长路径。
图
图的定义
1) 图分为有向图和无向图。
2)顶点的度是指和该顶点相连的边的条数。对有向图来说，分为入度和出度。
3) 顶点和边的权值分别称为点权和边权。
图的存储： 邻接矩阵和邻接表。
邻接矩阵：二维数组G[i] [j]表示顶点i和j之间有边，可以表示权值，是一个对称矩阵。
邻接表： 顶点的出边对应的列表，可用列表实现。
图的遍历
DFS
连通分量：在无向图中，如果两个顶点之间可以相互到达，就成为这两个顶点连通。如果图G(V,E)任意两个顶点都连通，则称图G为连通图；否则称为非连通图，且其中极大连通子图为连通分量。
强连通分量：针对有向图。
final int MAXV=1000; final int INF=100000; int n; int[][] G=new int[MAXV][MAXV]; boolean[] vis=new boolean[MAXV]; private void DFS(int u, int depth){ //u为当前访问顶点标号,depth为深度 vis[u]=true; //已被访问 for(int v=0;v<n;v++) { if(!vis[v]&&G[u][v]!=INF){ //v未被访问，且u可以到达v DFS(v,depth+1); //深度加1 } } } private void DFSTrave(){ for(int u=0;u<n;u++){ if(!vis[u])DFS(u,1); } }对于邻接表，
ArrayList<ArrayList<Integer>> Adj=new ArrayList<>(); int n; //顶点数 boolean[] vis=new boolean[MAXV]; private void DFS(int u, int depth) { vis[u]=true; for(int i=0;i<Adj.get(u).size();i++){ int v=Adj.get(u).get(i); if(!vis[v])DFS(v,depth+1); } }BFS
class GraphNode{ int val; int layer; public GraphNode(int val, int layer){ this.val=val; this.layer=layer; } public GraphNode(){} } boolean[] inq=new boolean[MAXV]; ArrayList<ArrayList<GraphNode>> Adj=new ArrayList<>(); private void BFS(int s){ //s为起点编号 Deque<GraphNode> deque=new LinkedList<>(); GraphNode node=new GraphNode(s,0); //起始顶点层号为0 deque.addLast(node); inq[s]=true; //顶点已被访问 while(!deque.isEmpty()){ GraphNode temp=deque.pollFirst(); int u=temp.val; //队首顶点编号 for(int i=0;i<Adj.get(u).size();i++){ GraphNode next=Adj.get(u).get(i); //从u出发能达到的顶点数 next.layer=temp.layer+1; //层数加1 if(!inq[next.val]){ deque.addLast(next); inq[next.val]=true; } } }
最短路径
给定图G(V,E)，求一条从起点到终点的路径，使得这条路径上经过的所有边的边权之和最小。
Dijkstra算法
解决单源最短路问题。G(V,E)设置集合S，存放被访问的顶点，每次从未被访问的顶点中选择与起点s的最短距离最小的一个顶点，访问并加入S(记为u)，令顶点u为中介点，优化起点s与所有从u能达到的顶点v的最短距离。这样执行n次(n为顶点个数)，直至集合S包含所有顶点。
邻接矩阵实现：
final int MAXV=1000; //最大顶点数 final int INF=10000000; //INF为一个很大的数 int n; //顶点数 int[][] G=new int[MAXV][MAXV]; //图 boolean[] vis=new boolean[MAXV]; //标记数组 int[] d=new int[MAXV]; //起点到达各点的最短路径长度 private void Dijistra(int s){ //s为起点 //对d数组进行初始化赋值 for(int i=0;i<n;i++)d[i]=INF; d[s]=0; //起点到达自身距离为0 for(int i=0;i<n;i++){ //循环n次 int u=-1,MIN=INF; //u是使d[u]最小的下标，MIN存放d[u]值 for(int j=0;j<n;j++){ //寻找未访问的d[]最小的 if(!vis[j]&&d[j]<d[u]){ u=j; MIN=d[j]; } } if(u==-1)return; //找不到，说明剩下顶点与起点不连通 vis[u]=true; //标记u已经被访问 //以u为中介点，更新距离值 for(int v=0;v<n;v++){ if(!vis[v]&&G[u][v]!=INF&&d[u]+G[u][v]<d[v])d[v]=d[u]+G[u][v]; } } }时间复杂度O(V^2^)。
邻接表如下：
class Node{ int v; int dis; //v为目标顶点,dis为边权 } ArrayList<ArrayList<Node>> Adj=new ArrayList<>(); //从顶点u出发所能达到的顶点 private void Dijkstra(int s){ for(int i=0;i<n;i++)d[i]=INF; d[s]=0; for(int i=0;i<n;i++){ int u=-1,MIN=INF; for(int j=0;j<n;j++){ if(!vis[j]&&d[j]<MIN){ u=j; MIN=d[j]; } } if(u==-1)return; vis[u]=true; //优化 for(int j=0;j<Adj.get(u).size();j++){ int v=Adj.get(u).get(j); if(!vis[v]&&d[v]<d[u]+Adj.get(u).get(j).dis)d[v]=d[u]+Adj.get(u).get(j).dis; } } }记录最短路径：设置数组pre[v]表示从s到v的最短路径上v的前一个顶点的编号。
//在优化是增加下面语句 pre[v]=u; //输出最短路径上的节点 void DFS(int s, int v){ if(s==v){ System.out.println(s); return; } DFS(s,pre[v]); System.out.println(v); }在实际题目中，可能会有多条最短路径，第一标尺是距离，会给出第二标尺：
1)新增边权。如花费，cost[u] [v]表示u到v的花费，并增加一个素组c[i]，令从起点到达顶点u的最少花费为c[u]，初始是c[s]为0，其他c[u]均为INF。这样，当最短距离相同时，同样需要更新花费c[u]+cost[u] [v]<c[v]。
for(int v=0;v<n;v++){ if(!vis[v]&&G[u][v]!=INF){ if(d[u]+G[u][v]<d[v]){ d[v]=d[u]+G[u][v]; c[v]=c[u]+cost[u][v]; }else if(d[u]+G[u][v]=d[v]&&c[u]+cost[u][v]<c[v]){ c[v]=cost[u][v]+c[u]; } } }2) 新增点权。如能收集到的物资，用weight[u]表示城市[u]能搜集到的物资，增加一个数组w[]，令从起点s到达顶点u可以搜集到的最大物资为w[u]。这样，当距离相同时，w[u]+weight[v]>w[v]时更新w[v]。
3)求最短路径条数。增加一个数组num[]，令从起点s到达顶点u的最短路径条数为num[u]。初始化时num[s]为1，其余num[u]均为0。这样，更新时num[v]继承num[u]，距离相同时，num[v]+=num[u]。
Bellman-Ford算法和SPFA算法
Bellman-Ford：对图进行V-1操作，每次遍历图中所有边，对每条u到v的边，如果以u为中介点可以使得d[v]更小，就更新d[v]。再对所有边进行一***作，判断是否有某条u到v的边仍然满足hds[u]+G[u] [v]<d[v]，如果有，则说明图中有从源点可达的负环，返回false；否则说明数组d中所有值达到最优返回true。时间复杂度O(VE)。
若使用邻接矩阵，则算法复杂度会上升到O(V^3^)。
class Node{ int v; int dis; //v为目标顶点,dis为边权 } ArrayList<ArrayList<Node>> Adj=new ArrayList<>(); //从顶点u出发所能达到的顶点 int n; int[] d=new int[MAXN]; //起点到达各点的最短路径长度 private boolean Bellman(int s){ for(int i=0;i<n;i++)d[i]=INF; d[s]=0; //起点s到达自身距离为0 for(int i=0;i<n-1;i++){ //执行n-1操作，n为顶点数 for(int u=0;u<n;u++){ for(int j=0;j<Adj.get[u].size();j++){ int v=Adj.get(u).get(j).v; //邻接边的顶点 int dis=Adj.get(u).get(j).dis; //邻接边的边权 if(d[u]+dis<d[v]){ //以u为中介点 d[v]=d[u]+dis; //松弛操作 } } } } //判断负环代码 for(int u=0;u<n;u++){ for(int j=0;j<Adj.get(u).size();j++){ int v=Adj.get(u).get(j).v; int dis=Adj.get(u).get(j).dis; if(d[u]+dis<d[v]){ return false; } } } return true; //所有值都达到最优 }在进行某一***作时，发现所有边都没有被松弛，那么说明d中已经达到最优，不需要继续，提前退出即可。
在统计最短路径条数是：由于Bellman算***多次访问曾经访问过的节点需要设置记录前驱的数组set< int> pre[MAXV]，当遇到路径相同长度时，重新计算最短路径长度。
SPFA: 只有当某个顶点u的d[u]值改变时，从它出发的邻接点v的d[v]值才可能改变。因此，建立一个队列，每次将队首顶点u取出，然后对从u出发的所有u到v的边进行松弛操作，取得最优值，此时如果v不在队列中，就加入队列。这样知道队列为空（没有负环）或者某个顶点的入队次数超过V-1（存在从源点可达负环）。期望时复杂度为O(kE)，k是一个常数，很多时候不超过2，如果存在负环，则会退化为0(VE)。
ArrayList<ArrayList<Node>> Adj=new ArrayList<>(); //从顶点u出发所能达到的顶点 int n; int[] d=new int[MAXN]; //起点到达各点的最短路径长度 boolean[] inq=new boolean[MAXN]; int[] num=new int[MAXN]; //记录顶点入队次数 private boolean SPFA(int s){ //源点 for(int i=0;i<n;i++)d[i]=INF; for(int i=0;i<n;i++)num[i]=0; d[s]=0; //起点s到达自身距离为0 //源点入队 Deque<Integer> deque=new LinkedList<>(); deque.addLast(s); inq[s]=true; num[s]++; //源点入队次数加1 while(!deque.isEmpty()){ int u=deque.pollFirst(); //队首顶点编号 inq[s]=false; //不在队列中 for(int j=0;j<Adj.get(u).size();j++){ int v=Adj.get(u).get(j).v; int dis=Adj.get(u).get(j).dis; if(d[u]+dis<d[v]){ d[v]=d[u]+dis; if(!inq[v]){ //v不在队列中 deque.addLast(v); num[v]++; inq[v]=true; if(num[v]>=n)return false; } } } } return true; }Floyd算法
解决全源最短路问题，即对任意给定的图G(V,E)，求任意两点u,v之间的最短路径长度，时间复杂度0(n^3^)，一般顶点数限制在200内，使用邻接矩阵。
如果存在顶点k,使得k作为中介点时i和j顶点的当前距离缩短，则使用k作为中介点，即dis[i] [k]+dis[k] [j]<dis[i] [j]。
int n,m; //n为顶点数,m为边数 int[][] dis=new int[MAXV][MAXV]; //dis[i][j]表示顶点i和顶点j的距离 private void Floyd() { for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j]){ dis[i][j]=dis[i][k]+dis[k][j]; } } } } }
拓扑排序
拓扑排序是将有向无环图所有顶点排成一个线性序列，使得对图G中的任意两个顶点u,v，如果存在u到v的百年，那么序列u一定在v前面。这个序列又被称为拓扑序列。
1) 定义一个队列Q，将所有入度为0的度加入队列；
2) 取队首节点，输出。删除从它所触发的边，并令到达这些边的顶点的入度减1。如果某个顶点入度为0，则将其加入队列。
3) 反复进行2)操作，直到队列为空。如果队列为空时入过队的节点数目刚好为N，说明拓扑排序成功，则图G为有向无环图，否则，拓扑排序失败，图G中有环。
ArrayList<ArrayList<Integer>> G=new ArrayList<>(); //邻接表
int n,m;
int[] inDegree=new int[MAXV]; //入度
private bool topologicalSort(){
int num=0; //记录加入拓扑排序序列的顶点数
Deque<Integer> deque=new LinkedList<>();
for(int i=0;i<n;i++){
if(inDegree[i]==0)deque.addLast(i);
}
while(!deque.isEmpty()){
int u=deque.pollFirst();
System.out.println(u);
for(int i=0;i<arrayList.get(u).size();i++){
int v=arrayList.get(u).get(i).v; //u的后继节点v
inDegree[v]--; //顶点v入度减1
if(inDegree[v]==0)deque.addLast(v);
}
num++;
}
if(num==n)return true;
else return false; //拓扑排序失败
} 如果要求多个入度为0的顶点，选择编号最小的顶点，将queue改为priority_queue即可。
关键路径
AOV网：顶点表示活动，边集表示活动间优先关系的有向图。
AOE网：带权的边集表示活动，用顶点表示事件的有向图。
AOV和AOE均是有向无环图。
AOE网中的最长路径称为关键路径，关键路径上的活动称为关键活动。
事件Vi在经过活动ar之后到达事件Vj，设置数组e[r]和l[r]表示活动ar的最早开始时间和最迟开始时间。设置数组ve[i]和vl[i]表示事件i的最早开始时间和最迟发生时间。这样：
1) 对活动ar来说，e[r]=ve[i];
2)如果l[r]是时间的最晚发生时间，则l[r]=vl[j]-length[r]。
求解ve[i],
Deque<Integer> topOrder=new LinkedList<>(); //存储拓扑序列
class Node{
int v; //顶点
int w; //时间
}
ArrayList<ArrayList<Node>> arrayList=new ArrayList<>();
private bool topologicalSort(){
Deque<Integer> deque=new LinkedList<>();
for(int i=0;i<n;i++){
if(inDeque[i]==0)deque.addLast(i);
}
while(!deque.isEmpty()){
int u=deque.pollFirst();
topOrder.addLast(u); //将u加入拓扑序列
for(int i=0;i<arrayList.get(u).size();i++){
int v=arrayList.get(u).get(i).v; //u的后继节点v
inDegree[v]--; //顶点v入度减1
if(inDegree[v]==0)deque.addLast(v);
if(ve[u]+arrayList.get(u).get(i).w>ve[v])ve[v]=ve[u]+arrayList.get(u).get(i).w;
}
}
if(topOrder.size()==n)return true;
else return false; //拓扑排序失败
} 求解vl数组，以下代码添加上：
for(int i=0;i<n;i++)vl[i]=ve[n-1]; //vl初始化，初始值为终点ve值
//对topOrder出栈即为逆拓扑序列
while(!topOrder.isEmpty()){
int u=topOrder.pollFirst();
for(int i=0;i<arrayList.get(u).size();i++){
int v=arrayList.get(u).get(i).v; //u的后继结点v
if(vl[v]-arrayList.get(u).get(i).w<vl[u])vl[u]=vl[v]-arrayList.get(u).get(i).w;
}
} 上面的步骤，即“先求点，在夹边”
int CriticalPath(){
for(int i=0;i<n;i++)ve[i]=0; //ve数组初始化
if(!toplogicalSort())return -1;
//遍历邻接表所有边，计算e和l
for(int u=0;u<n;u++){
for(int i=0;i<arrayList.get(u).size();i++){
int v=arrayList.get(u).get(i).v;
int w=arrayList.get(u).get(i).w;
int e=ve[u];
int l=vl[v]-w;
if(e==l)System.out.println(u+"->"+v); //输出关键活动
}
}
return ve[n-1]; //返回关键路径长度
} 对于一个没有正环的图（从源点可达的正环），如果需要求最长路径长度，则可以将所有边乘以-1，然后用Bellman-Ford算法或SPFA算法求最短路径长度。
专题扩展
分块思想
给出一个栈的入栈出栈过程，并能输出栈中中间大小的数。
final int maxn=100010;
final int sqrN=316; //sqrt(100001)
Deque<Integer> s=new LinkedList<>(); //栈
int[] block=new int[sqrtN]; //基于每一块中存在的元素元素个数
int[] table=new int[maxn]; //记录元素当前存在个数
void peekMedian(int K){
int sum=0; //当前累计个数
int idx=0; //块号
while(sum+=block[idx++]<K);
int num=(idx-1)*sqrN; //idx块第一个数
while(sum+=table[num++]<K);
System.out.println(num); //找到
}
void push(int x){
s.addLast(x); //入栈
block[x/sqrN]++;
table[x]++;
}
void pop(){
int x=s.pollLast();
block[x/sqrtN]--;
table[x]--;
} 对于N次查询，时间复杂度为O(Nsqrt(N))。
树状数组
lowbit(x)=x&-x;表示取二进制x最右边的1和它右边的0，也即能整除x的最大2幂次。
树状数组存放的是i号位之前lowbit(i)个整数之和，C[i]数组下标从1开始
1) getSum(x)返回前x个数之和
int getSum(int x){ int sum=0; for(int i=x;i>0;i-=lowbit(i)){ sum+=c[i] } return sum; }getSum时间复杂度为O(logN)。
2)update(x,v)，将第i个数加上一个数v
void update(int x, int v){ for(int i=1;i<=N;i+=lowbit(i)){ c[i]+=v; }时间复杂度为0(logN)。
给定一个N个整数的序列A，对序列中每一个数，求出序列中的左边比它小的数的个数。
for(int i=0;i<n;i++){ update(arr[i],1); //出现次数加1，x=arr[i] getSum(x-1); //查询当前小于x的数的个数 }
KMP算法
暴力法时间复杂度为O(nm)，KMP算法时间复杂度为O(m+n)。
next数组
next[i]就是子串s[0...i]中最长相等前后缀的前缀的最后一位下标（前缀跟后缀可以部分重叠，但不能是子串之身）。
1)初始化next数组，令j=next[0]=-1;
2)让i在1~len-1范围遍历，对每个i，执行3)4)，以求解next[i]；
3不断令j=next[i]，直到j回退-1或是s[i]==s[j+1]成立；
4)若是s[i]==s[j+1]，则next[i]=j+1，否则next[i]=j。
void getNext(char[] s,int len){ int j=-1; next[0]=-1; for(int i=1;i<len;i++){ while(j!=-1&&s[i]!=s[j+1])j=next[j]; if(s[i]==s[j+1])j++; next[i]=j; //令next[i]=j; } }KMP算法
boolean KMP(char[] text, char[] pattern,int n, int m){ getNext(pattern,m); //计算pattern的数组 int j=-1; //初始化j为-1表示当前还没有任意一位匹配 for(int i=0;i<n;i++){ //试图匹配text[i] while(j!=-1&&text[i]!=pattern[j+1]){ j=next[j]; } if(text[i]==pattern[j+i]){ j++; } if(j==m-1)return true; //完全匹配 } return false; }求解next数组的过程就是模式串pattern进行自我匹配的过程。
统计模式串pattern出现次数：
int KMP(char[] text, char[] pattern,int n, int m){ getNext(pattern,m); //计算pattern的数组 int j=-1; //初始化j为-1表示当前还没有任意一位匹配 int ans=0; for(int i=0;i<n;i++){ //试图匹配text[i] while(j!=-1&&text[i]!=pattern[j+1]){ j=next[j]; } if(text[i]==pattern[j+i]){ j++; } if(j==m-1){ ans++; //成功匹配次数加1 j=next[j]; //继续匹配 } } return ans; }优化：nextval[i]表示当模式串pattern的i+1位发生失配时，i应该回到的位置。
void getNextVal(char[] s, int len){ int j=-1; nextval[0]=-1; for(int i=1;i<len;i++){ while(j!=-1&&s[i]!=s[j+1]){ j=nextval[j]; } if(s[i]==s[j+1]){ j++; } if(j==-1||s[i+1]!=s[j+1]){ //j==-1不需要回退 nextval[i]=j; }else{ nextval[i]=nextval[j]; } } }
投递谷歌等公司10个岗位 >