经典算法与题目对应列表：https://leetcode.cn/circle/discuss/bawPH2/

排序（LC-912. 排序数组）

插入排序

直接插入排序

class Solution {public int[] sortArray(int[] nums) {int n = nums.length; int j;for(int i = 1; i < n; i++){int k = nums[i];for(j = i-1; j >= 0 && nums[j] > k; j--){nums[j+1] = nums[j];}nums[j+1] = k;}return nums;}
}

折半插入排序

class Solution {public int[] sortArray(int[] nums) {int n = nums.length;for(int i = 1; i < n; i++){int k = nums[i];int left = 0, right = i;while(left < right){int mid = (left + right) >> 1;if(nums[mid] > k) right = mid;else left = mid + 1;}for(int j = i-1; j >= right; j--)nums[j+1] = nums[j];nums[right] = k;}return nums;}
}

希尔排序

希尔排序 - 插入排序的改进版。为了减少数据的移动次数，在初始序列较大时取较大的步长，通常取序列长度的一半，此时只有两个元素比较，交换一次；之后步长依次减半直至步长为1，即为插入排序，由于此时序列已接近有序，故插入元素时数据移动的次数会相对较少，效率得到了提高。

class Solution {public int[] sortArray(int[] nums) {int j;int n = nums.length;for(int d = n/2; d >= 1; d = d/2){ //步长5 3 1for(int i = d; i < n; i++){ //从步长开始遍历int tmp = nums[i];//（直接插入排序）注意就j = j- d;for(j = i - d;j >= 0 && nums[j] > tmp; j -= d){nums[j+d] = nums[j];}nums[j+d] = tmp;}}return nums;}
}

交换排序

冒泡排序

class Solution {public int[] sortArray(int[] nums) {int n = nums.length;for(int i = 0; i < n-1; i++){boolean isexchange = false;for(int j = n-1; j > i; j--){if(nums[j-1] > nums[j]){isexchange = true;swap(nums, j-1, j);}}if(isexchange == false) break; // 已经有序}return nums;}public void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

https://pic.leetcode-cn.com/1662538438-KKAVSu-%E5%BF%AB%E6%8E%92.gif

快速排序【重要】

class Solution {public int[] sortArray(int[] nums) {quickSort(nums, 0, nums.length-1);return nums;}public void quickSort(int[] nums, int low, int high){if(low < high){int pivot = Partition(nums, low, high);quickSort(nums, low, pivot-1);quickSort(nums, pivot+1, high);}}public int Partition(int[] nums, int low, int high){int pivot = nums[low];while(low < high){while(low < high && nums[high] >= pivot) high--;nums[low] = nums[high];while(low < high && nums[low] <= pivot) low++;nums[high] = nums[low];}nums[low] = pivot; // 最终位置在low = high; return low;}
}

选择排序

简单选择排序

class Solution {public int[] sortArray(int[] nums) {int n = nums.length;for(int i = 0; i < n; i++){int k = i;for(int j = i+1; j < n; j++){if(nums[k] > nums[j]) k = j;}swap(nums, i, k);}return nums;}public void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

堆排序【重要】

https://leetcode.cn/problems/sort-an-array/solution/javacha-ru-dui-gui-bing-kuai-pai-dui-shu-dm56/

思路：

将无序序列构建成一个堆，根据本题要求构建成大顶堆

将堆顶与末尾元素进行交换，将最大元素沉到数组末尾

重新调整结构，使其满足堆的定义，然后继续交换堆顶与数组末尾元素，反复执行调整+交换，直至整个数组有序

class Solution {public int[] sortArray(int[] nums) {// 重建大根堆for(int i = nums.length/2-1; i >= 0; i--){adjustHeap(nums, i, nums.length);}for(int i = nums.length-1; i > 0; i--){ //n-1趟交换swap(nums, i, 0); //输出堆顶元素adjustHeap(nums, 0, i);}return nums;}// 将元素位置为i的根的子树进行调整 public void adjustHeap(int[] arr, int idx, int length){int tmp = arr[idx];for(int k = idx*2+1; k < length; k = k*2 + 1){if(k+1 < length && arr[k] < arr[k+1]){k++; //找到key较大的子节点在下面进行比较}if(arr[k] > tmp){arr[idx] = arr[k]; //将arr[i]调整到双亲上idx = k; //继续向下调整 }else{break; // 已经满足根>左右}}arr[idx] = tmp;}public void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

①假定数组初始顺序如下

②从最后一个非叶子节点6开始调整

③向上调整上一个非叶子节点4

④调整完成后造成以4为根节点的堆结构混乱，继续调整

⑤将堆顶元素9与末尾元素4交换

⑥重新调整结构，此时调整的是[4,6,8,5]的结构

⑦再将堆顶元素8与末尾元素5进行交换，得到第二大元素8

⑧后续继续进行调整交换，直至整个数组有序

归并排序【重要】

归并排序是利用归并的思想实现的排序方法，先将数组递归分解，再对分解后的两个数组进行比较合并

class Solution {public int[] sortArray(int[] nums) {mergesort(nums, 0, nums.length-1);return nums;}public void mergesort(int[] nums, int left, int right){if(right <= left) return ;int mid = (left + right) / 2;//分解数组mergesort(nums, left, mid);mergesort(nums, mid+1, right);// 合并数组merge(nums, left, mid, right);}public void merge(int[] nums, int left, int mid, int right){int[] tmp = new int[right - left + 1];int i = left, j = mid + 1, k = 0;while(i <= mid && j <= right){tmp[k++] = nums[i] < nums[j] ? nums[i++] : nums[j++];}while(i <= mid) tmp[k++] = nums[i++];while(j <= right) tmp[k++] = nums[j++];//将排序后的temp数组合并至原数组对应的索引部分for(int index = 0; index < tmp.length; index++) {nums[left + index] = tmp[index];}}
}

基数排序

题解+代码：https://leetcode.cn/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/

class Solution {private static final int OFFSET = 50000;public int[] sortArray(int[] nums) {int len = nums.length;// 预处理，让所有的数都大于等于 0，这样才可以使用基数排序for (int i = 0; i < len; i++) {nums[i] += OFFSET;}// 第 1 步：找出最大的数字int max = nums[0];for (int num : nums) {if (num > max) max = num;}// 第 2 步：计算出最大的数字有几位，这个数值决定了我们要将整个数组看几遍int maxLen = getMaxLen(max);// 计数排序需要使用的计数数组和临时数组int[] count = new int[10];int[] temp = new int[len];// 表征关键字的量：除数// 1 表示按照个位关键字排序// 10 表示按照十位关键字排序// 100 表示按照百位关键字排序// 1000 表示按照千位关键字排序int divisor = 1;// 有几位数，外层循环就得执行几次for (int i = 0; i < maxLen; i++) {// 每一步都使用计数排序，保证排序结果是稳定的// 这一步需要额外空间保存结果集，因此把结果保存在 temp 中countingSort(nums, temp, divisor, len, count);// 交换 nums 和 temp 的引用，下一轮还是按照 nums 做计数排序int[] t = nums;nums = temp;temp = t;// divisor 自增，表示采用低位优先的基数排序divisor *= 10;}int[] res = new int[len];for (int i = 0; i < len; i++) {res[i] = nums[i] - OFFSET;}return res;}private void countingSort(int[] nums, int[] res, int divisor, int len, int[] count) {// 1、计算计数数组for (int i = 0; i < len; i++) {// 计算数位上的数是几，先取个位，再十位、百位int remainder = (nums[i] / divisor) % 10;count[remainder]++;}// 2、变成前缀和数组for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 3、从后向前赋值for (int i = len - 1; i >= 0; i--) {int remainder = (nums[i] / divisor) % 10;int index = count[remainder] - 1;res[index] = nums[i];count[remainder]--;}// 4、count 数组需要设置为 0 ，以免干扰下一次排序使用for (int i = 0; i < 10; i++) {count[i] = 0;}}private int getMaxLen(int num) {int maxLen = 0;while (num > 0) {num /= 10;maxLen++;}return maxLen;}
}

二分查找（35. 搜索插入位置）

class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length-1;while(left <= right){int mid = (left + right) >> 1;if(nums[mid] == target) return mid;else if(nums[mid] < target) left = mid+1;else right = mid-1;}return left;}
}

class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length;while(left < right){int mid = (left + right) >> 1;if(nums[mid] == target) return mid;else if(nums[mid] < target) left = mid+1;else right = mid;}return left;}
}

字符串KMP算法（28. 找出字符串中第一个匹配项的下标）

class Solution {// KMP算法(在s字符串中找t字符串的起始位置)public int strStr(String s, String t) {int[] next = get_next(t);int i = 0, j = 0;while(i < s.length() && j < t.length()){if(j == -1 || s.charAt(i) == t.charAt(j)){//当 j=0 时，也让主串i移动i++; j++;// 继续比较后继字符}else{j = next[j]; // 模式串向左移动 }}if(j == t.length()) return i - t.length();else return -1;}// next数组：当发生不匹配时，j应该回到的位置(注意是对模式串(目标串)构建next数组)public int[] get_next(String t){int[] next = new int[t.length()+1];int i = 0, j = -1;next[0] = -1;while(i < t.length()){if(j == -1 || t.charAt(i) == t.charAt(j)){i++; j++;next[i] = j;// 若pi = pj,则next[j+1] = next[j]+1}else{j = next[j];}}return next;}
}

二叉树

中序遍历非递归（94. 二叉树的中序遍历）

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode p = root; // p指针遍历，初始指向根节点while(p != null || !stack.isEmpty()){if(p != null){stack.push(p);p = p.left;}else{ // p 为空时，遍历到最左下了p = stack.pop(); // 弹出元素并访问res.add(p.val);p = p.right; // 遍历右子树}}return res;}
}

class Solution {List<Integer> res;public List<Integer> inorderTraversal(TreeNode root) {res = new ArrayList<>();if(root == null) return res;dfs(root);return res;}public void dfs(TreeNode node){if(node == null) return;dfs(node.left);res.add(node.val);dfs(node.right);}
}

后序遍历非递归（145. 二叉树的后序遍历）

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode p = root; // p指针遍历，初始指向根节点TreeNode pre = null; // pre前驱指针while(p != null || !stack.isEmpty()){if(p != null){ //走到最左边 stack.push(p);p = p.left;}else{p = stack.peek(); // 读取栈顶节点if(p.right != null && p.right != pre){ //若右子树存在，且未被访问过 p = p.right; // 访问右子树}else{ //否则弹出结点并访问 p = stack.pop();res.add(p.val);pre = p; // 记录最近访问的结点 p = null; // 结点访问完后，重置p指针}}}return res;}
}

class Solution {List<Integer> res;public List<Integer> postorderTraversal(TreeNode root) {res = new ArrayList<>();if(root == null) return res;dfs(root);return res;}public void dfs(TreeNode node){if(node == null) return;dfs(node.left);dfs(node.right);res.add(node.val);}
}

层序遍历（515. 在每个树行中找最大值）

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> res = new ArrayList<>();if(root == null) return res;Deque<TreeNode> dq = new ArrayDeque<>();dq.addLast(root);while(!dq.isEmpty()){int size = dq.size();int max = Integer.MIN_VALUE;while(size-- > 0){TreeNode cur = dq.pollFirst();max = Math.max(max, cur.val);if(cur.left != null) dq.addLast(cur.left);if(cur.right != null) dq.addLast(cur.right);}res.add(max);}return res;}
}

图论

图遍历算法

BFS（宽度搜索算法）（1091. 二进制矩阵中的最短路径）

class Solution {int[][] dict = {{0, 1}, {0, -1}, {1, 0}, {-1, 0},{1, 1},{1, -1}, {-1, 1}, {-1, -1}};public int shortestPathBinaryMatrix(int[][] grid) {int m = grid.length, n = grid[0].length;boolean[][] visit = new boolean[m][n];int res = 1;Deque<int[]> dq = new ArrayDeque<>();if(grid[0][0] == 1) return -1;if(m == 1 && n == 1) return 1;dq.addLast(new int[]{0, 0});visit[0][0] = true;while(!dq.isEmpty()){int size = dq.size();res++;while(size-- > 0){int[] pos = dq.pollFirst();for(int[] d : dict){int nx = pos[0] + d[0], ny = pos[1] + d[1];if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny] && grid[nx][ny] == 0){if(nx == m-1 && ny == n-1) return res;visit[nx][ny] = true;dq.addLast(new int[]{nx, ny});}}}}return -1;}
}

Dijkstra单源最短路径（743. 网络延迟时间）

class Solution {private static final int INF = Integer.MAX_VALUE/2;public int networkDelayTime(int[][] times, int n, int k) {// 邻接矩阵存储边信息int[][] g = new int[n][n];for(int i = 0; i < n; i++){Arrays.fill(g[i], INF); // 初始化路径不可达}for(int[] t : times){int x = t[0]-1, y = t[1]-1; // 边序号从0开始g[x][y] = t[2];}int[] dist = new int[n]; // 从源点到某点的距离数组Arrays.fill(dist, INF);dist[k-1] = 0; // 由于从 k 开始，所以该点距离设为 0，也即源点boolean[] used = new boolean[n]; // 节点是否被更新数组for(int i = 0; i < n; i++){// 在还未确定最短路的点中，寻找距离最小的点int x = -1;for(int y = 0; y < n; y++){if(!used[y] && (x == -1 || dist[y] < dist[x])){x = y;}}used[x] = true; // 用该点更新所有其他点的距离for(int y = 0; y < n; y++){dist[y] = Math.min(dist[y], dist[x] + g[x][y]);}}// 找到距离最远的点int ans = Arrays.stream(dist).max().getAsInt();return ans == INF ? -1 : ans;}
}

最小生成树算法（1584. 连接所有点的最小费用）

Prim算法（选节点）

Prim 算法也使用贪心思想来让生成树的权重尽可能小，也就是切分定理。

切分定理：对于任意一种切分，其中权重最小的那条横切边一定是构成最小生成树的一条边。

Prim算法先以某一个点进行切分，然后找到它权重最小的边及邻点，将其加入最小生成树集合MST，然后再以这两个点进行切分…

每次切分都能找到最小生成树的一条边，然后又可以进行新一轮切分，直到找到最小生成树的所有边为止

同时用一个布尔数组 inMST 辅助，防止重复计算横切边

可以用一个优先级队列存储这些横切边，就可以动态计算权重最小的横切边了

class Solution {public int minCostConnectPoints(int[][] points) {// 转化成无向图邻接表的形式List<int[]>[] graph = buildGraph(points);// 执行 Prim 算法Prim prim = new Prim(graph);return prim.minWeightSum;}// 转化成无向图邻接表的形式public List<int[]>[] buildGraph(int[][] points){int n = points.length;List<int[]>[] graph = new List[n];for(int i = 0; i < n; i++) graph[i] = new ArrayList<>();for(int i = 0; i < n; i++){for(int j = i+1; j < n; j++){int x1 = points[i][0], y1 = points[i][1];int x2 = points[j][0], y2 = points[j][1];int dis = Math.abs(x1 - x2) + Math.abs(y1 - y2); // 用 points 中的索引表示坐标点// 无向图其实就是双向图// 一条边表示为 int[]{from, to, weight}graph[i].add(new int[]{i, j, dis});graph[j].add(new int[]{j, i, dis});}}return graph;}class Prim{// 核心数据结构，存储横切边的优先级队列// 按照边的权重从小到大排序PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[2] - b[2]));// 类似 visited 数组的作用，记录哪些节点已经成为最小生成树的一部分boolean[] inMST;int minWeightSum = 0; // 记录最小生成树的权重和// graph 是用邻接表表示的一幅图，graph[s] 记录节点 s 所有相邻的边，// 三元组 int[]{from, to, weight} 表示一条边List<int[]>[] graph;public Prim(List<int[]>[] graph){this.graph = graph;inMST = new boolean[graph.length];cnt(0); // 随便从一个点开始切分都可以，从节点 0 开始inMST[0] = true;// 不断进行切分，向最小生成树中添加边while(!pq.isEmpty()){int[] edge = pq.poll();int to = edge[1], weight = edge[2];if(inMST[to]){// 节点 to 已经在最小生成树中，跳过,否则这条边会产生环continue;}// 将边 edge 加入最小生成树cnt(to); // 节点 to 加入后，进行新一轮切分，会产生更多横切边inMST[to] = true;minWeightSum += weight;}}// 将 s 的横切边加入优先队列public void cnt(int v){for(int[] edge : graph[v]){// 相邻接点 to 已经在最小生成树中，跳过，否则这条边会产生环if(inMST[edge[1]])  continue;// 加入横切边队列pq.add(edge);}}}}

Kruskal算法（选边）

Kruskal 算法需要用到 Union-Find 并查集算法

Kruskal 算法的一个难点是保证生成树的合法性，生成的树不能包含环，而 Union-Find 算法就擅长这个

对于添加的某条边，如果该边的两个节点本来就在同一连通分量里，那么添加这条边会产生环；反之，如果该边的两个节点不在同一连通分量里，则添加这条边不会产生环。

为了得到的这棵生成树是权重和最小的，用到了贪心思路：

将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和 mst 中的其它边不会形成环，则这条边是最小生成树的一部分，将它加入 mst 集合；否则，这条边不是最小生成树的一部分，不要把它加入 mst 集合。

本题小技巧：每个坐标点是一个二元组，那么按理说应该用五元组表示一条带权重的边，但这样的话不便执行 Union-Find 算法；所以用 points 数组中的索引代表每个坐标点。

class Solution {public int minCostConnectPoints(int[][] points) {int n = points.length;// 生成所有边及权重ArrayList<int[]> edges = new ArrayList<>();for(int i = 0; i < n; i++){// ⭐注意j从i+1开始，不要重头开始，避免重复for(int j = i+1; j < n; j++){int x1 = points[i][0], y1 = points[i][1];int x2 = points[j][0], y2 = points[j][1];int dis = Math.abs(x1 - x2) + Math.abs(y1 - y2);edges.add(new int[]{i, j, dis});}}// 将边按照权重从小到大排序Collections.sort(edges, (a, b) -> (a[2] - b[2]));// 执行 Kruskal 算法UnionFind uf = new UnionFind(n);int minWeight = 0;for(int[] edge : edges){int i = edge[0], j = edge[1], weight = edge[2];// 如果i和j属于同一集合中，说明不能连接这条边，会产生环，不能加入mstif(uf.isConnected(i, j)) continue;// 若这条边不会产生环，则属于最小生成树uf.union(i, j);minWeight += weight;}return minWeight;}
}class UnionFind{private int count;private int[] parent;public UnionFind(int n){parent = new int[n];count = 0;for(int i = 0; i < n; i++) parent[i] = i;}public void union(int x, int y){int rootx = find(x);int rooty = find(y);parent[rootx] = rooty;// 两个连通分量合并成一个连通分量，count数量减一count--;}public int find(int x){if(parent[x] != x){parent[x] = find(parent[x]);}return parent[x];}// 返回两者是否属于同一连通分量public boolean isConnected(int x, int y){return find(x) == find(y);}public int getCount(){ return count;}
}

拓扑排序（207. 课程表）

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] indegre = new int[numCourses]; // 记录每个节点的入度List<Integer>[] g = new ArrayList[numCourses];for(int i = 0; i < numCourses; i++) g[i] = new ArrayList<>();// 建图，获取每个节点的入度for(int[] p : prerequisites){indegre[p[0]]++; // p1 -> p0 有条边g[p[1]].add(p[0]);}// 队列里存放入度为0的节点Queue<Integer> queue = new LinkedList<>();for(int i = 0; i < numCourses; i++){if(indegre[i] == 0) queue.add(i);}// BFS遍历过程while(!queue.isEmpty()){int pre = queue.poll();numCourses--;for(int nxt : g[pre]){// 如果减去pre入度后的节点 入度为0,则可以执行该课程if(--indegre[nxt] == 0) queue.add(nxt);}}return numCourses == 0; // 判断是否所有课程都学习了}
}