算法小技巧
1. 快读模板
面对大输入量的题目，使用常规的Scanner类来完成输入操作，就会出现超时或者超内存的情况，此时可以使用如下快读模板避免这一情况的发生。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
static class Read {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public int nextInt() throws Exception {
st.nextToken();
return (int) st.nval;
}
public long nextLong() throws Exception {
st.nextToken();
return (long) st.nval;
}
private static double nextDouble() throws IOException {
st.nextToken();
return (double) st.nval;
}
private static String next() throws IOException {
st.nextToken();
return st.sval;
}
}
}
2. 获取当前日期和时间
2.1. System.currentTimeMillis()
获取标准时间可以通过System.currentTimeMillis()方法获取，此方法不受时区影响，得到的结果是时间戳格式的。例如：
1543105352845
我们可以将时间戳转化成我们易于理解的格式
SimpleDateFormat formatter= new SimpleDateFormat("yyyy-MM-dd 'at' HH:mm:ss z");
Date date = new Date(System.currentTimeMillis());
System.out.println(formatter.format(date));
则该时间戳对应的时间为：
2021-8-4 at 00:22:12 CET
值得注意的是，此方法会根据我们的系统时间返回当前值，因为世界各地的时区是不一样的。
2.2. java.util.Date
在 Java 中，获取当前日期最简单的方法之一就是直接实例化位于 Java 包 java.util 的 Date 类。
Date date = new Date();
// this object contains the current date value
上面获取到的日期也可以被format成我们需要的格式，例如：
SimpleDateFormat formatter = new SimpleDateFormat("dd-MM-yyyy HH:mm:ss");
System.out.println(formatter.format(date));
2.3. Calendar API
Calendar 类，专门用于转换特定时刻和日历字段之间的日期和时间。
使用 Calendar 获取当前日期和时间非常简单：
Calendar calendar = Calendar.getInstance();
// get current instance of the calendar
与 date 一样，我们也可以非常轻松地 format 这个日期成我们需要的格式
SimpleDateFormat formatter = new SimpleDateFormat("dd-MM-yyyy HH:mm:ss");
System.out.println(formatter.format(calendar.getTime()));
上面代码打印的结果如下：
4-8-2021 00:27:20
2.4. Date/Time API
Java 8 提供了一个全新的 API，用以替换 java.util.Date 和 java.util.Calendar。Date / Time API 提供了多个类，帮助我们来完成工作，包括：
- LocalDate
- LocalTime
- LocalDateTime
- ZonedDateTime
2.4.1. LocalDate
LocalDate 只是一个日期，没有时间。 这意味着我们只能获得当前日期，但没有一天的具体时间。
LocalDate date = LocalDate.now(); // get the current date
我们可以 format 它。
DateTimeFormatter formatter = DateTimeFormatter.ofPattern("dd-MM-yyyy");
System.out.println(date.format(formatter));
得到的结果只有年月日，例如:
4-8-2021
2.4.2. LocalTime
LocalTime 与 LocalDate 相反，它只代表一个时间，没有日期。 这意味着我们只能获得当天的当前时间，而不是实际日期：
LocalTime time = LocalTime.now(); // get the current time
可以按如下方式 format。
DateTimeFormatter formatter = DateTimeFormatter.ofPattern("HH:mm:ss");
System.out.println(time.format(formatter));
得到的结果类似如下：
00:25:58
2.4.3. LocalDateTime
最后一个是 LocalDateTime，也是 Java 中最常用的 Date / Time 类，代表前两个类的组合 – 即日期和时间的值：
LocalDateTime dateTime = LocalDateTime.now(); // get the current date and time
format 的方式也一样。
DateTimeFormatter formatter = DateTimeFormatter.ofPattern("dd-MM-yyyy HH:mm:ss");
System.out.println(dateTime.format(formatter));
得到的日期结果类似于：
4-8-2021 00:27:20
3. 闰年判定
闰年：年份能够被4整除但不能被100整除或者能被400整除的为闰年。
bool isLeapYear(int n){
return n%400==0||(n%4==0&&n%100!=0);
}
4. 快速幂
我们虽然可以使用Java数学包下的Math.pow方法来求出x的n次幂的值，但这个函数本身运行起来是非常耗时的，对于我们需要参加竞赛的读者来说，无疑会让我们在超时的边缘徘徊，而快速幂可以通过将指数拆分成多个因数相乘的形式来简化幂运算，大大调高运算效率，可谓是我们的一大得力帮手！
快速幂算法是一种高效计算幂运算的方法，特别是在需要计算 (a^b) 的模 (n) 的结果时非常有用，即 (a^b \mod n)。这种方法通过将指数 (b) 表示为二进制形式，然后利用幂的性质来减少乘法运算的次数，从而加快计算速度。 快速幂算法的基本思想是将指数 (b) 分解为二进制形式，然后对于二进制表示中的每一个1，累乘底数 (a) 的相应幂次。每一步中，底数 (a) 都会被平方，这样可以减少乘法的次数。如果指数的二进制表示中某位是1，那么就将当前的 (a) 的幂乘到结果中。 下面是快速幂算法的一个简单实现，用于计算 (a^b \mod n)：
public class QuickPower {
public static long quickPow(long a, long b, long n) {
long res = 1;
// 对n取模，防止过程中出现大数
a %= n;
while (b > 0) {
if ((b & 1) == 1) {
res = (res * a) % n;
}
a = (a * a) % n;
b >>= 1;
}
return res;
}
public static void main(String[] args) {
// 底数
long a = 2;
// 指数
long b = 10;
// 模数
long n = 1000000007;
System.out.println("Result：" + quickPow(a, b, n));
}
}
5. 最大公约数
欧几里得算法：a与b的最大公约数等于b与a%b的最大公约数。
public static int gcd(int a,int b){
while(b!=0){
int temp=a;
a=b;
b=temp%b;
}
return a;
}
6. 最小公倍数
a与b的最大公约数与最小公倍数的乘积=a * b，所以最小公倍数=a*b/gcd(a,b)