Java算法竞赛常用模板

2021-02-10  本文已影响0人  眼若繁星丶

Java算法竞赛常用模板

一、输入输出

简单输入

import java.util.Scanner 
import java.io.BufferedInputStream;

Scanner sc1 = new Scanner(System.in);
Scanner sc2 = new Scanner(new BufferedInputStream(System.in));
// sc2用到缓冲流，读入更快

测试：

public static void main(String[] args) {
        long t1, t2, t3;
        Scanner sc1 = new Scanner(System.in);
        Scanner sc2 = new Scanner(new BufferedInputStream(System.in));

        t1 = System.nanoTime();
        String next = sc1.next();
        t2 = System.nanoTime();
        t3 = t2 - t1;
        System.out.println("sc1:" + t3);
        System.out.println(next);

        t1 = System.nanoTime();
        String next2 = sc2.next();
        t2 = System.nanoTime();
        t3 = t2 - t1;
        System.out.println("sc2:" + t3);
        System.out.println(next2);
    }

abc
sc1:7968695900
abc
abc
sc2:1945031900
abc

复杂输入

    如：1,2,3,4,5

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.next();
    String[] split = str.split(",");
    int[] strInt = new int[split.length];
    for (int i = 0; i < split.length; i++) {
        strInt[i] = Integer.parseInt(split[i]);
    }
    System.out.println(Arrays.toString(strInt));
}

1,2,3,4,5
[1, 2, 3, 4, 5]

文件输入

    用于大数据的读入，不用手动输入那么麻烦。BufferedInputStream缓冲流来加速，文件输入流用**绝对路径**，避免不必要的麻烦，要不就把资源文件放在src目录下。

public static void main(String[] args) throws FileNotFoundException {
    Scanner sc = new Scanner(new BufferedInputStream(new 
    FileInputStream("E:\\input.txt")));
    List<Integer> list = new ArrayList<>();
    while (sc.hasNext()) {
        list.add(sc.nextInt());
    }
    System.out.println(list);
}

二、数据类型

字符串

String[] s=str.split(" +");
String[] s=str.split("\\s+");
// 以一个或多个空格分割

String ss=str.replaceAll(" +", ",");
String ss=str.replaceAll("\\s+", ",");
// 二者都能把一个或多个空格换成逗号

大数

//BigDecimal类型构造方法
BigDecimal(double val)
          //将 double 转换为 BigDecimal，后者是 double 的二进制浮点值准确的十进制表示形式。
BigDecimal(int val)
          //将 int 转换为 BigDecimal。
BigDecimal(long val)
          //将 long 转换为 BigDecimal。
BigDecimal(String val)
          //将 BigDecimal 的字符串表示形式转换为 BigDecimal。
//BigInteger类型构造方法
BigInteger(int val)
          //将 int 转换为 BigInteger。
BigInteger(String val)
          //将 BigDecimal 的字符串表示形式转换为 BigInteger。
//BigInteger转换方法
BigInteger valueOf(long val)
          //返回其值等于指定 long 的值的 BigInteger。
          //如：BigInteger bi1=new BigInteger(1000);
//通用方法
BigInteger(BigDecimal).max(BigInteger(BigDecimal))
    //返回最大数
BigInteger(BigDecimal).min(BigInteger(BigDecimal))
    //返回最小数
BigInteger(BigDecimal).add(BigInteger(BigDecimal))
    //相当于：+
BigInteger(BigDecimal).subtract(BigInteger(BigDecimal))
    //相当于：-
BigInteger(BigDecimal).multiply(BigInteger(BigDecimal))
    //相当于：*
BigInteger(BigDecimal).divide(BigInteger(BigDecimal))
    //相当于：/
BigInteger(BigDecimal).mod(BigInteger(BigDecimal))
    //相当于：%
BigInteger(BigDecimal).abs()
    //返回其值是此 BigIntege(BigDecimal)r 的绝对值的 BigInteger(BigDecimal)。

Calendar类

Calendar calendar = Calendar.getInstance();

public static final int SUNDAY = 1;

public static final int JANUARY = 0;

以上表示，一周的开始是周日，即为1，以此类推。

一年的开始是一月，即为0，所以对月的设置要 - 1，对月的读取要 + 1

    `get(int field); `// 获取给定字段的值，field即上面的字段数字

Calendar calendar = Calendar.getInstance();
// 设置日期为: 2020.1.21
calendar.set(Calendar.YEAR, 2020);
calendar.set(Calendar.MONTH, 0);
calendar.set(Calendar.DAY_OF_MONTH, 21);
// 获取2020.1.21是星期几
System.out.print(calendar.get(Calendar.DAY_OF_WEEK));

输出：
3 // 3代表星期二

Calendar类与Date类的转换

Calendar cal = Calendar.getInstance();
Date date = cal.getTime();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd");
String s = simpleDateFormat.format(date);
System.out.println("时间为===="+s);

Date date2 = new Date();
Calendar cal2 = Calendar.getInstance();
cal2.setTime(date2);
System.out.println(cal2.get(Calendar.YEAR) +"-"+(cal2.get(Calendar.MONTH)+1)+"-"+cal2.get(Calendar.DATE));

例题：

从键盘输入一个日期，格式为yyyy-M-d

要求计算该日期与1949年10月1日距离多少天

例如：

用户输入了：1949-10-2 程序输出：1

用户输入了：1949-11-1 程序输出：31

public static void main(String[] args) {
        Calendar cal = Calendar.getInstance();
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        String s = sc.next();
        String[] str = s.split("-");
        cal.set(Integer.parseInt(str[0]), Integer.parseInt(str[1]) - 1, Integer.parseInt(str[2]));
        Calendar standard = Calendar.getInstance();
        standard.set(1949, 10 - 1, 1);
        long t1 = cal.getTimeInMillis();
        long t2 = standard.getTimeInMillis();
        System.out.println((t1 - t2) / (1000 * 60 * 60 * 24) + 1);
    }

双端队列

    定义：（常用）

Deque<Integer> q=new LinkedList<Integer>();

LinkedList底层是链表，ArrayDeque底层是数组实现

进制转换

其他进制字符串->十进制整数

System.out.println(Integer.valueOf(12));//12
 
// 十进制字符串 => 十进制整数
System.out.println(Integer.valueOf("12"));//12
System.out.println(Integer.valueOf("12",10));//12
 
// 二进制字符串 => 十进制整数
System.out.println(Integer.valueOf("1100", 2));//12
 
// 8进制字符串 => 十进制整数
System.out.println(Integer.valueOf("1100", 8));//576
 
// 16进制字符串 => 十进制整数
System.out.println(Integer.valueOf("1100", 16));//4352

同理，用 public static int parseInt(String s)或 public static int parseInt(String s, int radix)转换为int型

// 十进制字符串 => 十进制整数
System.out.println(Integer.parseInt("12")); // 12
System.out.println(Integer.parseInt("12", 10)); // 12
 
// 二进制字符串 => 十进制整数
System.out.println(Integer.parseInt("1100", 2)); // 12
 
// 8进制字符串 => 十进制整数
System.out.println(Integer.parseInt("1100", 8)); // 576
 
// 16进制字符串 => 十进制整数
System.out.println(Integer.parseInt("1100", 16)); // 4352
 
// 32进制字符串 => 十进制整数
System.out.println(Integer.parseInt("1100", 32)); // 33792

十进制整数->其他进制字符串

int n = 12;
// 十进制整数 -> 十进制字符串
System.out.println(Integer.toString(n));// 12
 
// 十进制整数 -> 二进制字符串
System.out.println(Integer.toString(n, 2));// 1100
 
// 十进制整数 -> 8进制字符串
System.out.println(Integer.toString(n, 8));// 14
 
// 十进制整数 -> 16进制字符串
System.out.println(Integer.toString(n, 16));// c
 
// 十进制整数 -> 32进制字符串
System.out.println(Integer.toString(n, 32));// c

自定义排序

public static void main(String[] args) {
    String[] arr = new String[] {"3", "22", "1111"};
    // 按照长度降序
    Arrays.sort(arr, (s1, s2) -> {
        return s2.length() - s1.length();
    });
    System.out.println(Arrays.toString(arr));
}

数组求和

int[] array = new int[]{1,2,3};
Arrays.stream(array).sum();
上一篇 下一篇

猜你喜欢

热点阅读