跳至主要內容

零基础速通蓝桥杯JAVA-B组-省4

源梦2024年6月16日...大约 7 分钟

JAVA语言基础

基础知识

运行程序

javac <文件名>
java <文件名>

数据类型

进制转换

String s = in.readLine();	
int a = Integer.parseInt(s, 16) // 将16进制的字符串转化十进制数
//BigInteger a = new BigInteger(s, 16);// 高精度数
out.write(Integer.toString(a, 8));	// 转化为8进制输出

进阶知识

类型转换

高精度运算

大数

int a=3;
BigInteger b=BigInteger.valueOf(a);

一些运算

add();
subtract();
multiply();
divide();
remainder();
pow();
gcd();
abs();
negate();
mod();
max();
min();

高阶知识

Lambda 表达式

基础模板

// 输入的库 这里使用了快速io
import java.InputStreamReader;
import java.io.BufferedReadr;
import java.io.IOExpection;
import java.io.PrintWriter;

public class Main {
	// java整数定义
	static int a;
	// java数组定义
	static int[][] b;
	// java数组初始化
	b = new int[100][10005];
	public static void main(String args[]) throws IOExpection {
		BufferedReader reader = new BufferedReader(new InputStreamReader(system.in));
		static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); // 就用System 就行 这个看看就好
		// 获取某一值
		int a = Integer.parseInt(reader.readLine());
		// 读取一连串的值
		String[] split = reader.readLine()String[].split(" ");
		// 读取一串数字
		String split = reader.readLine();
		for (int i = 1; i <= n; i ++) {
			int a = split.charAt(i-1)-'0';
		}
		// java中的输出
		System.out.println()
		System.out.printf("-1\n%d\n", r+1);
		out.println(b);  // b 的值为 30 
		out.flush();
        out.close();
	}
}

进阶模板

Arrays

import java.util.Arrays;

// 初始化数组b为0
Arrays.fill(b, 0);
// 数组排序
Arrays.sort(a);
// 二分查找 在a数组中找b a数组要已排序
Arrays.binarySearch(a, b[i])

STL

String

String s = "HelloWorld";
s.length(); // 10
s.charAt(0); // H
s.isEmpty(); // false
s = s.toLowerCase(); // helloworld
s = s.tpUpperCase();
s.trim(); // 去除前后空格
s.equals(s); // true 比较字符串
s.equalsIgnoreCase(s) // 忽略大小写比较
s.concat("添加内容相当于+")
s.compareTo(s) // 比大小
substring(int beginIndex, int endIndex) // 截取字符串
s.endsWith("");
s.startsWith("", <指定索引开始>);
s.contains(""); // 判断是否包含某序字符串
s.indexOf("", <指定索引开始>); // 第一次出现该字符串的索引
s.lastIndexOf(); // 反向索引
s.replace("",""); // 字符串替换
String String.replaceAll(String regex, String b)
boolean String.matches(String regrex)
String[] String.split(String regrex, int limit)
static int Integer.parseInt(String s)
static double Double.parseDouble(String s)
static T String.valueOf(T t)
char[] String.toCharArray(String s)
byte[] String.

高阶模板

Arrays

import java.util.Arrays;

//自定义排序
long startTime = System.currentTimeMillis();
Integer[] nums = new Integer[arrs.length];
for (int i = 0; i < arrs.length; i++) {
	nums[i] = arrs[i];
}
System.out.println(Arrays.toString(nums));
Arrays.sort(nums, new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
		return o2-o1;
	}
});
long endTime = System.currentTimeMillis();
System.out.println(Arrays.toString(nums));
System.out.println("耗时:" + (endTime - startTime));

这里要区别原子形数组和对象型数组

STL

ArrayList

import java.util.List;
import java.util.Arrays;

List<Integer> a = new ArrayList<>();
List<Integer> b = new ArrayList<>(3);
ArrayList<Integer> c = new ArrayList<>(Arrays.asList(1, 2, 3));
int ArrayList.get(int index)
for(int x : c) // 遍历c
boolean ArrayList.add(E e)
boolean ArrayList.remove(E e)
boolean ArrayList.clear()

StringBuffer

Set

TreeSet

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(1);
        treeSet.add(3);
        treeSet.add(5);
        treeSet.add(7);
        treeSet.add(9);

        int target = 6;

        Integer ceiling = treeSet.ceiling(target); // 返回大于等于6的最小元素，即7
        Integer floor = treeSet.floor(target); // 返回小于等于6的最大元素，即5

        System.out.println("大于等于6的最小元素: " + ceiling); // 输出 7
        System.out.println("小于等于6的最大元素: " + floor); // 输出 5
        Integer higher = treeSet.higher(target); // 返回严格大于6的最小元素，即7
        Integer lower = treeSet.lower(target); // 返回严格小于6的最大元素，即5
        System.out.println("严格大于6的最小元素: " + higher); // 输出 7
        System.out.println("严格小于6的最大元素: " + lower); // 输出 5
    }
}

Queue

map

Deque

Collections

读题基础

时间复杂度

速通就不考虑这些了 能做出来就行

空间复杂度

代码规范

简洁

int l = s.length();

数学基础

最大公约数

欧几里德算法

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b,a%b);
}

算法基础

图论基础

BF算法

(暴力匹配)

就是遍历

KMP算法

视频讲解

class Test {
    public static void main(String[] args) {
        System.out.println(kmp("ababaabb", "aab"));
    }
    static void getNext(String t, int[] next) {
        next[0] = 0;
        int k = 0, j = 1;
        while (j < t.length()) {
            if(t.charAt(j)==t.charAt(k)) {
                next[j] = ++k;
                j++;
            } else {
                if(k == 0) {
                    next[j] = k;
                    j++;
                } else {
                    k = next[k - 1];
                }
            }
        }

    }
    static int kmp(String s, String t) {
        int[] next = new int[t.length()];
        getNext(t, next);
        int i= 0, j = 0;
        while (i<s.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                if(j == 0) {
                    i++;
                } else {
                    j = next[j-1];
                }
            }
            if(j == t.length()) {
                return i - j;
            }
        }
        return -1;
    }
}

暴力

遍历、根据题目需求直接求解

快排

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

二分

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

归并

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

差分

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Arrays;

class Main{
    static int n, m;
    static int[] b = new int[(int)1e5+10];
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] split = reader.readLine().split(" ");
        n = Integer.parseInt(split[0]);
        m = Integer.parseInt(split[1]);
        split = reader.readLine().split(" ");
        Arrays.fill(b, 0);
        for (int i = 1; i <= n; i++) {
            // 构建差分数组
            if(i == 1) b[i] = Integer.parseInt(split[i-1]);
            else b[i] = Integer.parseInt(split[i-1]) - Integer.parseInt(split[i-2]);
        }
        while (m-- > 0) {
            split = reader.readLine().split(" ");
            int l = Integer.parseInt(split[0]);
            int r = Integer.parseInt(split[1]);
            int c = Integer.parseInt(split[2]);
            b[l] += c;
            b[r+1] -= c;
            
        }

        for (int i = 1; i <= n; i++) {
            b[i] += b[i-1];
            writer.print(b[i] + " ");
        }
        writer.flush();
    }

}

前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]


import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Arrays;

class Main{
    static int n, m;
    static int[] s = new int[(int)1e5+10];
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] split = reader.readLine().split(" ");
        n = Integer.parseInt(split[0]);
        m = Integer.parseInt(split[1]);
        split = reader.readLine().split(" ");
        Arrays.fill(s, 0);
        for (int i = 1; i <= n; i++) {
            s[i] = s[i-1] + Integer.parseInt(split[i-1]);
        }
        while (m-->0) {
            split = reader.readLine().split(" ");
            int l = Integer.parseInt(split[0]);
            int r = Integer.parseInt(split[1]);
            writer.println(s[r] - s[l-1]);
        }
        writer.flush();
    }

}

双指针

BFS

广度优先搜索 教程

package com.item.action;

import java.util.LinkedList;
import java.util.Queue;
 
public class Demo5 {
	/**
	 * 顶点
	 */
	public static int d[] = { 1, 2, 3, 4, 5, 6, 7 };
	/**
	 * 图转换数组
	 */
	public static int[][] arr= {
			{0,1,0,0,0,1,0},
			{1,0,1,1,0,0,0},
			{0,1,0,0,0,0,0},
			{0,1,0,0,1,0,0},
			{0,0,0,1,0,0,0},
			{1,0,0,0,0,0,1},
			{0,0,0,0,0,1,0},
	};
	/**
	 * 顶点长度
	 */
	public static int d_length=d.length;
	/**
	 * 记录每一个节点的遍历过程，走过则记录为true
	 */
	public static boolean[] isfStatus;
	
    /**
          * 队列完成的广度搜索
     */
    private static void BFS() {
    	isfStatus = new boolean[d_length];
        Queue<Integer> temp = new LinkedList<Integer>();
        //遍历每个节点
        for (int i = 0; i < d_length; i++) {
        	//判断当前节点是否被访问过
            if (!isfStatus[i]) {//如果没有被访问的话则将其加入队列
                System.out.print(d[i] + " ");
                isfStatus[i] = true;
                temp.offer(i);
                while (!temp.isEmpty()) {
                	//将最先进入队列的节点移除
                    int j = temp.poll();
                    //广度搜索子节点
                    for (int k = firstValue(j); k >= 0; k = nextValue(j, k)) {
                        if (!isfStatus[k]) {
                            System.out.print(d[k] + " ");
                            isfStatus[k] = true;
                            temp.offer(k);
                        }
                    }
                }
            }
        }
    }
    // 返回与i相连的第一个顶点
    private static int firstValue(int i) {
        for (int j = 0; j < d_length; j++) {
            if (arr[i][j] > 0) {
                return j;
            }
        }
        return -1;
    }
    // 返回与i相连的下一个顶点
    private static int nextValue(int i, int j) {
        for (int k = (j + 1); k < d_length; k++) {
            if (arr[i][k] > 0) {
                return k;
            }
        }
        return -1;
    }
 
    // 测试
    public static void main(String args[]) {
        BFS();
    }
}

DFS

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Arrays;

class Main{
    static int n;
    static boolean[] state = new boolean[10];
    
    static int[] path = new int[10];
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        Arrays.fill(state, false);
        n = Integer.parseInt(reader.readLine());
        dfs(0);
    }
    static void dfs(int u) {
        if(u == n) {
            for (int i = 0; i < n; i ++ ) {
                writer.printf("%d",path[i]);
                if (i == n - 1) {
                    writer.println();
                } else {
                    writer.print(" ");
                }
            }
            writer.flush();
        }
        for(int i = 1; i <= n; i++) {
            if (!state[i]) {
                path[u] = i;
                state[i] = true;
                dfs(u + 1);
                state[i] = false;
            }
        }
    }

}

贪心

快速幂

并查集

常见问题与坑

骗分技巧

直接输出答案

System.out.println("题目后面给的答案或者不存在的情况")

随机输出

public class Main {
    public static void main(String[] args) {
        int randomNumber = (int) (Math.random() * X); // 生成一个0到X-1的随机整数
        System.out.println(randomNumber);
    }
}

根据题目规律猜答案