文章目录
- 前言
- 导航
- 注意事项
- 技巧类
- 自定义Pair
- 排序
- N维数组转一维
- 位运算
- 状态压缩
- 算法基础
- 枚举 √
- 指数型枚举
- 排列型枚举
- 组合型枚举
- 模拟 √
- 日期天数问题：平年闰年情况
- 递归&分治 √
- 递推
- 贪心 √
- 货仓选址-模板题
- 排序 √
- 归并排序
- 前缀和&差分 √
- 前缀和
- 差分（一维、二维、三维）
- 二分 √
- 搜索
- DFS √
- BFS √
- IDA*
- 回溯
- 字符串
- KMP算法
- 动态规划 √
- 线性DP
- 背包DP
- 区间DP
- 树形DP
- 状态压缩DP
- 计数DP
- 数学 √
- 数论
- 算法基本定理
- 约数
- 最大公约数与公倍数
- 欧拉筛法（含朴素筛法、埃式筛法）
- 质数-欧拉筛
- 欧几里得与扩展欧几里得
- 辗转相除（含辗转相减法）
- 组合数学
- 容斥定理
- 快速幂
- 矩阵
- 数据结构
- 哈希表 √
- 树状数组 √
- 并查集
- 线段树 √
- 树上问题
- 树的直径
- 计算机几何
- 杂项
- 双指针 √
前言
本章节内容主要做一个全局算法题导航指引，含有代码基本模板、相对应习题以及相关知识点，所有题目围绕这个导航索引进行补充扩展，目前博主水平有限也在不断学习更新当前博客内容。
所有博客文件目录索引：博客目录索引(持续更新)
当前博客更新日志：
2023.4.2：更新动态规划-线性DP：数字三角形(最大路径)、最长上升子序列(朴素、贪心优化)、最长公共子序列、最短编辑距离的核心思想及模板
2023.3.31：更新动态规划-背包问题：01背包、完全背包、多重背包、分组背包的思路及精简模板
2023.2-2023.4.1：更新大体框架，添加大部分模板
导航
OI Wiki：我愿称之为算法最全知识点合集！
旧金山大学的数据结构与算法在线动效：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
对于Java的一些注意事项以及API可见：算法竞赛Java选手的语言快速熟悉指南
C++一般运行1秒(运行10^7^-10^8^)
时间复杂度：
- n ∈ 1000：O(n^2^)，dp
- n ∈ 10000：O(nlogn)，二分、排序
- 2^10^=1024，2^20^=1048576（10^6^），2^30^=1073741824（10^9^），2^40^=1e12，2^50^=1e15。【2^20^约等于100万，2^31^就爆一秒了】
- 10! = 362万，11! = 3900万，12! = 4亿，13! = 60亿
关于数据类型以及对应的内存范围：
- int：最大2147483647，20亿，2x10^10^
- long：占8个字节，64位，[-9223372036854775808到9223372036854775807] 百亿亿，9*2^19^
- 1亿亿等于1兆，一百兆。
- 64MB：64MB最多可以开16777216个int
，相当于一千六百七十万个。
调试技巧：
计算机程序花费时间：
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
//...
long endTime = System.currentTimeMillis();
System.out.println("花费时间" + (en dTime - startTime) + "ms");
System.out.println("花费时间" + (endTime - startTime) / 1000 + "s");
}
①acwing官网问题
- 若是出现Segmentation fault，那么可以使用exit(0)来进行调试确定在哪一行出了错：
void func(){
exit(0);
}
//调用
func();
- 若是在func()放在当前行执行没有出现Segmentation fault，说明再此之前没有可能出现Segmentation fault，那么就可以将func放置到后面。
②关于输入输出
//输入、输出函数
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
③自定义类及属性 > 定义一维数组效率。具体可见leetcode1235题
注意事项
1、关于long res = 0; res = int * int出现精度问题
原因：int * int 得到的值会转为int类型，哪怕乘积是一个long类型，所以我们这边应该先将乘数先转为一个long类型才可。
案例1：1237. 螺旋折线，在java中对于这种k参与运算并且相乘结果超int范围的，必须将其本身也设置为long类型。
2、关于1e2问题
1e1就是10，若是有10个0，那么就是1e9情况。
技巧类
自定义Pair
自定义的键值对集合Pair：在acwing中需要自定义
static class Pair<K, V> {
K x;
V y;
public Pair(K x, V y) {
this.x = x;
this.y = y;
}
}
排序
①方式一：自定义类的话需要继承comparable接口，也就是实现compareTo方法
static class Node implements Comparable<Node> {
public int ts;
public int id;
public Node(Integer ts, Integer id) {
this.ts = ts;
this.id = id;
}
public boolean equals(Node node) {
return this.ts == node.ts && this.id == node.id;
}
@Override
public int compareTo(Node o) {
if (this.ts == o.ts) return this.id - o.id;
return this.ts - o.ts;
}
}
②方式二：
//该接口是实现compare接口
Arrays.sort(list, (o1, o2)->{})
N维数组转一维
二维数组转一维：
int A, B;//A表示行数、B表示列数
public int get(int i, int j) {
return (i * B) + j;
}
三维数组转一维：
int A, B, C;
public int get(int i, int j, int k) {
return (i * B + j) * C + k;
}
位运算
与运算：
场景一：判断是偶数还是奇数
ch & 1 == 1 => 奇数 ch & 1 == 0 偶数
异或：
场景一：大写、小写字母转换，无需写if判断大小写来进行+32或-32，可直接进行ch ^= 1 << 5; 也就是异或32
示例：https://leetcode.cn/problems/letter-case-permutation/
ch[i] ^= 1 << 5;
//异或情况
a ^ b = c
a ^ c = b
状态压缩
5位状态：state = (1 << 5) - 1，此时即为11111
查看当前状态没有选择的：i = (1 << 5) - 1 - state
- 例如state=01100，最终i为10011。
当前状态补上新加的：state |= newState
- 例如state=00010，newState = 01100，最终结果为01110。
消除掉原先的一些状态：state = state & ~pack或者state ^ (state & pack)，两个等价
- 例如state = 11111，消除目标pack = 01100，最终结果为10011。
算法基础
枚举 √
枚举是否选择
指数型枚举
模板题链接：92. 递归实现指数型枚举
题目：从 1∼n这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
复杂度分析：时间复杂度O(2^n^)；空间复杂度O(n)
import java.util.*;
class Main{
private static int n;
private static int[] arr;//0表示初始，1表示选，2表示不选
public static void dfs(int u) {
if (u == n) {
//从选好的一组情况中来找到选的物品
for (int i = 0; i < n; i++) {
if (arr[i] == 1) {
System.out.printf("%d ",i + 1);
}
}
System.out.println();
return;
}
//递归多种状态
//选
arr[u] = 1;
dfs(u + 1);
arr[u] = 0;
//不选
arr[u] = 2;
dfs(u + 1);
arr[u] = 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
arr = new int[n];
dfs(0);
}
}
排列型枚举
知识点
模板例题：94. 递归实现排列型枚举
示例：把 1∼n这n个整数排成一行后随机打乱顺序，输出所有可能的次序。
复杂度分析：时间复杂度为 O(n*n!)；空间复杂度为O(n)
class Main {
static int N = 9;
static int n;
//存储结果集
private static int[] state = new int[N];
//存储该路径是否访问过
private static int[] vis = new int[N];
//递归处理
//dfs(0)开始
public static void dfs (int u) {
if (u == n) {
//输出对应的方案
for (int i = 0; i < n; i ++) {
System.out.printf("%d", state[i]);
}
System.out.println();
return;
}
//遍历枚举多种情况
for (int i = 0; i < n; i ++) {
if (!visited[i]) {
visited[i] = true;
state[u] = i + 1;//真实的值
//递归
dfs(u + 1);
//恢复
visited[i] = false;
state[u] = 0;
}
}
}
}
题单
组合型枚举
模板题目：93. 递归实现组合型枚举
介绍：在排列型中进行升级，原本给定3个数让你找到所有3个排列方案，而在这里有n个数，让你找对应m个( <= n)个数组合的排列情况。
复杂度分析：时间复杂度O(m^n^!)
class Main {
static final int N = 15;
static int n, m;
//每个结果集都
static int[] state = new int[N];
public static void dfs(int u, int start) {
//优化剪枝，提前结束
if (u + (n - start) < m) return;
//若是遍历的到终点个数个
if (u == m) {
//输出对应的方案
for (int i = 0; i < n; i ++) {
System.out.printf("%d ", state[i]);
}
System.out.println();
}
for (int i = start; i < n; i ++) {
statue[u] = i + 1;
dfs(u + 1, i + 1);
statue[u] = 0;
}
}
}
模拟 √
日期天数问题：平年闰年情况
//平年28天，闰年为29天
//判断闰年：不能被100整除,可以被4整除 或者 整除400
if (year % 100 != 0 && year % 4 == 0 || year % 400 == 0)
static int[] months = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//判断8位数是否是合法日期
public static boolean check(int d) {
int year = d / 10000;
int month = d % 10000 / 100;
int day = d % 100;
if (month > 12 || month == 0 || day > 31 || day == 0) return false;
//闰年判断
if (month != 2 && day > months[month]) return false;
if (month == 2) {
int leap = year % 4 == 0 && year % 100 != 0 || year % 400 == 0 ? 1 : 0;
if (day > 28 + leap) return false;
}
return true;
}
//判断日期的合法功能函数
public static boolean check(int year, int month, int day) {
if (month > 12 || month == 0 || day > 31 || day == 0) return false;
//闰年判断
if (month != 2 && day > months[month]) return false;
if (month == 2) {
int leap = year % 4 == 0 && year % 100 != 0 || year % 400 == 0 ? 1 : 0;
if (day > 28 + leap) return false;
}
return true;
}
日期时间点问题：
求 HH:mm:ss
//获取到h小时m分钟s秒的总共秒数
public static int get_seconds(int h, int m, int s) {
return h * 3600 + m * 60 + s;
}
//将对应的总秒数去换算得到小时，分钟，秒数
int hour = time / 3600, minute = time % 3600 / 60, second = time % 60;
递归&分治 √
递归包含内容：递归枚举、递推枚举、dfs、bfs
递推
根据之前的状态来进行不断推举，例如：斐波那契数列。
贪心 √
货仓选址-模板题
给你多个点，让你去确定在那个地点建仓库可以让来回距离最短：
将所有水平点存储到数组中对其进行排序，接着mid = (n + 1) / 2即可确定中间点，最后就是来进行求取距离。
- 若是有对应的公式推导成最终这个样子：|A~1~ - B| + |A~2~ - B| + |A~3~ - B| … + |A~n~ - B|，那么最后就是
ans += Math.abs(A[i] - A[mid])。
排序 √
归并排序
前缀和&差分 √
前缀和
一维前缀和：
s[i] = s[i - 1] + nums[i]
# 推导，其中nums的值需要从坐标1开始，若是默认给的从0开始则需要为s[i] = s[i - 1] + nums[i - 1]
s[1] = s[0] + nums[1]
s[2] = s[1] + nums[2] = nums[1] + nums[2]
s[3] = s[2] + nums[3] = nums[1] + nums[2] + nums[3]
# 计算范围：[1,3] s[3] - s[1 - 1] => [i, j] s[i] - s[j - 1]
二维前缀和：
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]
# 计算范围 x1,y1 x2y2
sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]
差分（一维、二维、三维）
蓝桥杯三维差分题：AcWing 1232. 三体攻击
一维：
步骤一(反推b)：b[i] = a[i] - a[i - 1]
中间步骤(范围操作)：
b[l] += c;
b[r + 1] -= c;
步骤三：a[i] = a[i - 1] + b[i]
二维：
步骤一(反推b)：b[i][j] = a[i][j] + a[i - 1][j - 1] - a[i - 1][j] - a[i][j - 1]
中间步骤(范围操作)：
b[x1][y1] += c
b[x2 + 1][y1] -= c
b[x1][y2 + 1] -= c
b[x2 + 1][y2 + 1] += c
步骤三(反推a)：a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j]
三维：
//步骤一：首先确定三维前缀和公式
b(x, y, z) = a(x, y, z) - a(x - 1, y, z) - a(x, y - 1, z) + a(x - 1, y - 1, z)
- a(x, y, z - 1) + a(x - 1, y, z - 1) + a(x, y - 1, z - 1) - a(x - 1, y - 1, z - 1)
中间步骤(范围操作)：
二维正面（以z1为）
b[x1 ][y1 ][z1] += val
b[x1 ][y2 + 1][z1] -= val
b[x2 + 1][y1 ][z1] -= val
b[x2 + 1][y2 + 1][z1] += val
转为z2+1，且符号改变
b[x1 ][y1 ][z2 + 1] -= val
b[x1 ][y2 + 1][z2 + 1] += val
b[x2 + 1][y1 ][z2 + 1] += val
b[x2 + 1][y2 + 1][z2 + 1] -= val
步骤三：最后反推求出a数组推导来进行计算
a(x, y, z) = b(x, y, z) + a(x - 1, y, z) + a(x, y - 1, z) - a(x - 1, y - 1, z)
+ a(x, y, z - 1) - a(x - 1, y, z - 1) - a(x, y - 1, z - 1) + a(x - 1, y - 1, z - 1)
扩展：
1、前缀异或
相关题目：
二分 √
规律：一组单调递增或者递减情况(不限制于数字)情况时可以采用二分来进行优化。【O(n) -> O(logn)】
模板：
//第一类二分写法：check
int l = 0, r = n;
while (l < r) {
int mid = l + r >> 1;
if (mid >= target) l = mid + 1;
else r = mid;
}
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (nums2[i] >= nums1[mid]) l = mid - 1;
else r = mid;
}
//第二种二分写法：
while (l != r) {
int mid = l + ((r - l) >> 1);
if (nums1[mid] < nums2[i]) l = mid + 1;
else r = mid;
}
题单
搜索
DFS √
题型：最大长度
模板：
void dfs(int step) //步长
{
if(/*跳出循环的条件*/){
return; //return十分关键，否则循环将会无法跳出
}
/*函数主体
对功能进行实现*/
for(/*对现有条件进行罗列*/){
if(/*判断是否合理*/){
//将条件修改
dfs(/*新的step*/)
/*！重中之重，当跳出那层循环后将数据全部归位*/
}
}
}
矩阵模板：
int f[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //用于判断下一步怎么走向几个方向走就是几个数据
void dfs(int x,int y){ //进入点的坐标
if(/*跳出循环的条件*/){
/*作出相应操作*/
return; //不要忘了return
}
for(int i=0;i</*f的长度*/;i++){
int x0=x+f[i][0];
/*此处是更新点的坐标，注意是直接让原来的点加上这个数据，不是直接等于*/
int y0=y+f[i][1];
if(/*用新坐标x0,y0判断是否符合条件*/){
dfs(x0,y0); //用新的坐标进行递归
}
}
}
BFS √
题单
模板
题型：最短路径。
模板：
1、二叉树：
class Solution {
public static void main (String[] args) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(xx);//添加root节点
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
//取出node结点进行操作
TreeNode node = queue.poll();
//放置左右子节点
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
res.add(1.0 * sum / size);
}
}
}
2、二维矩阵：
class Point {
private int x;
private int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Solution {
public static void main (String[] args) {
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(1,2));//出发点
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
//取出Point结点进行操作
Point point = queue.poll();
//进行操作
//放置四个方向的节点
for (int d = 0; d < dicts.length; d++) {
int x = point.x + dicts[d][0];
int y = point.y + dicts[d][1];
queue.offer(new Point(x, y))
}
}
}
}
}
3、坐标点写法：
class Solution {
static final int N = 110;
static int[] q = new int[N * N];
static int hh, tt;//hh表示头指针(用于出队)，tt表示入队指针
//四个方向 (0, 1) (0, -1) (1, 0) (-1, 0)
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
//矩阵
static int[][] g = new int[N][N];
static int H, W;
//将二维坐标转为一个数字
public static int get(int x, int y) {
return x * (W + 1) + y;
}
public static void main (String[] args) {
//bfs过程
while (hh < tt) {
int top = q[hh ++];
int x = top / (W + 1);
int y = top % (W + 1);
//四个方向
for (int k = 0; k < 4; k ++) {
int xx = x + dx[k];
int yy = y + dy[k];
//搜索校验（边界情况 && 其他情况xxx）
if (xx >= 1 && yy >= 1 && xx <= H && yy <= W) {
//入队
q[tt ++] = get(x, y);
//相关动作xxx
}
}
}
}
}
IDA*
考虑事项：
- 迭代加深：进行逐层判断，是否能够完全覆盖。
- 选择最少的列：尽可能选择情况少的来进行搜索。
- 可行性剪枝：通过使用一个估价函数h(state)表示对于状态state至少需要多少行。若是符合当前的搜索的行数则继续向下，若是不符合提前剪枝结束。
题单
回溯
字符串
KMP算法
模板：
package com.changlu.string;
public class KMP {
public static void main(String[] args) {
//API
System.out.println("ababcabcaabbcdeabcdef".indexOf("abcaabb"));
//手写
System.out.println(kmp("ababcabcaabbcdeabcdef", "abcaabb"));
}
public static int kmp (String str, String sub) {
int[] next = getNext(sub);
for (int i = 0, j = 0; i < str.length(); i++) {
while (j > 0 && str.charAt(i) != sub.charAt(j)) {
j = next[j - 1];
}
if (str.charAt(i) == sub.charAt(j)) j++;
//若是匹配到最后
if (j == sub.length()) {
return i - j + 1;
}
}
return -1;
}
public static int[] getNext(String str) {
int[] next = new int[str.length()];
next[0] = 0;
for (int i = 1, j = 0; i < str.length(); i ++) {
while (j > 0 && str.charAt(i) != str.charAt(j)) {
j = next[j - 1];
}
//若是当前字符相等
if (str.charAt(i) == str.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}
动态规划 √
线性DP
来源：AcWing 902. 最短编辑距离【闫式DP大法好：）】
数字三角形问题：找最大路径问题
//时间复杂度O(n^2) 空间O(n)
//上至下 边界填充负无穷值，滚动数组从后往前，最后一层需要进行计算最小值
f(i, j) += max(f(i - 1, j - 1), f(i - 1, j))
//从下之上
f(i, j) += max(f(i + 1, j), f(i + 1, j + 1)) + a[i][j]
子序列问题：这个子序列并非是连续的。
最长上升子序列：找严格递增(减)子序列长度
//暴力法 时间O(n^2) 空间O(n)
for (int i = 1; i <= n; i ++) {
fn[i] = 1;
for (int j = 1; j < i; j ++) {
//递增情况
if (a[i] > a[j]) fn[i] = Math.max(fn[i], fn[j] + 1);
}
}
//贪心优化 时间O(n.logn) 空间O(n)
//核心思想：若是添加数>末尾数，直接添加到末尾；若是<=，则找到队列中>=该添加数的第一个数(从前往后)
//注意点：这种做法最终在q队列数组中的剩余元素并非是最长递增的正确元素，在这个过程中我们对于替换队列中的元素目的为（每次替换元素都是，增加了序列长度增长的潜力！！！）
q = new int[N] //优先队列
q[++ cnt] = a[1]; //第一个数先入队
for (int i = 2; i <= n; i ++) {
if (a[i] > q[cnt]) { //若是递增直接添加到后面
q[++ cnt] = a[i];
}else {
//替换从前往后第一个>=a[i]的位置 find()是二分操作
q[find(a[i])] = a[i];
}
}
public static int find (int num) {
int l = 1, r = cnt;
while (l < r) {
int mid = l + r >> 1;
//若是目标元素值>=num，此时范围为[l, mid]
if (q[mid] >= num) r = mid;
else l = mid + 1;//若是<num，则需要直接到右半部分去寻找，范围为[mid + 1, r]
}
return r;
}
最长公共子序列：给定A、B两个字符串，求两者之间的最长公共子序列
//时间复杂度O(n*m) 空间O(n*m)
//不重不漏针对于第i个第j个分为如下四种情况
f(i - 1, j - 1)：两个都不选，00
f(i - 1, j)：第i个不选，第j个选，01
f(i, j - 1)：第i个选，第j个不选，10
f(i - 1,j - 1) + 1：两个都选，11
//转移方程
a[i] != a[j]：max (a(i - 1, j)，a(i, j - 1)) //【实际上由于a(i - 1, j)和a(i, j - 1)是包含a(i - 1, j - 1)所以我们可以省略掉a(i - 1, j - 1)；原本是max (a(i - 1, j)，a(i, j - 1), a(i - 1, j - 1))】
a[i] == a[j]：`f(i - 1, j - 1) + 1`
最短编辑距离问题：一个字符串替换成另一个字符串的最短替换操作次数，给定插入、删除、编辑三种情况
//时间复杂度O(n*m) 空间O(n*m)
//初始化 0->1,2,3,4,5 (i->j) 插入操作 | 1,2,3,4,5 -> 0 (i->j) 删除操作
fn[0][j] = j; fn[i][0] = i;
//删除与插入情况：
min(f(i - 1, j) + 1, f(i, j - 1) + 1)
//a[i] == b[j]
min(f(i, j), f(i - 1, j - 1))
//a[i] != b[j]（需要进行替换操作一次）
min(f(i, j), f(i - 1, j - 1) + 1)
背包DP
01背包问题：每件物品选一次或者不选，每件物品最多选1次
- fn(i, j)表示的选择i个，重量为j的最大价值
//二维数组
//不选：
fn[i][j] = fn[i - 1][j];
//选：
fn[i][j] = max (fn[i][j], fn[i - 1][j - v[i]] + w[i])
//一维滚动数组(需要从后往前进行遍历)
fn[j] = max (f[j], f[j - v[i] + w[i])
完全背包问题：每件物品选一次或者不选，每件物品有无限个
//二维数组，优化之后（三重循环转二重循环）
//不选：
fn[i][j] = fn[i - 1][j];
//选：注意此时后面的fn[i]不再是i - 1
fn[i][j] = max (fn[i][j], fn[i][j - v[i]] + w[i])
//一维滚动数组(可直接从前往后遍历)
fn[j] = max(f[j], f[j - v[i]] + w[i])
多重背包（含优化）：每件物品最多有有限个，题目给出限制
//三重暴力
for (int i = 1; i <= n; i ++) //前i个物品
for (int j = 0; j <= m; j ++) //体积为k
//指定物品的数量（注意：k * v[i] <= j范围下进行选择）
for (int k = 0; k <= s[i] && k * v[i] <= j; k ++)
fn[i][j] = Math.max (fn[i][j], fn[i - 1][j - k * v[i]] + k * w[i]);
//时间复杂度O(n*logs*m)
//二进制优化：利用二进制去将1个物品s个数量优化为logs个组合箱子数，接着就是一个01背包思路解决方案
//读取每一个物品体积、价值以及数量，根据数量(二进制优化，拆分指定组箱子，每组有2进制阶乘个数)
int cnt = 0;
for (int i = 1; i <= n; i ++) {
//得到vw、ww、s（体积、价值以及数量）
int k = 1;
//根据s来分配每组物品的数量
while (k <= s) {
cnt ++;
v[cnt] = k * vv;
w[cnt] = k * ww;
s -= k;//减去总数
k *= 2;//2的倍乘
}
//处理多余的s
if (s > 0) {
cnt ++;
v[cnt] = s * vv;
w[cnt] = s * ww;
}
}
//最后就是一个01背包模板解决（一维滚动数组）
fn[j] = max (f[j], f[j - v[i] + w[i])
分组背包：有多组，每一组里面可以选一个
//三重暴力，以i组为单位对每组中的物品进行选择 s[i]、v[i][k]、w[i][k] 分别记录每组数量、指定i组第k个体积、指定i组第k个价值
for (int i = 1; i <= n; i ++) { //遍历前i组
for (int j = m; j >= 0; j --) { //体积重量 滚动数组，从后往前(01背包)
for (int k = 0; k < s[i]; k ++) { //组内第k个
//必须放在for循环内部，否则会直接提前结束
if (j >= v[i][k]) {
fn[j] = Math.max(fn[j], fn[j - v[i][k]] + w[i][k]);
}
区间DP
树形DP
状态压缩DP
计数DP
数学 √
数论
算法基本定理
知识点
题单
约数
最大公约数与公倍数
//最大公约数 greatest common divisor
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
//最小公倍数 Lowest Common Multiple
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
欧拉筛法（含朴素筛法、埃式筛法）
质数-欧拉筛
模板：
//欧拉筛所需要数组
//flag表示合数数组，true为合数
static boolean[] flag = new boolean[N];
//存储质数
static int[] primes = new int[N];
static int cnt = 0;
//欧拉筛
public static void getPrimes(int n) {
//遍历所有情况
for (int i = 2; i <= n; i++) {
if (!flag[i]) primes[cnt++] = i;
//枚举所有primes数组中的情况来提前构造合数
for (int j = 0; j < cnt && primes[j] * i <= n; j ++) {
int pre = primes[j] * i;
flag[pre] = true;
if (i % primes[j] == 0) break;
}
}
}
//判断是否是质数（由于之前primes数组仅仅开了sqrt(20亿)也就只有50万，所以这里需要进行遍历一遍质数数组来进行判断校验）
public static boolean isPrime(int x) {
//若是x在50万范围，直接从flag数组中判断返回即可
if (x < N) return !flag[x];
//若是>=50万，那么就进行遍历质数数组看是否有能够整除的，如果有那么直接返回
for (int i = 0; primes[i] <= x / primes[i]; i++) {
if (x % primes[i] == 0) return false;
}
return true;
}
欧几里得与扩展欧几里得
辗转相除（含辗转相减法）
组合数学
容斥定理
容斥定理：能被 a 或 b 整除的数的个数 = 能够被 a 整除的数的个数 + 能够被 b 整除的数的个数 - 既能被 a 又能被 b 整除的数的个数。
题单
快速幂
模板：
private static final long MOD = 1000000007;
/**
* 递归快速幂
* @param a 实数a
* @param n 阶数n，三种情况，n=0,n=奇数，n=偶数
* @return
*/
public static long qpow(long a, long n){
if (n == 0){
return 1;
}else if ((n & 1) == 1) { //奇数
return qpow(a, n -1) * a % MOD;
}else {
long temp = qpow(a, n / 2) % MOD;
return temp * temp % MOD;
}
}
/**
* 非递归方式
*/
public static long qpow2(long a, long n) {
long ans = 1;
while ( n != 0) {
if ((n & 1) == 1) { //若是n为奇数
ans *= a % MOD;
ans %= MOD;//求模处理
}
a *= a % MOD; //这个就表示偶数情况
a = a % MOD;//求模处理
n = n >> 1;
}
return ans;
}
矩阵
数据结构
哈希表 √
树状数组 √
并查集
线段树 √
#图论 √
评论区请在客户端页面查看