基础算法题的归纳总结
排序
常数操作：+-*/以及数组获取值（ps：链表获取不是常数操作）
简单排序
每次都找到最小值放置到对应的数组位置上即可
// 这里需要找n-1趟就可以了 因为最后一个默认已经到了最后的位置
for(int i = 0;i<arr.length-1;i++) {
int minIndex = i;
for(int j = i+1;j<arr.length;j++) {
minIndex = arr[minIndex] > arr[j] ? j : minIndex;
}
swap(arr,minIndex,i);
}
冒泡排序
先确定最大值，两两进行交互
for(int i = arr.length-1;i>0;i--) {
for(int j = 0;j<i;j++) {
if(arr[j] > arr[j+1]) {
swap(arr,j,j+1);
}
}
}
ps:这里的swap交换可以使用普通的交换方法，还可以使用异或来表示，因为异或具有交换律和结合律，0^N = N, N^N = 0 位运算是最快的
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
插入排序
下标0~0有序
下标0~1有序
…
每次都朝后扩展一个数进入到已经排好序的数组中，然后将其依次与前一个比较，如果小，则交换位置，否则停止
// 因为0~0已经是有序的了，所以直接从0~1开始
for(int i = 1;i<arr.length;i++) {
for(int j = i-1;j>=0 && arr[j]<arr[j+1];j--) {
swap(arr,j,j+1);
}
}
ps：插入排序与简单排序和冒泡排序的区别
前两种排序它们的过程与数据状态没有关系，每趟都会执行且时间复杂度固定，但是插入排序与数据状态有关，因此会区分最好时间复杂度和最坏时间复杂度
归并排序
先对数据进行划分，找到mid，找到左侧，找到右侧，然后递归这样的操作，将每一部分细化到只有一个数为止，然后对每两个小部分开始合并，合并时需要让其有序，这里建立一个辅助空间使其有序
// process这里主要是对L和R中的数据进行划分
public void process(int[] arr,int L,int R) {
// 停止递归的条件 当左侧和右侧都是一个数的时候
if(L == R) {
return;
}
int mid = L + ((R - L) >> 1);
process(arr,L,mid);
process(arr,mid+1,R);
merge(arr,L,mid,R);
}
// merge就是对当前分好的左右侧小块进行合并
public void merge(int[] arr,int L,int mid,int R) {
// 建立辅助空间
int[] help = new int[R-L+1];
int i = 0;
int p1 = L;
int p2 = mid+1;
while(p1 <= M && p2 <= R) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1<=M) {
help[i++] = arr[p1++];
}
while(p2<=R) {
help[i++] = arr[p2++];
}
// 将辅助空间内容拷贝到原数组中
for(int j = 0;j<help.length;j++) {
arr[j+L] = help[j];
}
}
归并时间复杂度计算：（采用递归的master计算公式）
时间复杂度：$O(N*logN)$ 空间复杂度：O(N)
快速排序
分治法，每一轮选择挑选一个基准元素，并让其它比它大的元素移动数列一边，比它小的移动到另外一边，从而将数列拆解成了两个部分。
public void quicksort(int[] arr,int L,int R) {
if(L<R) {
int index = (int)Math.random()*(R-L+1);
swap(arr,index,R);
int[] p = partition(arr,L,R);
quicksort(arr,L,p[0]-1);
quicksort(arr,p[1]+1,R);
}
}
public void partition(int[] arr,int L,int R) {
// less是小于区的下标界限
// more是大于区的下标界限
int less = L-1;
int more = R;
while(L<more) {
if(arr[L]<arr[R]) {
less++;
swap(arr,less,L);
L++;
}
else if(arr[L]>arr[R]) {
more--;
swap(arr,more,L);
}
else L++;
}
// 这里将arr[R]看作了基准，最后需要将最后一个数放置到他自己的位置上去，因此需要交换
swap(arr,more,R);
// 这里less指向小于区的末尾，所以+1才能跳转到=区，因为more与R进行了交换所以刚好是=区的末尾
return int[] {less+1,more};
}
堆排序
堆排序就是先建立大顶堆或者小顶堆 heapInsert的过程
然后交换堆顶和堆底的数值，然后跳转大顶堆或者小顶堆heapify的过程
public void heapSort(int[] arr) {
// 开始插入建立大顶堆
for(int i = 0;i<arr.length;i++) {
heapInsert(arr,i);
}
// 定义堆大小
int heapSize = arr.length;
// 第一次交换
swap(arr,0,--heapSize);
// 交换之后调整
while(heapSize > 0) {
heapify(arr,0,heapSize);
swap(arr,0,--heapSize);
}
}
// 插入大顶堆
public void heapInsert(int[] arr,int i) {
// 如果比自己的父节点大
while(arr[i]>arr[(i-1)/2]) {
swap(arr,i,(i-1)/2);
i = (i-1)/2;
}
}
// 开始调整
public void heapify(int[] arr,int i,int size) {
int left = 2 * i + 1;
while(left < size) {
int largest = left+1<size && arr[left+1] > arr[left] ? left+1 : left;
largest = arr[i] > arr[largest] ? i : largert;
if(largest == i) {
break
}
swap(arr,i,largest);
i = largest;
left = 2*i+1;
}
}
桶排序
自定义比较器：升序（o1- o2） 返回负数第一个参数会排在前面
不是基于比较的排序，而是需要根据状况来统计，排序过程中，位数不足的需要补齐，个位先排，然后依次出桶，然后十位排序，出桶。。。
总结
稳定性：同样值的个体之间，不因为排序而改变相对次序
不具备稳定性：选择、快排、堆
基础类型对稳定性要求不高，非基础类型对稳定性要求较高
| 时 | 空 | 稳 | |
|---|---|---|---|
| 选择 | $O(N^2)$ | $O(1)$ | × |
| 冒泡 | $O(N^2)$ | $O(1)$ | √ |
| 插入 | $O(N^2)$ | $O(1)$ | √ |
| 归并 | $O(NlogN)$ | $O(N)$ | √ |
| 快排 | $O(NlogN)$ | $O(logN)$ | × |
| 堆 | $O(NlogN)$ | $O(1)$ | × |
这里快排的空间复杂度为$O(logN)$，是因为虽然快排过程中没有开辟空间，但是使用了递归，递归会开辟栈
递归算法的空间复杂度 = 每次递归的空间复杂度$O(1)$*递归深度
递归时间复杂度
master公式：$T(N) = a*T(N/b) + O(N^d)$
对递归问题的时间复杂度计算
$a$：表示递归次数
$O(N^d)$：表示剩余所需的时间复杂度
最后整个时间复杂度为
$log_ba < d$ -> $O(N^d)$
$log_ba > d$ -> $O(N^(log_ba))$
$log_ba == d$ -> $O(N^d * logN)$
链表
链表涉及的题目都是练习coding，没有太多的算法部分，一般题型可能有
打印两个链表的公共有序部分（指针下标法）
判断一个链表是否是回文结构（栈、快慢指针+栈）
链表排序（申请辅助数组空间）
复制含有随机指针节点的链表（可以使用hashmap类型，保存老节点与新节点之间的地址）
两个单链表相交的一系列问题（涉及到判断每个链表是否有环）
二叉树
节点定义
class Node {
V value;
Node left;
Node right;
}
先序遍历（栈）
非递归
1、从栈中弹出一个节点
2、打印
3、右节点入栈
4、左节点入栈
后序遍历（栈）
双栈配合
第一个栈弹出，进入第二个栈，然后分别将弹出节点的左右节点放入第一个栈，依次循环
第二个栈就是需要的后序遍历的顺序，直接循环输出第二个栈即可
中序遍历（栈）
因为是左根右的打印顺序，故需要一直压入左节点然后头节点左节点头节点…如果没有左节点了，就需要转换到右节点即可
层次遍历（队列）
头节点进入队列，然后弹出，打印
弹出节点的左右节点进入队列
队列弹出，打印，然后将弹出节点的左右节点压入队列
获取二叉树最大宽度
层次遍历+hashmap（记录每个节点与它对应的层数）
判断是否是搜索二叉树
递归 （采用一个preValue记录当前节点的前一个节点值，如果curValue < preValue 则不是搜索二叉树）
搜索二叉树的左节点值都小于根节点，右节点值都大于根节点
还可以采用与判断是否是平衡二叉树一样的方法，调用树形递归方法
非递归
需要采用中序遍历的方法，因为中序刚好是左根右的顺序，判断是否是升序就可
判断是否是完全二叉树
层次遍历
1、任意节点有右孩子但是无左孩子 false
2、在遵守1的条件下，遇到了第一个左右孩子不全，后续的都是叶节点才行
采用一个flag表示遍历过程中是否遇到过左右两个孩子不双全的情况
判断是否是满二叉树
判断逻辑：深度为$l$，节点数为$N$，如果$N = 2^l-1$,那么它就是一颗满二叉树
递归分别得到左右子树的高度和node数，然后进行比较
判断是否是一颗平衡二叉树
左数与右树的高度差不能超过1
如果是一棵平衡二叉树的话，左子树是平衡的，右子树是平衡的，且$|左树高度 - 右树高度|<=1$
需要定义一种新的数据类型，在递归时可以使用，因为根据判断条件，需要得到左右子树是否是平衡的flag以及左右子树的高度。
于是递归调用判断函数即可
两棵二叉树节点的最低公共祖先节点
循环遍历方法
用hashMap来记录每个节点与它的父节点之间的映射
将一棵二叉树的节点往上查找的链放置到set1中
同样，遍历第二棵二叉树，查看该节点是否出现在了第一棵二叉树的set链中，如果出现了说明就是两个节点的最近公共祖先。
找出二叉树中一个节点的后继节点
这道题必须有某节点的父节点记录才行
这里的后继节点指的是中序遍历得到的顺序中该节点的下一个节点
情况1：
该节点有右子树时，它的下一个节点为右子树的最左的节点
情况2：
该节点没有右子树，如果它是父节点的左孩子，那么它的下一个节点就是它的父节点，如果它是父节点的有孩子，那么它的下一个节点就需要从父节点身上循环去找
情况3：
整棵树的最右节点没有后继节点
二叉树的序列化与反序列化
序列化：将二叉树先序遍历的结果用字符串的形式进行表示
先序遍历（递归）
反序列化：将字符串的形式表示转换为一棵二叉树
采用辅助空间队列，将字符串拆分成一个字符串数组放置在队列中，然后递归建立根节点，左节点，右节点即可
折纸问题
其实折纸问题类似于一棵二叉树，左子树的头节点都是凹，右子树的头节点都是凸，按照中序打印的方式可以得到正确的折痕顺序
图
数据结构
// 每个节点表示
class Node {
int value;
int in; // 入度
int out; // 出度
ArrayList<Node> nexts; // 邻接点
ArrayList<Edge> edges; // 邻接边
Node(value) {
this.value = value;
in = 0;
out = 0;
nexts = new ArrayList<>();
edges = new ArrayList<>();
}
}
// 每条边表示
class Edge {
int weight; // 边的权重
Node from; // 边的起始点
Node to; // 边的结束点
Edge(int weight,Node from,Node to) {
this.weigth = weight;
this.from = from;
this.to = to;
}
}
// 图的表示
class Graph {
HashMap<Integer,Node> nodes;
HashSet<Edge> edges;
Graph(){
nodes = new HashMap<>();
edges = new HashSet<>();
}
}
宽度优先遍历
类似于层次遍历，使用队列
将源节点入队列，弹出，然后将弹出节点的所有邻接节点入队列，循环这个过程
public void bfs(Node node) {
Queue<Node> queue = new LinkedList<>();
// 这里使用set主要是因为在遍历邻接节点时需要判断是否遍历过了
HashSet<Node> set = new HashSet<>();
queue.add(node);
set.add(node);
while(!queue.isEmpty()) {
Node temp = queue.poll();
System.out.println(temp.value);
for(Node cur: temp.nexts) {
// 说明未曾遍历过 是否遍历也可以使用一个boolean数组来表示该节点是否遍历过
if(!set.contains(cur)) {
queue.add(cur);
set.add(cur);
}
}
}
}
深度优先遍历
栈
从源节点开始将节点按照深度放入栈，然后弹出，每弹出一个节点，就把该节点未进过栈的邻接节点入栈，直到栈变空
public void dfs(Node node) {
Stack<Node> stack = new Stack<>();
HashSet<Node> set = new HashSet<>();
stack.add(node);
set.add(node);
System.out.println(node.value);
while(!stack.isEmpty()) {
Node cur = stack.pop();
for(Node next: cur.nexts) {
if(!set.contains(next)) {
stack.push(cur);
System.out.println(next.value);
stack.push(next);
set.add(next);
// 这里的break非常重要，可以直接跳出for循环，避免与宽度遍历一样一直找当前节点的邻接节点
break;
}
}
}
}
拓扑排序
每次找到一个入度为0的节点，打印，然后删除掉它的影响，继续找入度为0的节点，循环这个过程
public List<Node> sortTopology(Graph graph) {
// 保存每个节点的入度隐射
HashMap<Node,Integer> inMap = new HashMap<>();
// 保存入度是0的节点
Queue<Node> zeroInQueue = new LinkedList<>();
// 对上述数据进行初始化
for(Node cur: graph.nodes.values()) {
inMap.put(cur,cur.in);
if(cur.in == 0) {
zeroInQueue.add(cur);
}
}
// 开始拓扑排序 结果保存在result中
ArrayList<Node> result = new ArrayList<>();
while(!zeroInQueue.isEmpty()) {
Node cur = zeroInQueue.poll();
result.add(cur);
for(Node temp:cur.nexts) {
// 个人认为这里可以直接使用node.in的，但是最好不要在原来数据上修改in的值，所以
// 使用了hashMap来进行记录 使得图的原来的数据不变
inMap.put(temp,inMap.get(temp) - 1);
if(inMap.get(temp) == 0) {
zeroInQueue.add(temp);
}
}
}
return result;
}
最小生成树MST
K算法
prim算法 无向图
从图中任选一个点，然后挑选权重最小的边，然后再挑选与已选的点集有关边的最小权重边，循环，直到图连通
Dijkstra算法
最短路径问题
从图中某个顶点出发到达另外一个顶点所经过的边的权重和最小的一条路径，称为最短路径
解决算法
1、dijkstra算法 使用hashmap来记录某节点到其它节点的距离 使用set来记录已经选择过的节点
2、floyd算法
public HashMap<Node,Integer> dijkstra(Node node) {
// 记录其它节点到node的距离 如果没有保存说明它们之间的距离为正无穷
HashMap<Node,Integer> distanceMap = new HashMap<>();
// 记录已经更新的节点
HashSet<Node> selectedNode = new HashSet<>();
// 初始化
distanceMap.put(node,0);
// 获取
Node minNode = getNode(distanceMap,selectedNode);
while(minNode != null) {
// 找到最小点之后需要更新他周边的点距离
int dis = distanceMap.get(minNode);
for(Edge edge:minNode.edges) {
Node toNode = edge.to;
if(!distanceMap.containsKey(toNode)) {
distanceMap.put(toNode,dis+edge.weight);
selectedNode.add(toNode);
} else {
distanceMap.put(toNode,Math.min(dis+edge.weight,distanceMap.get(toNode)));
}
}
selectedNode.add(minNode);
minNode = getNode(distanceMap,selectedNode);
}
return distanceMap;
}
// 获取到distanceMap中路径最短的点
public Node getNode(HashMap<Node,Integer> distanceMap,HashSet<Node> seletedNode) {
Node minNode = null;
int minDis = Integer.MAX_VALUE;
for(Map.Entry<Node,Integer> entry:distanceMap.entrySet()) {
Node cur = entry.getKey();
int distance = entry.getValue();
if(distance < minDis && !seletedNode.contains(cur)) {
minNode = cur;
minDis = distance;
}
}
return minNode;
}
前缀树
数据结构
// 前缀树定义
class TrieNode {
int pass; // 表示该节点通过了多少次 || 将当前字符串作为前缀的数量
int end; // 多少个字符串的结尾节点 || 将当前字符串作为结尾的数量
TrieNode[] nexts;
TrieNode() {
pass = 0;
end = 0;
nexts = new TrieNode[26];
}
}
前缀树如果后期有使用到，再详细记录
贪心算法
优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫做贪心算法。
也就是说，不从整体最优上加以考虑，所作出的是在某种意义上的局部最优解。
会议室宣讲
有很多项目宣讲，知道每个项目的开始和结束时间，要求会议室进行的宣讲场次最多，返回最多的宣讲场次。
思路：结束时间早的先安排，需要自己编写自定义比较器，按照结束时间来对项目进行排序，遍历排序后的数组，如果开始时间<当前时间，则可以安排该项目。
金条分割问题
[10,20,30]将一块60的金条分割成数组所示的数值，但是切割的cost = 金条的value，如果切割使得cost最少。
使用小根堆 PriorityQueue数据结构，然后构建哈夫曼树，在构建过程中可以得到最小的cost
public int lessMoney(int[] arr) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int num: arr) {
pq.add(num);
}
// 构建哈夫曼树
int sum = 0;
while(pq.size()>1) {
int cur = pq.poll()+pq.poll();
sum += cur;
pq.add(cur);
}
return sum;
}
金条分割问题可以归类到最小分割问题，一般都可以使用建立哈夫曼树的过程解决（如何很好的使用小根堆）
获取项目最大利润
若干个项目，有自己的cost和profit，k表示最多能做的项目数量，m表示初始资金。
只能串行做项目，做完的项目收益可以当作初始资金投入到下一轮项目
思路：大小根堆的配合使用
小根堆（根据cost将项目排序，小根堆的项目是锁定的项目）
大根堆（如果项目的cost <= m，那么这些项目就可以解锁，从小根堆中移除，然后根据项目利润在大根堆中排序）然后m+=获得的利润，又可以解锁更多的项目，依次放入到大根堆中
// 表示一个项目的信息
class Program {
int profit;
int cost;
// 初始化
Program(int pro,int cos) {
this.profit = pro;
this.cost = cos;
}
}
// 建立大根堆比较器
class MaxProfitComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o2.profit - o1.profit;
}
}
// 建立小根堆比较器
class MinCostComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.cost - o2.cost;
}
}
public int findMaxCapital(int k,int m,int[] Profits,int[] Capital) {
PriorityQueue<Program> minq = new PriorityQueue<>(new MinCostComparator());
PriorityQueue<Program> maxq = new PriorityQueue<>(new MaxProfitComparator());
//将项目全部加入到小根堆中
for(int i = 0;i<Profits.length;i++) {
minq.add(new Program(Profits[i],Capital[i]));
}
// 开始解锁
// 因为只能做k个项目 所以有k轮，在每一轮中找到利润最大的
for(int j = 0;j<k;j++) {
while(!minq.isEmpty() && minq.peek().cost<=m){
maxq.add(minq.poll());
}
// 这里如果解锁后大根堆里仍然是空的，说明没有符合条件的项目，故返回初始资金即可
if(maxq.isEmpty()) {
return m;
}
m += maxq.poll().profit;
}
return m;
}
N皇后问题
如果n = 1，则只有一种放置的方法
如果n = 2或者3 则没有放置的方法
public int NQueens(int n) {
// record[i]表示在第i行放置皇后的列位置
int[] record = new int[n];
return process(0,record,n);
}
// 表示在第i行放置皇后
public int process(int i,int[] record,int n) {
// 如果已经来到了第n层，说明已经放置成功了一种
if(i == n) return 1;
// 否则需要在第0列-第n-1列进行尝试
int res = 0;
for(int j = 0;j<n;j++) {
// 判断第j列是否共列共斜线
if(isValid(record,i,j)) {
res += process(i+1,record,n);
}
}
return res;
}
public boolean isValid(int[] record,int i,int j) {
// 将前i-1行的位置分别与第i行的位置进行比较，看是否符合
for(int k = 0;k<i;k++) {
if(record[k] == j || Math.abs(record[k] - j) == Math.abs(k-i)) {
return false;
}
}
return true;
}
暴力递归
1、把问题转化为规模缩小了的同类问题的子问题
2、有递归停止的条件
3、不记录每一个子问题的解
汉诺塔问题
汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？
// 汉诺塔问题
public static void hano(int n) {
func(n,"左","右","中");
}
public static void func(int i,String start,String end,String other) {
if(i==1) {
System.out.println("Move 1 from "+start+" to "+end);
}else {
func(i-1,start,other,end);
System.out.println("Move "+i+" from "+start+" to "+end);
func(i-1,other,end,start);
}
}
打印字符串的全部子序列
举例abc（穷举法）
有a （有b （有c abc
（无c ab
（无b （有c ac
（无c a
无a（有b （有c bc
（无c b
（无b （有c c
（无c 空
// 来到i位置前，要和不要，走两条路
// res是之前的选择所形成的列表
public static void process(char[] str,int i,List<Character> res) {
if(i == str.length) {
printList(res);
return;
}
// 保留第i个字符
List<Character> resKeep = new ArrayList<>(res);
resKeep.add(str[i]);
process(str,i+1,resKeep);
// 不保留第i个字符
List<Character> resNotKeep = new ArrayList<>(res);
process(str,i+1,resNotKeep);
}
public static void printList(List<Character> res) {
String result = "";
for(Character c: res){
result += c;
}
if(result==""){
System.out.println("空");
return;
}
System.out.println(result);
}
打印字符串的全排列
要求不出现重复的排列，每个字符都可以做排列的开头
a ）b ）c
）c ）b
b ）a ）c
）c ）a
c ）b ）a
）a ）b
获胜者的分数
博弈论 先手胜或者后手胜
逆序栈
不能申请额外的数据结构，只能使用递归函数
字符串转化结果
给定一个只有数字字符组成的字符串str，1对应A，2对应B…
背包问题
暴力递归的解法就是尝试所有的可能，然后返回最大价值
// 暴力递归背包问题
public static int process(int[] weights,int[] values,int i,int alreadyWeight,int bag) {
// 停止递归的条件
// 已装的重量大于等于了包的容量
if(alreadyWeight >= bag)return 0;
// 或者已经撞到了最后一个 不能再装了
if(i == weights.length) return 0;
// 返回的是装了第i个物品或不装第i个物品的最大价值
return Math.max(values[i]+process(weights, values, i+1, alreadyWeight+weights[i], bag), process(weights,values,i+1,alreadyWeight,bag));
}
