切削工具东莞网站建设,专业的网页制作服务好,网站开发有哪些软件有哪些,专业网站建设公司兴田德润优惠吗文章目录前言导航注意事项技巧类自定义Pair排序N维数组转一维位运算状态压缩算法基础枚举 √指数型枚举排列型枚举组合型枚举模拟 √日期天数问题#xff1a;平年闰年情况递归分治 √贪心 √货仓选址-模板题排序 √归并排序前缀和差分 √前缀和差分#xff08;一维…
文章目录前言导航注意事项技巧类自定义Pair排序N维数组转一维位运算状态压缩算法基础枚举 √指数型枚举排列型枚举组合型枚举模拟 √日期天数问题平年闰年情况递归分治 √贪心 √货仓选址-模板题排序 √归并排序前缀和差分 √前缀和差分一维、二维、三维二分 √搜索DFS √BFS √IDA*回溯字符串KMP算法动态规划 √线性DP背包DP区间DP树形DP状态压缩DP计数DP数学 √数论算法基本定理约数最大公约数与公倍数欧拉筛法含朴素筛法、埃式筛法质数-欧拉筛欧几里得与扩展欧几里得辗转相除含辗转相减法组合数学容斥定理快速幂矩阵数据结构哈希表 √树状数组 √并查集线段树 √树上问题树的直径计算机几何杂项双指针 √前言
本章节内容主要做一个全局算法题导航指引含有代码基本模板、相对应习题以及相关知识点所有题目围绕这个导航索引进行补充扩展目前博主水平有限也在不断学习更新当前博客内容。
所有博客文件目录索引博客目录索引(持续更新)
导航
OI Wiki我愿称之为算法最全知识点合集 对于Java的一些注意事项以及API可见算法竞赛Java选手的语言快速熟悉指南
时间复杂度
n ∈ 1000O(n2)dpn ∈ 10000O(nlogn)二分、排序 2101024220104857610623010737418241092401e122501e15。【220约等于100万231就爆一秒了】10! 362万11! 3900万12! 4亿13! 60亿
关于数据类型以及对应的内存范围
int最大214748364720亿2x1010long占8个字节64位[-9223372036854775808到9223372036854775807] 百亿亿9*219 1亿亿等于1兆一百兆。 64MB64MB最多可以开16777216个int 相当于一千六百七十万个。
调试技巧
①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类型才可。
案例11237. 螺旋折线在java中对于这种k参与运算并且相乘结果超int范围的必须将其本身也设置为long类型。 案例21814. 统计一个数组中好对子的数目 2、关于1e2问题
1e1就是10若是有10个0那么就是1e9情况。 技巧类
自定义Pair
自定义的键值对集合Pair在acwing中需要自定义
static class PairK, V {K x;V y;public Pair(K x, V y) {this.x x;this.y y;}
}排序
①方式一自定义类的话需要继承comparable接口也就是实现compareTo方法
static class Node implements ComparableNode {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;}Overridepublic 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
例如state01100最终i为10011。
当前状态补上新加的state | newState
例如state00010newState 01100最终结果为01110。
消除掉原先的一些状态state state ~pack或者state ^ (state pack)两个等价
例如state 11111消除目标pack 01100最终结果为10011。 算法基础
枚举 √
指数型枚举
模板题链接92. 递归实现指数型枚举
题目从 1∼n这 n 个整数中随机选取任意多个输出所有可能的选择方案。
复杂度分析时间复杂度O(2n)空间复杂度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(mn!)
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;递归分治 √
贪心 √
货仓选址-模板题
给你多个点让你去确定在那个地点建仓库可以让来回距离最短
将所有水平点存储到数组中对其进行排序接着mid (n 1) / 2即可确定中间点最后就是来进行求取距离。
若是有对应的公式推导成最终这个样子|A1 - B| |A2 - B| |A3 - B| … |An - 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
转为z21且符号改变
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、前缀异或
相关题目
第 314 场周赛—6201. 找出前缀异或的原始数组
二分 √
规律一组单调递增或者递减情况(不限制于数字)情况时可以采用二分来进行优化。【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;
}题单 蓝桥杯13届真题-求阶乘算数基本定理、二分
搜索
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 i0;i/*f的长度*/;i){int x0xf[i][0]; /*此处是更新点的坐标注意是直接让原来的点加上这个数据不是直接等于*/int y0yf[i][1];if(/*用新坐标x0,y0判断是否符合条件*/){dfs(x0,y0); //用新的坐标进行递归}}
}BFS √ 题单 3、蓝桥杯13届真题-回忆迷宫模拟、BFS 模板 题型最短路径。
模板
1、二叉树
class Solution {public static void main (String[] args) {QueueTreeNode 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) {QueuePoint 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];//搜索校验边界情况 其他情况xxxif (xx 1 yy 1 xx H yy W) {//入队q[tt ] get(x, y);//相关动作xxx}}}}
}IDA*
回溯
字符串
KMP算法
模板
package com.changlu.string;public class KMP {public static void main(String[] args) {//APISystem.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
背包DP
区间DP
树形DP
状态压缩DP
计数DP
数学 √
数论
算法基本定理 知识点 算数基本定理 题单 蓝桥杯13届真题-求阶乘算数基本定理、二分
约数
约数个数及约数之和知识点(含公式)
最大公约数与公倍数
//最大公约数 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 整除的数的个数。 题单 leetcode、878. 第 N 个神奇数字(困难)
快速幂
快速幂及矩阵快速幂分析及代码实现
模板
private static final long MOD 1000000007;/*** 递归快速幂* param a 实数a* param n 阶数n三种情况n0,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;
}矩阵
数据结构
哈希表 √
树状数组 √
并查集
线段树 √
#图论 √
树上问题
树的直径
计算机几何
杂项
双指针 √
