一. 目录
- 排序
- 二分
- 二叉树非递归遍历
- 01背包
- 最长递增子序列
- 最长公共子序列
- 最长公共子串
- 大数加法
- 大数乘法
- 大数阶乘
- 全排列
- 子集
- N皇后
- 并查集
- 树状数组
- 线段树
- 字典树
- 单调栈
- 单调队列
- KMP
- Manacher算法
- 拓扑排序
- 最小生成树
- 最短路
- 欧拉回路
- GCD和LCM
- 素数筛法
- 唯一分解定理
- 乘法快速幂
- 矩阵快速幂
二. 面试常见手撕模板题以及笔试模板总结
0. Java快速输入
先给一个干货，可能有些题用Java会超时（很少），下面是Petr刷题时的模板，一般用了这个就不会出现C++能过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();
// 不关闭就没有输出
}
}
1. 排序
先给出一个swap函数，代表交换数组两个位置的值，很多排序用到这个函数:
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))排序(非比较排序可以看下面的详细总结)。
①. 冒泡
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;
}
}
②. 选择
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);
}
}
③. 插入
// 几个边界: 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;
}
}
第二种写法:
// 边界 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);
}
}
二分插入排序:
// 注意 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;
}
}
④. 希尔排序
采取的是增量序列每次减半的策略。
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;
}
}
}
⑤. 快排
给出的是三路快排
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};
}
⑥. 归并排序
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];
}
非递归归并排序:
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防止越界
}
}
}
⑦. 堆排
// 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过程即可。
// 注意这里是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过程也可以使用递归的写法:
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);
}
}
2. 二分
二分最主要的就是边界问题:
- 第一个=key的，不存在返回-1；
- 第一个>=key的；
- 第一个>key的；
- 最后一个=key的；
- 最后一个<=key的；
- 最后一个<key的；
最基本的二分查找:
static int b(int[] arr, int key){
int L = 0, R = arr.length - 1;
while(L <= R){
int mid = L + (R - L) / 2;
if(arr[mid] == key) return mid;
if(arr[mid] > key)
R = mid - 1;
else
L = mid + 1;
}
return -1;
}
口诀: 左边的先R(if后的)，右边的先L。
查找第一个=key的，不存在返回-1:
// 左边的三个， 注意是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的:
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的:
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的:
// 右边的三个 注意是 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的:
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;
}
最后一个<key的:
static int lastSmall(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;
}
3. 二叉树非递归遍历
这里给出一种非递归前序遍历、非递归中序、以及两种非递归后序遍历。
public class M3_BinaryTree {
static PrintStream out = System.out; //打印
static class Node{
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
static Node buildTree(int[] arr, int i){
if(i >= 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<Node> 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<Node> 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<Node> s1 = new Stack<>();
Stack<Node> 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<Node> 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);
}
}
4. 01背包
这个在笔试题中可能会出现，有时候只是出题场景不同。
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();
}
}
5. 最长递增子序列
这个也是笔试中可能出现变种的题目的。
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();
}
}
6. 最长公共子序列
也是笔试中可能出现的经典DP题目。
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));
}
}
7. 最长公共子串
同理，也是可能出现的。
/**
* 最长公共子串问题
*/
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] 返回公共子串
}
}
8. 大数加法
这个在拼多多的笔试中就出现过。。。
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();
}
}
9. 大数乘法
也不难。
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();
}
}
10. 大数阶乘
这个稍微特殊一点。我这里简单讲一下，举个例子结合代码就懂了。
比如算50的阶乘:
- 我们要先从1开始乘：1*2=2，将2存到a[0]中；
- 接下来是用a[0]3；23=6，将6储存在a[0]中；
- 接下来是用a[0]4；64=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、1206=720，那么720%10==0存到a[0]中，720/10%10==2存到a[1]中，720/100==7存到a[2]中。。。
代码：
/**
* 题目链接:
* 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));
}
}
写在最后
限于篇幅，剩余20个例子，就不在文中一一展现出来，本文共30个面试常见手撕模板题，现已全部整理完毕，需要的朋友
点击下方传送门即可免费领取！
传送门
以下是整理好的部分PDF文件截图
