# 面试常见手撕模板题以及笔试模板总结(附带少数ACM入门算法) 现在大部分大厂的笔试面试越来越重视算法。特别是笔试题里面，大部分题型和ACM几乎一样。 所以我在这里总结了一些(30个)常见面试和ACM**入门级别**的算法模板（其实也不只是ACM要求，大部分模板都可以在`LeetCode`中找到对应的题型），有一部分也是面试时候面试官经常要你手撕的经典算法。例如排序、二叉树非递归遍历、二分、大数等。 **可能这些算法有些对初学者有点难度，但是不要慌～...～，我在每个算法代码的上方都给了一个链接，每个算法几乎都有很详细的解释(大部分带图，有些是我写的，有些是我看到的很好的文章)，不懂的可以点链接进行学习，另外有些模板配了原题，可以验证算法正确性。祝大家在笔试面试手撕算法顺利。。^_^**。 当然这些只是我们刷题的基础和模板，**更多的还是需要我们多多刷题**，锻炼逻辑思维和感觉～...～。 语言用的Java，但是大部分代码和C++基本上没啥很大区别～...～。 **如果觉得总结的还不错的话，给个`star`哦*╯3╰ .** > 仓库会不断更新和完善新的笔试面试中出现的模板^_^。 > > 由于这段时间非常忙，C++版本没有跟上，有兴趣的可以先看我之前写的[ACMC++模板](https://blog.csdn.net/zxzxzx0119/article/details/79838261)，后面有时间我会补上^_^。 ## 目录 * [一、排序](#一排序) * [二、二分](#二二分) * [三、二叉树非递归遍历](#三二叉树非递归遍历) * [四、01背包](#四01背包) * [五、最长递增子序列](#五最长递增子序列) * [六、最长公共子序列](#六最长公共子序列) * [七、最长公共子串](#七最长公共子串) * [八、大数加法](#八大数加法) * [九、大数乘法](#九大数乘法) * [十、大数阶乘](#十大数阶乘) * [十一、全排列](#十一全排列) * [十二、子集](#十二子集) * [十三、N皇后](#十三n皇后) * [十四、并查集](#十四并查集) * [十五、树状数组](#十五树状数组) * [十六、线段树](#十六线段树) * [十七、字典树](#十七字典树) * [十八、单调栈](#十八单调栈) * [十九、单调队列](#十九单调队列) * [二十、KMP](#二十kmp) * [二十一、Manacher算法](#二十一manacher算法) * [二十二、拓扑排序](#二十二拓扑排序) * [二十三、最小生成树](#二十三最小生成树) * [二十四、最短路](#二十四最短路) * [二十五、欧拉回路](#二十五欧拉回路) * [二十六、GCD和LCM](#二十六gcd和lcm) * [二十七、素数筛法](#二十七素数筛法) * [二十八、唯一分解定理](#二十八唯一分解定理) * [二十九、乘法快速幂](#二十九乘法快速幂) * [三十、矩阵快速幂](#三十矩阵快速幂) ## Java快速输入 先给一个干货，可能有些题用Java会超时（很少），下面是[Petr](https://en.wikipedia.org/wiki/Petr_Mitrichev)刷题时的模板，一般用了这个就不会出现C++能过Java不能过的情况了。 ```java import java.io.*; import java.util.*; public class Main { static class FR { BufferedReader br; StringTokenizer tk; FR(InputStream stream) { br = new BufferedReader(new InputStreamReader(stream), 32768); tk = null; } String next() { while (tk == null || !tk.hasMoreElements()) { try { tk = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return tk.nextToken(); } int nextInt() { return Integer.parseInt(next()); } } static void solve(InputStream stream, PrintWriter out) { FR in = new FR(stream); // start code..... } public static void main(String[] args) { OutputStream os = System.out; InputStream is = System.in; PrintWriter out = new PrintWriter(os); solve(is, out); out.close(); // 不关闭就没有输出 } } ``` ## 一、排序 先给出一个swap函数，代表交换数组两个位置的值，很多排序用到这个函数: ```java static void swap(int[] arr, int a, int b){ int t = arr[a]; arr[a] = arr[b]; arr[b] = t; } ``` 面试主要考察**比较排序**(`O(N^2)、O(NlogN)`)排序(非比较排序可以看下面的详细总结)。给出两篇博客: * [各种排序算法总结](https://github.com/ZXZxin/ZXBlog/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/Algorithm/Sort/%E5%90%84%E7%A7%8D%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93(%E5%85%A8%E9%9D%A2).md)； * [动图搞定排序算法](https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg)； ### 1、冒泡 ```java static void bubbleSort(int[] arr){ for(int end = arr.length - 1; end > 0; end--){ boolean isSort = true; for(int i = 0; i < end; i++){ if(arr[i] > arr[i+1]) { swap(arr, i, i + 1); isSort = false; } } if(isSort) break; } } ``` ### 2、选择 ```java static void selectSort(int[] arr){ for(int i = 0; i < arr.length; i++){ int minIdx = i; for(int j = i + 1; j < arr.length; j++) minIdx = arr[j] < arr[minIdx] ? j : minIdx; swap(arr, minIdx, i); } } ``` ### 3、插入 ```java // 几个边界: i=1开始(不是必须)、j >= 0, arr[j+1] = key注意一下 static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int key = arr[i], j; for (j = i - 1; j >= 0 && arr[j] > key; j--) arr[j + 1] = arr[j]; arr[j + 1] = key; } } ``` 第二种写法: ```java // 边界 j > 0 static void insertSort2(int[] arr) { for (int i = 1; i < arr.length; i++) { for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) swap(arr, j, j - 1); } } ``` 二分插入排序: ```java // 注意 R = i-1，注意找第一个>=key的，注意arr[i]先用key保存 static void binaryInsertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int L = 0, R = i - 1; // 找第一个大于的 二分边界搞不清的看下面的二分链接 int key = arr[i]; while (L <= R) { int m = L + (R - L) / 2; if (arr[m] > arr[i]) { R = m - 1; } else { L = m + 1; } } for (int j = i - 1; j >= L; j--) arr[j + 1] = arr[j]; arr[L] = key; } } ``` ### 4、希尔排序 采取的是**增量序列每次减半**的策略。 ```java static void shellSort(int[] arr) { for (int g = arr.length; g > 0; g /= 2) { // 增量序列 gap for (int end = g; end < arr.length; end++) { // 每一个组的结束元素, 从数组第gap个元素开始 // 每组做插入排序 int key = arr[end], i; for (i = end - g; i >= 0 && key < arr[i]; i -= g) arr[i + g] = arr[i]; arr[i + g] = key; } } } ``` ### 5、快排 给出的是三路快排，其他的看我给的博客。 ```java static void quickSort(int[] arr){ if(arr == null || arr.length == 0) return; quickRec(arr, 0, arr.length - 1); } static void quickRec(int[] arr, int L, int R) { if (L >= R) return; swap(arr, L, L + (int) (Math.random() * (R - L + 1))); int[] p = partition(arr, L, R); quickRec(arr, L, p[0] - 1); quickRec(arr, p[1] + 1, R); } // 用arr[L]作为划分点 static int[] partition(int[] arr, int L, int R) { int key = arr[L]; int less = L, more = R + 1; int cur = L + 1; while (cur < more) { if (arr[cur] < key) { swap(arr, ++less, cur++); } else if (arr[cur] > key) { swap(arr, --more, cur); } else { cur++; } } swap(arr, L, less); // 返回相等的两个下标，　less位置是我最后交换过来的划分值，more位置是>的，所以返回more-1 return new int[]{less, more - 1}; } ``` ### 6、归并排序 ```java static void mergeSort(int[] arr){ if(arr == null || arr.length == 0) return; mergeRec(arr, 0, arr.length - 1); } //注意是mergeSort(arr, L, m); 不是mergeSort(arr, L, m-1) static void mergeRec(int[] arr, int L, int R) { if (L >= R) return; int m = L + (R - L) / 2; mergeRec(arr, L, m); mergeRec(arr, m + 1, R); merge(arr, L, m, R); } static void merge(int[] arr, int L, int mid, int R) { int[] h = new int[R - L + 1]; int p1 = L, p2 = mid + 1; int k = 0; while (p1 <= mid && p2 <= R) h[k++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; // 注意保证稳定性 while (p1 <= mid) h[k++] = arr[p1++]; while (p2 <= R) h[k++] = arr[p2++]; for (int i = 0; i < k; i++) arr[L + i] = h[i]; } ``` 非递归归并排序: ```java static void mergeSortBU(int[] arr) { for (int sz = 1; sz <= arr.length; sz += sz) { // 区间的个数，1..2..4..8 for (int i = 0; sz + i < arr.length; i += sz + sz) { // 对[i...i+sz-1]和[i+sz...i+2*sz-1]内归并 merge(arr, i, i + sz - 1, Math.min(arr.length - 1, i + 2 * sz - 1)); // min防止越界 } } } ``` ### 7、堆排 ```java // if(arr == null || arr.length <= 1) return; 是必须的 static void heapSort(int[] arr) { if (arr == null || arr.length <= 1) return; for (int i = 0; i < arr.length; i++) siftUp(arr, i);//上浮方式建堆 int size = arr.length - 1; swap(arr, 0, size); while (size > 0) { siftDown(arr, 0, size); swap(arr, 0, --size); } } // 上浮 static void siftUp(int[] arr, int i) { while (arr[i] > arr[(i - 1) / 2]) { swap(arr, i, (i - 1) / 2); i = (i - 1) / 2; } } // 下沉 static void siftDown(int[] arr, int i, int heapSize) { int L = 2 * i + 1; while (L < heapSize) { int maxIndex = L + 1 < heapSize && arr[L + 1] > arr[L] ? L + 1 : L; maxIndex = arr[i] > arr[maxIndex] ? i : maxIndex; if (maxIndex == i) break; swap(arr, i, maxIndex); i = maxIndex; L = 2 * i + 1; } } ``` 第二种方式，使用`heapfiy`的优化，只需要使用`siftDown`过程即可。 ```java // 注意这里是size+1,因为这个不是交换了最后一个，所以要考虑arr[size]，下面不要考虑arr[size] // if (arr == null || arr.length <= 1) return; 是必须的 static void heapSort2(int[] arr) { if (arr == null || arr.length <= 1) return; int size = arr.length - 1; for (int i = (size - 1) / 2; i >= 0; i--) siftDown(arr, i, size + 1); swap(arr, 0, size); while (size > 0) { siftDown(arr, 0, size); swap(arr, 0, --size); } } ``` 其中`siftDown`过程也可以使用递归的写法: ```java static void siftDown(int[] arr, int i, int heapSize) { //从arr[i] 开始往下调整 int L = 2 * i + 1; int R = 2 * i + 2; int maxIdx = i; if (L < heapSize && arr[L] > arr[maxIdx]) maxIdx = L; if (R < heapSize && arr[R] > arr[maxIdx]) maxIdx = R; if (maxIdx != i) { swap(arr, i, maxIdx); siftDown(arr, maxIdx, heapSize); } } ``` ## 二、二分 给出我的[另一篇文章](https://github.com/ZXZxin/ZXBlog/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/Algorithm/BinarySearch/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E7%9A%84%E6%80%BB%E7%BB%93(6%E7%A7%8D%E5%8F%98%E5%BD%A2).md)，有关于二分的详细讲解。 二分最主要的就是边界问题: * 第一个`=key`的，不存在返回`-1`； * 第一个`>=key`的； * 第一个`>key`的； * 最后一个`=key`的； * 最后一个`<=key`的； * 最后一个` key) R = mid - 1; else L = mid + 1; } return -1; } ``` **口诀: 左边的先R(`if`后的)，右边的先L**。 查找第一个`=key`的，不存在返回`-1`: ```java // 左边的三个， 注意是L < arr.length static int firstEqual(int[] arr, int key){ int L = 0, R = arr.length - 1; while(L <= R){ int mid = L + (R - L) / 2; if(arr[mid] >= key) R = mid - 1; else L = mid + 1; } if(L < arr.length && arr[L] == key) return L; return -1; } ``` 第一个`>=key`的: ```java static int firstLargeEqual(int[] arr, int key){ int L = 0, R = arr.length - 1; while(L <= R){ int mid = L + (R - L) / 2; if(arr[mid] >= key) R = mid - 1; else L = mid + 1; } return L; } ``` 第一个`>key`的: ```java static int firstLarge(int[] arr, int key){ int L = 0, R = arr.length - 1; while(L <= R){ int mid = L + (R - L) / 2; if(arr[mid] > key) // 因为是第一个> 的，所以> R = mid - 1; else L = mid + 1; } return L; } ``` 最后一个`=key`的: ```java // 右边的三个 注意是 R>=0 static int lastEqual(int[] arr, int key){ int L = 0, R = arr.length - 1; while(L <= R){ int mid = L + (R - L) / 2; if(arr[mid] <= key) L = mid + 1; else R = mid - 1; } if(R >= 0 && arr[R] == key) return R; return -1; } ``` 最后一个`<=key`的: ```java static int lastEqualSmall(int[] arr, int key){ int L = 0, R = arr.length - 1; while(L <= R){ int mid = L + (R - L) / 2; if(arr[mid] <= key) L = mid + 1; else R = mid - 1; } return R; } ``` 最后一个`= arr.length || arr[i] == -1) return null; Node root = new Node(arr[i]); root.left = buildTree(arr, i * 2 + 1); root.right = buildTree(arr, i * 2 + 2); return root; } static Node buildTree(Scanner in){ Node root = null; int val = in.nextInt(); if(val != -1){ root = new Node(val); root.left = buildTree(in); root.right = buildTree(in); } return root; } //前序 static void preOrder(Node root){ if(root == null) return; Stack stack = new Stack<>(); Node p = root; // stack.push(root); // wrong while(p != null || !stack.isEmpty()){ while(p != null){ out.print(p.val + " "); stack.push(p); // 注意先推入 p = p.left; } p = stack.pop(); p = p.right; } out.println(); } //中序 static void inOrder(Node root){ if(root == null) return; Stack stack = new Stack<>(); Node p = root; while(p != null || !stack.isEmpty()){ while(p != null){ stack.push(p); p = p.left; } p = stack.pop(); out.print(p.val + " "); p = p.right; } out.println(); } //后序第一种: 双栈: 可以实现 中-> 右-> 左, 然后再用一个栈逆转即可 static void postOrder(Node root){ if(root == null) return; Node p = root; Stack s1 = new Stack<>(); Stack s2 = new Stack<>(); s1.push(root); while(!s1.isEmpty()){ Node cur = s1.pop(); s2.push(cur); if(cur.left != null ) s1.push(cur.left); if(cur.right != null ) s1.push(cur.right); } while(!s2.isEmpty()) out.print(s2.pop().val + " "); out.println(); } // 后序第二种pre static void postOrder2(Node root){ Stack s = new Stack<>(); s.push(root); Node pre = null; while(!s.isEmpty()){ Node cur = s.peek(); if((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))){ out.print(cur.val + " "); s.pop(); pre = cur; }else { if(cur.right != null) s.push(cur.right); if(cur.left != null) s.push(cur.left); } } out.println(); } public static void main(String[] args){ //int[] arr = {1,2,3,4,5,6,7,8,-1,9,-1,10,-1,11,-1, -1,-1,-1,-1,-1,-1,-1,-1}; // 和下面一样 int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, -1, 9, -1, 10, -1, 11, -1}; Node root = buildTree(arr, 0); preOrder(root); inOrder(root); postOrder(root); postOrder2(root); // Scanner in = new Scanner(new BufferedInputStream(System.in)); // 树结构和上面相同,输入: 1 2 4 8 -1 -1 -1 5 9 -1 -1 -1 3 6 10 -1 -1 -1 7 11 -1 -1 -1 // Node root2 = buildTree(in); } } ``` ## 四、01背包 这个在笔试题中可能会出现，有时候只是出题场景不同。 同样也给出我的[另一篇博客](https://github.com/ZXZxin/ZXBlog/blob/master/%E5%88%B7%E9%A2%98/Other/Hdu/DP/Hdu%20-%202602.%20Bone%20Collector(01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98).md)的总结。 ```java import java.io.*; import java.util.*; /** * 01背包 * 题目: http://acm.hdu.edu.cn/showproblem.php?pid=2602 */ public class M4_Knapsack { static int n, C; static int[] w, v; static int[][] dp; //记忆化 static int rec(int p, int curW) { if (p == n) return 0; if (dp[p][curW] != -1) return dp[p][curW]; if (curW + w[p] > C) return dp[p][curW] = rec(p + 1, curW); else return dp[p][curW] = Math.max(rec(p + 1, curW + w[p]) + v[p], rec(p + 1, curW)); } // 普通 static int dp(){ int[][] dp = new int[n+1][C+1]; for(int i = n - 1; i >= 0; i--){ for(int j = 0; j <= C; j++){ dp[i][j] = j + w[i] > C ? dp[i+1][j] : Math.max(dp[i+1][j], dp[i+1][j+w[i]]+v[i]); } } return dp[0][0]; } // 二维滚动 static int dp2(){ int[][] dp = new int[2][C+1]; for(int i = n - 1; i >= 0; i--){ for(int j = 0; j <= C; j++){ dp[i&1][j] = j + w[i] > C ? dp[(i+1)&1][j] : Math.max(dp[(i+1)&1][j], dp[(i+1)&1][j+w[i]]+v[i]); } } return dp[0][0]; } // 一维dp static int dp3(){ int[] dp = new int[C + 1]; for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= C; j++) { // 注意顺序一定要这样 dp[j] = j + w[i] > C ? dp[j] : Math.max(dp[j], dp[j + w[i]] + v[i]); } } return dp[0]; } public static void main(String[] args) { Scanner in = new Scanner(new BufferedInputStream(System.in)); PrintWriter out = new PrintWriter(System.out); int T = in.nextInt(); for (int t = 0; t < T; t++) { n = in.nextInt(); C = in.nextInt(); w = new int[n]; v = new int[n]; for (int i = 0; i < n; i++) v[i] = in.nextInt(); for (int i = 0; i < n; i++) w[i] = in.nextInt(); dp = new int[n][C + 1]; for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1); // out.println(rec(0, 0)); // out.println(dp()); // out.println(dp2()); out.println(dp3()); out.flush(); } out.close(); } } ``` ## 五、最长递增子序列 这个也是笔试中可能出现变种的题目的。 [详细讲解博客](https://github.com/ZXZxin/ZXBlog/blob/master/%E5%88%B7%E9%A2%98/LeetCode/DP/LeetCode%20-%20354.%20Russian%20Doll%20Envelopes%E5%8F%8A%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93.md)。 ```java import java.io.PrintWriter; import java.util.Arrays; /** * 最长公共子序列 * 题目: https://leetcode-cn.com/problems/longest-increasing-subsequence/ */ public class M5_LIS { // O(N^2) public int lengthOfLIS(int[] nums){ if(nums == null || nums.length == 0) return 0; int[] dp = new int[nums.length]; int res = 1; for(int i = 0; i < nums.length; i++){ dp[i] = 1; for(int j = 0; j < i; j++){ if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1); } res = Math.max(res, dp[i]); } return res; } // O(N^2) static int[] getDp(int[] nums){ if(nums == null || nums.length == 0) return new int[]{}; int[] dp = new int[nums.length]; for(int i = 0; i < nums.length; i++){ dp[i] = 1; for(int j = 0; j < i; j++){ if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1); } } return dp; } static int[] getLIS(int[] arr, int[] dp){ int maxLen = 0, end = 0; for(int i = 0; i < dp.length; i++) if(dp[i] > maxLen){ maxLen = dp[i]; end = i; } int[] lis = new int[maxLen]; lis[--maxLen] = arr[end]; for(int i = end - 1; i >= 0; i--){ if(dp[i] == dp[end] - 1 && arr[i] < arr[end]){ lis[--maxLen] = arr[i]; end = i; } } return lis; } // O(N * logN) public int lengthOfLIS2(int[] nums) { if (nums == null || nums.length == 0) return 0; int[] dp = new int[nums.length]; int[] ends = new int[nums.length + 1]; dp[0] = 1; ends[1] = nums[0]; int right = 1; // [1~right]为有效区　ends数组是有序的(升序), right是右边界 int L, mid, R; for (int i = 1; i < nums.length; i++) { L = 1; R = right; // 找到第一个>=arr[i]的，返回结果是 L while (L <= R) { mid = L + (R - L) / 2; if (ends[mid] >= nums[i]) R = mid - 1; else L = mid + 1; } // 说明以arr[i]以arr[i]结尾的最长递增子序列=ends区有效长度+1 if (L > right) { //没有找到arr[i]是最长的 (因为下标从1开始，所以判断是>right), dp[i] = right + 1; ends[right + 1] = nums[i]; // 扩大ends数组 right += 1; //扩大有效区 } else { // 找到了arr[l] > arr[i], 更新end[l] = arr[i] ,表示l长度的最长子序列结尾可以更新为arr[i] dp[i] = right; // dp[i]还是没有加长 ends[L] = nums[i]; } } return right; } public static void main(String[] args){ PrintWriter out = new PrintWriter(System.out); int[] arr = {10,9,2,5,3,7,101,18}; out.println(Arrays.toString(getLIS(arr, getDp(arr)))); out.close(); } } ``` ## 六、最长公共子序列 也是笔试中可能出现的经典DP题目。 [详细讲解博客](https://github.com/ZXZxin/ZXBlog/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/DP/51Nod%20-%201006.%20%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97LCS%20%E5%92%8C%20%E6%9C%80%E9%95%BF%E5%85%AC%E4%BC%97%E5%AD%90%E4%B8%B2.md) ```java import java.io.BufferedInputStream; import java.util.Scanner; /** * 最长公共子串 * 题目: http://www.51nod.com/Challenge/Problem.html#!#problemId=1006 */ public class M6_LCS { /** * dp[i][j]代表的是 str[0..i]与str[0...j]的最长公共子序列 */ static int[][] getDp(char[] s1, char[] s2) { int n1 = s1.length, n2 = s2.length; int[][] dp = new int[n1][n2]; dp[0][0] = s1[0] == s2[0] ? 1 : 0; for (int i = 1; i < n1; i++) // 一旦dp[i][0]被设置成1,则dp[i~N-1][0]都为1 dp[i][0] = Math.max(dp[i - 1][0], s1[i] == s2[0] ? 1 : 0); for (int j = 1; j < n2; j++) dp[0][j] = Math.max(dp[0][j - 1], s2[j] == s1[0] ? 1 : 0); for (int i = 1; i < n1; i++) { for (int j = 1; j < n2; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); if (s1[i] == s2[j]) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1); } } } return dp; } static String getLCS(char[] s1, char[] s2, int[][] dp) { if(s1 == null || s1.length == 0 || s2 == null || s2.length == 0) return ""; int i = s1.length - 1; int j = s2.length - 1; char[] res = new char[dp[i][j]]; //生成答案的数组 int index = dp[i][j] - 1; while (index >= 0) { if (i > 0 && dp[i][j] == dp[i - 1][j]) { i--; } else if (j > 0 && dp[i][j] == dp[i][j - 1]) { j--; } else { // dp[i][j] = dp[i-1][j-1]+1 res[index--] = s1[i]; i--; j--; } } return String.valueOf(res); } public static void main(String[] args) { Scanner in = new Scanner(new BufferedInputStream(System.in)); char[] s1 = in.next().toCharArray(); char[] s2 = in.next().toCharArray(); int[][] dp = getDp(s1, s2); // System.out.println(dp[s1.length-1][s2.length-1]); //length of lcs System.out.println(getLCS(s1, s2, dp)); } } ``` ## 七、最长公共子串 同理，也是可能出现的。 [详细讲解博客](https://github.com/ZXZxin/ZXBlog/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/DP/51Nod%20-%201006.%20%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97LCS%20%E5%92%8C%20%E6%9C%80%E9%95%BF%E5%85%AC%E4%BC%97%E5%AD%90%E4%B8%B2.md)。 ```java /** * 最长公共子串问题 * 题目: https://www.nowcoder.com/questionTerminal/02e7cc263f8a49e8b1e1dc9c116f7602?toCommentId=1532408 */ public class M7_LSS { public int findLongest(String A, int n, String B, int m) { char[] s1 = A.toCharArray(); char[] s2 = B.toCharArray(); int[][] dp = new int[s1.length][s2.length]; for (int i = 0; i < s1.length; i++) //注意和最长公共子序列有点不同 dp[i][0] = s1[i] == s2[0] ? 1 : 0; for (int j = 0; j < s2.length; j++) dp[0][j] = s1[0] == s2[j] ? 1 : 0; int res = 0; for (int i = 1; i < s1.length; i++) { for (int j = 1; j < s2.length; j++) { if (s1[i] == s2[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; res = Math.max(res, dp[i][j]); } } } return res; //dp数组中的最大值，就是最大公共字串的长度 } static int[][] getDp(char[] s1, char[] s2) { int[][] dp = new int[s1.length][s2.length]; for (int i = 0; i < s1.length; i++) //注意和最长公共子序列有点不同 dp[i][0] = s1[i] == s2[0] ? 1 : 0; for (int j = 0; j < s2.length; j++) dp[0][j] = s1[0] == s2[j] ? 1 : 0; int res = 0; for (int i = 1; i < s1.length; i++) { for (int j = 1; j < s2.length; j++) { if (s1[i] == s2[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; res = Math.max(res, dp[i][j]); } } } System.out.println(res); //4 return dp; //dp数组中的最大值，就是最大公共字串的长度 } /** * 根据dp表得到答案 */ static String getLongestSubstring(String s1, String s2, int[][] dp) { if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) return ""; int max = 0, end = 0; for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[0].length; j++) { if (dp[i][j] > max) { max = dp[i][j]; end = i; } } } return s1.substring(end - max + 1, end + 1); } // 空间优化 public int findLongest(String A, String B) { char[] s1 = A.toCharArray(); char[] s2 = B.toCharArray(); int row = 0, col = s2.length - 1; //从右上角开始 int max = 0, end = 0; //记录最大长度和结束位置 while (row < s1.length) { int i = row, j = col; int ul = 0; while (i < s1.length && j < s2.length) { if (s1[i] == s2[j]) ul++; else ul = 0; if (ul > max) { max = ul; end = i; } i++; j++; } if (col > 0) // 还没到最左边 -->　往左移动 col--; else row++; //到了最左 --> 往下移动 } return max; //return sa.substring(end-max+1, end+1); // [end-max+1, end] 返回公共子串 } } ``` ## 八、大数加法 这个在拼多多的笔试中就出现过。。。 可以看[这篇博客](https://www.cnblogs.com/wuqianling/p/5387099.html)吧，比较简单，就没有自己写了。 ```java public class M8_BigAdd { //大数加法 static String add(String str1, String str2){ char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int n1 = s1.length, n2 = s2.length; int maxL = Math.max(n1, n2); int[] a = new int[maxL + 1];//注意a,b的数组大小都必须是maxL+1 int[] b = new int[maxL + 1]; for(int i = 0; i < n1; i++) a[i] = s1[n1 - i - 1] - '0'; for(int i = 0; i < n2; i++) b[i] = s2[n2 - i - 1] - '0'; for(int i = 0; i < maxL; i++){ if(a[i] + b[i] >= 10){ int tmp = a[i] + b[i];//注意一定要先抽取出来 a[i] = tmp%10; a[i+1] += tmp/10; }else a[i] += b[i]; } StringBuilder sb = new StringBuilder(); if(a[maxL] != 0) sb.append((char)(a[maxL] + '0')); for(int i = maxL-1; i >= 0; i--) sb.append((char)(a[i] + '0')); return sb.toString(); } } ``` ## 九、大数乘法 也不难。 ```java public class M9_BigMul { // 大数乘法 static String mul(String str1, String str2){ char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int n1 = s1.length, n2 = s2.length; int[] a = new int[n1]; int[] b = new int[n2]; int[] c = new int[n1 + n2]; for(int i = 0; i < n1; i++) a[i] = s1[n1 - i - 1] - '0'; for(int i = 0; i < n2; i++) b[i] = s2[n2 - i - 1] - '0'; for(int i = 0; i < n1; i++){ for(int j = 0; j < n2; j++){ c[i+j] += a[i] * b[j]; } } for(int i = 0; i < n1 + n2 - 1; i++){ if(c[i] >= 10){ c[i+1] += c[i]/10; c[i] %= 10; } } int i; for(i = n1 + n2 - 1; i >= 0; i--) if(c[i] != 0) break; StringBuilder sb = new StringBuilder(); for(; i >= 0; i--) sb.append( (char)(c[i] + '0')); return sb.toString(); } } ``` ## 十、大数阶乘 这个稍微特殊一点。我这里简单讲一下，举个例子结合代码就懂了。 比如算`50`的阶乘: * 我们要先从1开始乘：`1*2=2`，将2存到`a[0]`中； * 接下来是用`a[0]*3`；`2*3=6`，将`6`储存在`a[0]`中； * 接下来是用`a[0]*4`；`6*4=24`，是两位数，那么`24%10==4`存到`a[0]`中，`24/10==2`存到`a[1]`中； * 接下来是用`a[0]*5`；`a[1]*5+num`(如果前一位相乘结果位数是两位数，那么`num`就等于十位上的那个数字；如果是一位数，`num==0`)；`24*5=120`，是三位数，那么`120%10==0`存到`a[0]`中，`120/10%10==2`存到`a[1]`中，`120/100==1`存到`a[2]`中； * 接下来是用`a[0]*6`、`a[1]*6+num`、`a[2]*6+num`、`120*6=720`，那么`720%10==0`存到`a[0]`中，`720/10%10==2`存到`a[1]`中，`720/100==7`存到`a[2]`中。。。 代码： ```java /** * 题目链接: * http://nyoj.top/problem/28 */ public class M10_BigPow { //大数计算阶乘位数，可以自己在网上找一下博客 //lg(N!)=[lg(N*(N-1)*(N-2)*......*3*2*1)]+1 = [lgN+lg(N-1)+lg(N-2)+......+lg3+lg2+lg1]+1; static int factorialDigit(int n) { double sum = 0; for (int i = 1; i <= n; i++) sum += Math.log10(i); return (int) sum + 1; } static String bigFactorial(int n) { int[] res = new int[100001]; int digit = 1; res[0] = 1; for (int i = 2; i <= n; i++) { int carry = 0; for (int j = 0; j < digit; j++) { int temp = res[j] * i + carry; //每一位的运算结果 res[j] = temp % 10; //将最低位保留在原位置 carry = temp / 10; //计算进位, 等下这个进位会累加到j+1 } while (carry != 0) { res[digit] = carry % 10; carry /= 10; digit++; } } StringBuilder sb = new StringBuilder(); for (int i = digit - 1; i >= 0; i--) sb.append( (char)(res[i] + '0')); return sb.toString(); } public static void main(String[] args){ System.out.println(bigFactorial(5)); } } ``` ## 十一、全排列 总共有四种，前两种是刘汝佳的书中的，后面是经典的和`dfs`的。给出三个博客(后两个我自己的): * [枚举生成全排列](https://www.cnblogs.com/Kohinur/p/8523856.html)。 * [非去重全排列](https://github.com/ZXZxin/ZXBlog/blob/master/%E5%88%B7%E9%A2%98/LeetCode/Search/LeetCode%20-%2046.%20Permutations(%E4%B8%89%E7%A7%8D%E6%96%B9%E6%B3%95).md)。 * [去重全排列](https://github.com/ZXZxin/ZXBlog/blob/master/%E5%88%B7%E9%A2%98/LeetCode/Search/LeetCode%20-%2047.%20Permutations%20II(%E4%B8%8D%E9%87%8D%E5%A4%8D%E5%85%A8%E6%8E%92%E5%88%97)(%E5%9B%9B%E7%A7%8D%E6%96%B9%E5%BC%8F%E5%AE%9E%E7%8E%B0).md)。 ```java public class M11_Permutation { static PrintStream out = System.out; // 1 ~ n 的排列 static void permutation(int[] tmp, int cur, int n) { if (cur == n) { // 边界 for (int i = 0; i < n; i++) out.print(tmp[i] + " "); out.println(); } else for (int i = 1; i <= n; i++) { //尝试在arr[cur]中填充各种整数 (1~n) boolean flag = true; for (int j = 0; j < cur; j++) if (i == tmp[j]) { // 如果i已经在arr[0]~arr[cur-1]中出现过，则不能选 flag = false; break; } if (flag) { tmp[cur] = i; //把i填充到当前位置 permutation(tmp, cur + 1, n); } } } // 数组的去重全排列 // tmp存放排列，arr是原数组 static void permutation(int[] tmp, int[] arr, int cur, int n) { if (cur == n) { for (int i = 0; i < n; i++) out.print(tmp[i] + " "); out.println(); } else for (int i = 0; i < n; i++) if (i == 0 || arr[i] != arr[i - 1]) { int c1 = 0, c2 = 0; for (int j = 0; j < n; j++) if (arr[j] == arr[i]) // 重复元素的个数 c1++; for (int j = 0; j < cur; j++) if (tmp[j] == arr[i]) // 前面已经排列的重复元素的个数 c2++; if (c2 < c1) { tmp[cur] = arr[i]; permutation(tmp, arr, cur + 1, n); } } } //非去重　经典全排列 static void permutation_2(int[] arr, int cur, int n){ if(cur == n){ for(int i = 0; i < n; i++) out.print(arr[i] + " "); out.println(); return; } for(int i = cur; i < n; i++){ swap(arr, i, cur); permutation_2(arr, cur + 1, n); swap(arr, i, cur); } } static void swap(int[] arr, int a, int b){ int t = arr[a]; arr[a] = arr[b]; arr[b] = t; } // 用一个used数组来求得全排列 static void dfs(int[] arr, ArrayList list, boolean[] used){ if(list.size() == arr.length){ for(int num : list) out.print(num + " "); out.println(); return; } for(int i = 0; i < arr.length; i++){ // if (used[i] || (i > 0 && !used[i - 1] && arr[i] == arr[i - 1])) continue; // 去重的写法，去重要先排序 Arrays.sort(arr); if(used[i]) continue; used[i] = true; list.add(arr[i]); dfs(arr, list, used); list.remove(list.size() - 1); used[i] = false; } } public static void main(String[] args) { int n = 5; permutation(new int[n], 0, n); out.println("--------------"); int[] arr = {1, 1, 1}; // 需要先排序 , 上面的排列只会输出 1,1,1因为我们去重了 Arrays.sort(arr); permutation(new int[arr.length], arr, 0, arr.length); out.println("--------------"); permutation_2(new int[]{1, 1}, 0, 2); // 输出两个{1, 1} out.println("---------------"); dfs(new int[]{1, 3, 2}, new ArrayList<>(), new boolean[3]); } } ``` 输出: ```java 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 -------------- 1 1 1 -------------- 1 1 1 1 --------------- 1 3 2 1 2 3 3 1 2 3 2 1 2 1 3 2 3 1 ``` ## 十二、子集 这个模板在`LeetCode`上面也是有原题的。例如[LeetCode - 78. Subsets](https://leetcode-cn.com/problems/subsets/)。 关于第三种方法(二进制枚举)，这里做简单解释:  `n = 3`；则要枚举`0 - 7` 对应的是有`7`个子集，每个子集去找有哪些元素`print_subset`中的 `1<< i `，也就是对应的那个位置是有元素的，例如`1`的二进制是`0001`也就是代表`0`位置有元素，`0010`是`2`，代表第一个位置是`1`，`0100`代表第`2`个位置上有元素，相应的`1000 = 8`对应第`3`个位置上有元素。 总结来说也就是对应`1<< i`对应` i`上是`1`(从`0`开始)，其余位置是`0`。看图容易理解：