蓝桥杯备赛

蓝桥杯备赛（java组）

做题思路

  1. 对照数据找规律，找不出就把数据带入执行一遍
  2. 对照规律设计公式，思考选择什么算法：递归，dfs，dp，暴力

动态规划

  1. 根据问题总结递归方程
  2. 初始化值
  3. 过滤约束条件下的情况
  4. 利用状态转移方程求出结果

基础能力准备

闰年（366天）

1
year % 4 == 0 && year % 100 !=0; //二月份有29天

普通闰年：公历年份是4的倍数，且不是100的倍数的，为闰年（如2004年、2020年等就是闰年）。

世纪闰年：公历年份是整百数的，必须是400的倍数才是闰年（如1900年不是闰年，2000年是闰年）。

办公软件技巧

word查找功能：ctr + F;

excel计算两年之间的天数：

image-20240302112013866

数学知识储备

标准差

$$
σ=\sqrt{∑(X−μ)2 \over N}
$$

排列

$$
C^{N}_{M}={N! \over (N-M)!*M!}
$$

$$
C^{N}{M}+C^{N-1}{M}=C^{N}_{M+1}
$$

$$
C^{0}{M}+C^{1}{M}+…..+C^{M}_{M}=2^M
$$

两点截距和斜率

$$
k={y1-y2 \over x1-x2}
$$

$$
b={x1y2-x2y1 \over x1-x2}
$$

java知识储备

基础数据类型

image-20240404212821008

image-20240405092729529

BigInteger

存储超大数值，并做开方运算

1
2
BigInteger two = BigInteger.valueOf(2);
System.out.println(two.pow(100));

输入输出方式

image-20240405092634139

精度输出：

1
2
float o = scanner.nextFloat();
System.out.printf("%.3f",o);
  1. 整数
    • %d：输出十进制整数。
    • %x 或 %X：输出十六进制整数（小写或大写）。
    • %o：输出八进制整数。
1
2
int num = 255;  
System.out.printf("%d %x %o\n", num, num, num); // 输出：255 ff 3ff
  1. 浮点数
  • %f：输出浮点数。
  • %e 或 %E：输出科学记数法表示的浮点数。
  • %a 或 %A：输出十六进制浮点数。
1
2
3
double pi = 3.141592653589793;  
System.out.printf("%.2f\n", pi); // 输出：3.14  
System.out.printf("%e\n", pi); // 输出：3.141593e+00

数据类型方法

image-20240405101312784

image-20240405095438026

image-20240405101404531

image-20240405113441410

image-20240405130143409

排序方法

image-20240405142806222

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
		Scanner scanner =new Scanner(System.in);
		int[][] arr = new int[][] {{1,2,3},{5,6,7}}; 
		Arrays.sort(arr,(o1,o2)->o1[0]-o2[0]);
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
		scanner.close();
	}

image-20240405144335649

String和StringBuilder

image-20240405150852428

subString(x,n) // [x,n)

image-20240408213213234

image-20240405152730592

String类型大小写转换：

1
2
3
4
5
if (word.matches("[a-z]+")) { // 小写单词转大写  
           System.out.print(word.toUpperCase() + " ");  
       } else if (word.matches("[A-Z]+")) { // 大写单词转小写  
           System.out.print(word.toLowerCase() + " ");  
       }

时间类

计算两天的间隔天数

1
2
3
4
5
6
import java.time.*;
Scanner scanner = new Scanner(System.in);
        LocalDate start = LocalDate.of(2003,6,7);
        LocalDate end = LocalDate.of(2024, 4, 12);
        long n = ChronoUnit.DAYS.between(start, end);
        System.out.println(n);

常用导包

1
2
3
import java.util.*;
import java.lang.Math;
import java.util.Scanner;

队列类Queue

由链表（LinkedList）实现

1
Queue queue = new LinkerList();

Queue的6个方法
压入元素(添加)：add()、offer()
相同：未超出容量，从队尾压入元素，返回压入的那个元素。
区别：在超出容量时，add()方法会对抛出异常，offer()返回false

弹出元素(删除)：remove()、poll()
相同：容量大于0的时候，删除并返回队头被删除的那个元素。
区别：在容量为0的时候，remove()会抛出异常，poll()返回false

获取队头元素(不删除)：element()、peek()
相同：容量大于0的时候，都返回队头元素。但是不删除。
区别：容量为0的时候，element()会抛出异常，peek()返回null。

阻塞队列
阻塞队列（Blocking Queue）提供了可阻塞的 put 和 take 方法，它们与可定时的 offer 和 poll 是等价的。如果队列满了 put 方法会被阻塞等到有空间可用再将元素插入；如果队列是空的，那么take 方法也会阻塞，直到有元素可用。当队列永远不会被充满时，put 方法和 take 方法就永远不会阻塞。

Map

1
Map<String, String> map = new HashMap<String,String>();

get方法：获取指定键(key)所对应的值(value)

put方法：将指定的键与值对应起来，并添加到集合中

使用put方法时，若指定的键(key)在集合中

remove方法：根据指定的键(key)删除元素，返回被删除元素的值(value)。

Map遍历方式：

1
2
3
4
5
6
7
8
9
10
11
//获取Map中的所有key
        Set<String> keySet = map.keySet();
        //遍历存放所有key的Set集合
        Iterator<String> it =keySet.iterator();
        while(it.hasNext()){                         //利用了Iterator迭代器**
            //得到每一个key
            String key = it.next();
            //通过key获取对应的value
            String value = map.get(key);
            System.out.println(key+"="+value);
        }

字符串操作

  1. 查找索引

indexOf() 方法用于返回字符（串）在指定字符串中首次出现的索引位置，如果能找到，则返回索引值，否则返回 -1。该方法主要有两种重载形式：

  • str.indexOf(value)
  • str.indexOf(value,int fromIndex)

其中，str 表示指定字符串；

value 表示待查找的字符（串）；

fromIndex 表示查找时的起始索引，如果不指定 fromIndex，则默认从指定字符串中的开始位置（即 fromIndex 默认为 0）开始查找

1
2
String s = "Hello Java";
int size = s.indexOf('v');    // size的结果为8
  1. 根据索引查找

String 类的 charAt() 方法可以在字符串内根据指定的索引查找字符，该方法的语法形式如下：
字符串名.charAt(索引值)
提示：字符串本质上是字符数组，因此它也有索引，索引从零开始。

charAt() 方法的使用示例如下：

1
2
3
4
String words = "today,monday,sunday";
System.out.println(words.charAt(0));    // 结果：t
System.out.println(words.charAt(1));    // 结果：o
System.out.println(words.charAt(8));    // 结果：n
  1. 输入字符串转char数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;

public class StringToCharArray {
    public static void main(String[] args) {
        // 创建Scanner对象用于获取控制台输入
        Scanner scanner = new Scanner(System.in);
        
        // 提示用户输入一个字符串
        System.out.print("请输入一个字符串: ");
        String inputString = scanner.nextLine();
        
        // 将字符串转换为字符数组
        char[] charArray = inputString.toCharArray();
        
        // 打印字符数组中的每个字符
        System.out.println("字符数组的内容:");
        for (char c : charArray) {
            System.out.println(c);
        }
        
        // 关闭scanner对象
        scanner.close();
    }
}

输入list

1
2
3
4
5
int T = scanner.nextInt();//次数
int[] arr= new int[T];
for(int j=0;j<T;j++){
arr[j] = scanner.nextInt();
}

Math类

  1. 求绝对值
1
Math.abs(i)

算法题

image-20240325210504677

动态规划

image-20240406165916151

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package leetCode;  
  
import java.util.Scanner;  
  
public class Main {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        int n = scanner.nextInt(); // 输入数组长度  
        int[] a = new int[n];  
        for (int i = 0; i < n; i++) {  
            a[i] = scanner.nextInt(); // 输入数组元素  
        }  
        int[] dp = new int[n];  
        dp[0] = 1; // 初始化dp数组，第一个元素的最长递增子序列长度为1  
        int max = 1; // 最长递增子序列的最大长度  
          
        for (int i = 1; i < n; i++) { // 从第二个元素开始遍历  
            dp[i] = 1; // 初始化为1，表示至少包含自己本身  
            for (int j = 0; j < i; j++) {  
                if (a[i] > a[j]) {  
                    dp[i] = Math.max(dp[i], dp[j] + 1); // 更新dp[i]为以a[i]结尾的最长递增子序列长度  
                }  
            }  
            max = Math.max(dp[i], max); // 更新最长递增子序列的最大长度  
        }  
        System.out.println(max); // 输出最长递增子序列的长度  
        scanner.close();  
    }  
}

最大公约数

1
2
3
4
5
6
7
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*y/gcd(x, y);
	}

进制转换

image-20240408164006491

1
c[i]^=32 //char字符大小进制转换

debug

image-20240409155238906

BFS

image-20240409155419576