基本数据类型
int的取值范围：
-2^31 ~ 2^31-1
-2147483648 ~ 2147483647（约等于10的9次方）
long long的取值范围：
-2^63 ~ (2^63-1）
-9223372036854775808 ~ 9223372036854775807（约等于10的18次方）
输入输出
使用文件流对输入输出的重要性：https://blog.csdn.net/weixin_43554580/article/details/130167554
快速输入输出 蓝桥杯JAVA-1.入门必知、正常输入输出和快速输入输出_正常输出和快速输出是什么意思-CSDN博客
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(br);
static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
输入：
private static char getChar() throws IOException {
String s = getString();
return s.charAt(0);
}
private static String getString() throws IOException {
InputStreamReader inputStreamReader = new InputStreamReader(System.in);
BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
String str = bufferedReader.readLine();
return str;
}
private static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
输出：
private static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
排序
重写 Comparator 比较器
参考：【蓝桥杯Java】数位排序 Java中Arrays.sort()自定义排序的实现
自定义排序的数组需要为Integer类型，使用int类型数组会报错
质数
1.质朴思路
private boolean isPrime(int num) {
//注意 i 遍历到最大 sqrt(num) 即可
int max = (int)Math.sqrt(num);
for (int i = 2; i <= max; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
2.埃式筛
public int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
Arrays.fill(isPrim, true);
// 从 2 开始枚举到 sqrt(n)。
for (int i = 2; i * i < n; i++) {
// 如果当前是素数
if (isPrim[i]) {
// 就把从 i*i 开始，i 的所有倍数都设置为 false。
for (int j = i * i; j < n; j+=i) {
isPrim[j] = false;
}
}
}
// 计数
int cnt = 0;
for (int i = 2; i < n; i++) {
if (isPrim[i]) {
cnt++;
}
}
return cnt;
}
3.线性筛(欧拉筛）
最大公约数-模板
//最大公约数-模板
public static long gcd(long x,long y) {
return y==0?x:gcd(y, x%y);
}
//最小公倍数-模板
public static long lcm(long x,long y) {
return x/gcd(x,y)*y;
}
Stack 类
| 序号 | 方法描述 |
|---|---|
| 1 | boolean empty() 测试堆栈是否为空。 |
| 2 | Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。 |
| 3 | Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。 |
| 4 | Object push(Object element) 把项压入堆栈顶部。 |
| 5 | int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。 |
Deque(双向队列)
Java 数据结构之Deque(双向队列)_java 双向队列-CSDN博客
String
substring() 方法
public String substring(int beginIndex)
或
public String substring(int beginIndex, int endIndex)
参数
- beginIndex -- 起始索引（包括）, 索引从 0 开始。
- endIndex -- 结束索引（不包括）。
例如：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| T | h | i | s | i | s |
str="This is";
str.substring(2,7);//"is is" [2,7)
str.substring(5);//"is"
KMP算法
排序
实现compare()
Arrays.sort(stu,new Comparator<student>() {
@Override
public int compare(student s1, student s2) {
if (s1.sum!=s2.sum) {
//降序
return s2.sum-s1.sum;
} else if (s1.chinese!=s2.chinese) {
return s2.chinese-s1.chinese;
} else {
//升序
return s1.no-s2.no;
}
}
});
例题：NOIP2009 普及组] 分数线划定 NOIP2007 普及组] 奖学金
二叉树
返回值问题：
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（113.路径总和ii）
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。（236. 二叉树的最近公共祖先 ）
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（112. 路径总和）
回溯算法
void backtracking(){
if(终止条件){
收集结果;
return;
}
for(集合的元素集，类似节点的个数){
处理节点;
递归函数;
回溯操作(撤销处理节点)l
}
}
回溯算法解决的几类问题
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
回溯算法优化问题
需要满足 n - i >= k - path.size( ) → i <= n + path.size( ) - k +1
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
动态规划
- 完全背包问题
- 如果求组合数就是外层for循环遍历物品，内层for循环遍历背包（无顺序）
- 如果求排列数就是外层for循环遍历背包，内层for循环遍历物品（有顺序）
图论
双向BFS
「双向 BFS」的搜索空间通常只有「朴素 BFS」的空间消耗的几百分之一，甚至几千分之一。
「双向 BFS」的基本实现思路如下：
创建「两个队列」分别用于两个方向的搜索；
创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」；
为了尽可能让两个搜索方向“平均”，每次从队列中取值进行扩展时，先判断哪个队列容量较少；
如果在搜索过程中「搜索到对方搜索过的节点」，说明找到了最短路径。
d1、d2 为两个方向的队列
m1、m2 为两个方向的哈希表，记录每个节点距离起点的
// 只有两个队列都不空，才有必要继续往下搜索
// 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
while(!d1.isEmpty() && !d2.isEmpty()) {
if (d1.size() < d2.size()) {
update(d1, m1, m2);
} else {
update(d2, m2, m1);
}
}
// update 为将当前队列 d 中包含的元素取出，进行「一次完整扩展」的逻辑（按层拓展）
void update(Deque d, Map cur, Map other) {}
蓝桥杯准备
材料
Eclipse配置
如何在eclipse中设置代码自动补全_eclipse怎么实现代码补全-CSDN博客
Eclipse设置代码提示后不显示Java 类问题解决-CSDN博客
eclipse的控制台/console不见了怎么调出来？_eclipse控制台不见了-CSDN博客
字体大小 -> Preferences搜索font-> Java文件夹修改代码字体大小(Java Editor) -> 搜索console修改控制台字体
.var -> ctrl+2 L
Eclipse 格式化代码块快捷键：Ctrl+Shift+F
拿分技巧
if(n<=1000){
暴力解法
} else {
正解
}
【Java组经验分享| 蓝桥杯拿分技巧】 https://www.bilibili.com/video/BV1NZ421z7WV/?share_source=copy_web&vd_source=5b3aef50b853d5b2be2d0da2462e99dd
时间&空间复杂度
计算机1s可以计算 10^8 次 代码的时间复杂度需要控制再10^8
256 MB最大也只能开 10^7 的数组
根据数据范围反推时间复杂度：
- 当题目数据 n<=100 -> O(n^3)
- 当题目数据 n<=1000 -> O(n2)或O(n2 * log(n))
- 当题目数据 n<=1e5 -> O(n)或O(n * log(n))
- 当题目数据n≤1e9 -> O(√n)
二分查找模板
//对数组[0,left-1]满足arr[i]<target,在[left,n-1]满足arr[i]>=target
//即left位置为查找元素的第一个位置
public int getLeft(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] >= target) right = mid;
else left = mid + 1;
}
return left;
}
//数组的区间[0,left] 满足 arr[i]<=target ,[left+1,n-1]满足arr[i]>target;
public int getRight(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = (left + right + 1) / 2;
if (arr[mid] <= target) left = mid;
else right = mid - 1;
}
return left;
}
进制转换
public static String fun(int x,int y){
StringBuilder str=new StringBuilder();
while(x>0){
str.append(x%y);
x/=y;
}
return str.reverse().toString();
}
//10进制转x进制
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b=scanner.nextInt();
String s=Integer.toString(a,b);
s=s.toUpperCase();
System.out.println(s);
}
//x进制转10进制
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int x = scanner.nextInt();
char[] chars=scanner.next().toCharArray();
int sum=0,k=1;
for(int i=chars.length-1;i>=0;i--) {
int res=0;
if (chars[i]>='A' && chars[i]<='Z') {
res=chars[i]-'A'+10;
} else {
res=chars[i]-'0';
}
sum+=res*k;
k*=x;
}
System.out.println(sum);
}