@[toc]

算法竞赛题目的类型

主要分为核心代码模式以及ACM模式，前者就是只需要实现对应的功能函数关注函数传入的参数值以及我们需要返回的结果集即可，后者则需要我们从main方法开始完整的从读入开始截至最后的输出。

• 核心代码模式：力扣。
• ACM模式：蓝桥杯、ACM竞赛。

上案例题，斐波那契数列：

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

核心代码模式

我们来看下力扣的一道题509. 斐波那契数：右边是已经给我们写好了的相应函数，我们只需要完成函数功能方法即可（函数名、结果类型、参数类型不能变，参数名称可以改）：

• 为什么参数名称可以改？因为你写完的程序发送到服务器，服务器会有一个事先写好的main方法去调用你这个fib()函数，这样你就可以想得通为什么参数名称是可以修改的了。

class Solution {
    public int fib(int n) {
        int[] dp = new int[33];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    } 
}

ACM模式

相应竞赛：蓝桥杯

给出题目以及相应的输入、输出案例，然后不会给你任何代码，让你从头文件开始去写输入、功能函数以及最后的输出。

案例题我们来看Acwing网站上的 21. 斐波那契数列：所有的代码都需要自己去实现包括导包

import java.util.*;
import java.io.*;

class Main {
    
    static long[] fn = new long[65];
    static int count, n;
    
    public static void main (String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        count = Integer.parseInt(cin.readLine());
        while (count != 0) {
            n = Integer.parseInt(cin.readLine());
            //斐波那契递推
            fn[1] = 1;
            fn[2] = 1;
            for (int i = 3; i <= n; i++) 
                fn[i] = fn[i - 1] + fn[i - 2];
            System.out.printf("Fib(%d) = %s\n", n, Long.valueOf(fn[n]));
            count--;
        }
    }
}

---

Java的输入与输出

输入

方式一：借助Scanner函数（输入数据量少推荐使用）

若是数据是固定的就几个推荐使用Scanner，因为比较方便可以直接使用nextInt()得到指定类型的值。

例如 1214. 波动数列：

输入格式
共一行，包含四个整数 n,s,a,b，含义如前面所述。

分析：类似于这种固定几个数字的，我们就可以使用Scanner来直接得到值。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        s = cin.nextInt();
        a = cin.nextInt();
        b = cin.nextInt();
    }
}

方式二：使用BufferedReader函数（输入数据量大推荐使用，效率更高）

说明：推荐使用Integer.parseInt来进行转int类型数据。

举例：1015. 摘花生的输入案例

题库输入描述：
第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输入举例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

分析：对于这类不是固定的数据长度，可能会根据T组会有很大很大的读入操作，此时更推荐使用BufferedReader而不是Scanner！

首先用Scanner熟悉下写如下，仅仅只是为了演示：

//Scanner属于java.util包下
import java.util.*;

class Main {
    
    static final int N = 1010;
    static int count, m, n;
    static int arr[][] = new int[N][N];
    
	public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        //int num = cin.nextInt() 可通过'空格'或换行'\n'来作为分割读取一个整型数据
        //long num = cin.nextLong();
        //通用方法使用cin.nextLine();读取一行，然后去使用split(" ")来进行分隔成一个数组
        count = Integer.parseInt(cin.nextLine());
        while (count != 0) {
            String[] s = cin.nextLine().split(" ");
            n = Integer.parseInt(s[0]);
            m = Integer.parseInt(s[1]);
            //读取每行每列
            for (int i = 0; i < n; i++){
                s = cin.nextLine().split(" ");
                for (int j = 0; j < m; j++) {
                    arr[i][j] = Integer.parseInt(s[j]);
                }
            }
            //业务处理，针对于int [][]arr
            //************
            printAll(n, m);//测试读入的数据
            //************
            count--;
        }
    }
    
    //辅助：额外的
    public static void printAll (int n, int m) {
        System.out.printf("n = %d\n", n);
        System.out.printf("m = %d\n", m);
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++) {
                System.out.printf("%d ", arr[i][j]);
            }
            System.out.println();
        }
        System.out.printf("*****************\n");
    }

}

接下来使用BufferedReader，BufferedReader实际上与Scanner大差不差，我来写出相应的不同处：

//替换一：Scanner cin = new Scanner(System.in);
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));

//替换二：cin.nextLine()
cin.readLine()
    
//替换三：import java.util.*;
import java.io.*;

还有就是在main方法外抛出异常：

throws Exception

其他几乎都是一模一样，下面给出完整代码：

package com.changlu.java;

import java.io.*;

public class Test {
    static final int N = 1010;
    static int count, m, n;
    static int arr[][] = new int[N][N];

    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        count = Integer.parseInt(cin.readLine());
        while (count != 0) {
            String[] s = cin.readLine().split(" ");
            n = Integer.parseInt(s[0]);
            m = Integer.parseInt(s[1]);
            //读取每行每列
            for (int i = 0; i < n; i++){
                s = cin.readLine().split(" ");
                for (int j = 0; j < m; j++) {
                    arr[i][j] = Integer.parseInt(s[j]);
                }
            }
            //业务处理，针对于int [][]arr
            //************
            printAll(n, m);//测试读入的数据
            //************
            count--;
        }
    }


    //辅助：额外的
    public static void printAll (int n, int m) {
        System.out.printf("n = %d\n", n);
        System.out.printf("m = %d\n", m);
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++) {
                System.out.printf("%d ", arr[i][j]);
            }
            System.out.println();
        }
        System.out.printf("*****************\n");
    }

}

---

实战选择案例

BufferedReader适用于所有输入场景。最佳选择如下：

输入数据量很小，一般确定几个值选择使用Scanner，可以直接接收指定类型数据方便。

数据数据量由N决定，不确定长度或者数量特别多，就选择使用BufferedReader。

这里使用acwing的一道题来进行测试：1236. 递增三元组

读题的输入案例：

输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…AN。
第三行包含 N 个整数 B1,B2,…BN。
第四行包含 N 个整数 C1,C2,…CN。

1≤N≤105,
0≤Ai,Bi,Ci≤105

可以看到该题最佳选择输入的函数应该是BufferedReader，因为输入的数据量很大，完全是由N决定，我们来测试一下效果：

①使用Scanner

import java.util.*;

class Main {
    
    static final int N = 100010;
    static int n;
    static int[][] arr = new int[3][N];

    public static void main(String[] args){
        //读入数据
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = cin.nextInt();
            }
        }
        //排序
        Arrays.sort(arr[0], 0, n);
        Arrays.sort(arr[1], 0, n);
        Arrays.sort(arr[2], 0, n);
        long ans = 0;
        int a = 0, c = 0;
        //以B数组的所有数据作为基准
        for (int i = 0; i < n; i++) {
            int target = arr[1][i];
            while (a < n && arr[0][a] < target) a++;
            while (c < n && target >= arr[2][c]) c++;
            //其中n - c一定要添加long来进行转换，否则就会当成int类型来计算
            ans += (long)(a * (long)(n - c));
        }
        System.out.println(ans);
    }
}

②使用BufferedReader

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 100010;
    static int n;
    static int[][] arr = new int[3][N];

    public static void main(String[] args) throws Exception{
        //读入数据
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(cin.readLine());
        for (int i = 0; i < 3; i++) {
            String[] s = cin.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(s[j]);
            }
        }
        //排序
        Arrays.sort(arr[0], 0, n);
        Arrays.sort(arr[1], 0, n);
        Arrays.sort(arr[2], 0, n);
        long ans = 0;
        int a = 0, c = 0;
        //以B数组的所有数据作为基准
        for (int i = 0; i < n; i++) {
            int target = arr[1][i];
            while (a < n && arr[0][a] < target) a++;
            while (c < n && target >= arr[2][c]) c++;
            //其中n - c一定要添加long来进行转换，否则就会当成int类型来计算
            ans += (long)(a * (long)(n - c));
        }
        System.out.println(ans);
    }
}

结论：可以看到仅仅对于输入量特别大的案例，选择一个合适的输入函数可以节省几秒，请务必重视你的输入函数选择！！！

输出

方式一：采用System.out.printf()（输出数据量少可使用）

输出案例：741. 斐波那契数列

输出样例：
Fib(0) = 0
Fib(4) = 3
Fib(2) = 1

有些使用输出不仅仅让我们输出结果，可能会让我们输出相应的结果式子，一般使用的System.out.printf()以及System.out.println()

System.out.printf() //这个printf跟c语言的效果一致，如printf("%d", 123)

System.out.println() //使用这个println()就不能写表达式了，输出后会自带一个\n

根据样例来编写代码：

class Main {
    public static void main(String[] args) {
        System.out.printf("Fib(%d) = %d\n", 0, 0);
        //下面两条等价于 => System.out.printf("Fib(%d) = %d\n", 4, 3);
        System.out.printf("Fib(%d) = %d", 4, 3);
        System.out.println();
        System.out.printf("Fib(%d) = %d\n", 2, 1);
    }
}

方式二：采用PrintWriter（输出数据量大推荐使用）

简单示例

注意：在进行printf等其他输出函数后(可多条)，最终一定要执行flush，才能够打印到控制台上。

class Main {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        out.printf("%d\n", 123);
        out.flush();//刷新流
	}
}

对应PrintWriter对象的实例方法如下，基本上与方式一的System.out一致：

实战案例场景

这里拿一个acwing题目来进行举例：1265. 数星星

题目中需要让我们输出N个数，这个N的范围为1≤N≤15000，十分大，若是使用System.out.printf来进行输出就会超时：

我们将System.out.printf替换为PrintWriter并且使用println()来进行输出，就能够通过了：

这里给出示例代码，小伙伴们也可以去尝试一下：

import java.util.*;
import java.io.*;

class Main {
    
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static final int N = 32010;
    static int n;
    //树状数组、索引数组
    static int[] tr = new int[N], index = new int[N];
    
    public static int lowbit(int x) {
        return x & -x;
    }
    
    //在x位置+1
    public static void add(int x) {
        for (int i = x; i < N; i += lowbit(i)) {
            tr[i]++;
        }
    }
    
    //计算前缀和
    public static int sum(int x) {
        int ret = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            ret += tr[i];
        }
        return ret;
    }
    
    
    public static void main (String[] args) throws Exception{
        n = Integer.parseInt(cin.readLine());
        for (int i = 0; i < n; i++) {
            String[] s = cin.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            x++;
            //统计星级的数量（统计出为0的数量）
            index[sum(x)]++;
            //再进行加1
            add(x);
        }
        for (int i = 0; i < n; i++) {
            //上面声明：static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
            //效率由高到低比较：
            //[PrintWriter].println() > [PrintWriter].printf() > System.out.println() > System.out.printf()
            //经过测试：out.println(index[i]); 比 out.printf("%d\n", index[i])效率更高，后者在该题中也会超时。
            out.println(index[i]);
        }
        out.flush();
    }
}

---

Java读取文件

实际习题（填空题）：蓝桥杯题解 寻找2020 Java答案、第十一届蓝桥杯JavaB组试题B：寻找2020（2020.txt文件）

//填写绝对路径
FileReader fileReader = new FileReader("E:\\自学历程\\Gitee仓库\\demo-exer\\algorithm-java\\src\\main\\resources\\2020.txt");
//传入相应的FileReader即可
BufferedReader cin = new BufferedReader(fileReader);

//读取方式，与之前的一致
cin.readLine();

---

常用集合类

//数组拷贝
int[] arr = {1, 2, 3, 4};
int[] clone = arr.clone();
//数组排序，在区间进行排序[i, j]
Array.sort(clone, i, j + 1);

//转int型
Integer.parseInt("02") //2
//输出一个数字补0
printf("%02d", 1);//01

//Pair键值对
Pair<Integer, Integer> pair = new Pair<>(1, 2);
System.out.println(pair.getKey());
System.out.println(pair.getValue());

//唯一集合容器
Set<xx> t = new HashSet<xx>();          t.add(xx); [若是添加已经有，返回false]                t.contains(xx)

//栈集合                        查看栈顶元素值(有返回值)      入栈      栈是否为空        出栈(返回值)
Stack<xx> s  = new Stack<xx>();    s.peek()        s.push(xx);   s.isEmpty()     s.pop()

//动态数组集合（可动态扩容的一个数组）
List<Integer> list = new ArrayList<Integer>();    list.size();   list.get(i);

//链表集合
new LinkedList<Node>()    getFirst()    addFirst   removeLast()   isEmpty()

//双端队列
ArrayDeque<Integer> dq = new ArrayDeque<Integer>();  dq.pollLast();  dq.add(num[i]);  

//队列（链表集合中就有队列的实现）
Deque<TreeNode> queue = new LinkedList<>();   出队：queue.poll()  入队：queue.offer(node.left); 查看第一个：queue.peekFirst()  删除最后一个：queue.removeLast()

//哈希表
HashMap<Integer, Integer> map = new HashMap<>();   map.containsKey();

//优先队列 
PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->o2.compareTo(o1));

//集合转数组
String[] strArrayTrue = (String[]) arrayList.toArray(new String[0]);

//集合转数组：
ArrayList<Integer> res = new ArrayList<>();int[] ts = (int[])(res.toArray(new int[]));

//自定义比较器
compare()返回值：https://blog.csdn.net/weixin_44998686/article/details/109550175
return 0:不交换位置，不排序
return 1:交换位置
return -1:不交换位置
return o1-o2:升序排列
return o2-o1:降序排列

---

Java基本模板

在Java里，方法是从main函数开始运行的，main函数是静态方法，在算法竞赛里我们无需去new当前自己定义的class类名再去调用方法，一般情况都是直接定义static静态函数方法的，在main方法中可以直接进行调用：

模板：

import java.util.*;//包含常用的集合工具类如队列、动态数组、哈希表、栈
import java.io.*;//包含BufferedReader、InputStreamReader

class Main {
    
    //输入、输出函数
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    //定义公共变量一般就是我们需要读入的数据
    static final int N = 100000;//一般是给定题目的最大数据范围
    static int count, n, m;
    static int[][] arr = new int[N][N];
    
    public static void main(String[] args) {
        //读入
        String line = cin.readLine();
        String[] s = line.split(" ");
        
        //转Int：使用Integer.parseInt
        int n = Integer.parseInt(s[0]);
        
        //输出。一定要注意最后要带上out.flush()
        out.printf("%d\n", n);
        out.flush();
        
        //调用函数方法
        func1();
        func2();
    }
    
    public static void func1() {
        //功能1
    }
    
    public static void func2() {
        //功能2
    }
}