前言：笔者在这段时间准备蓝桥杯竞赛，由于个人原因选择Java作为语言，刷题中也是不断感到Java有些语法还是不够方便（非常羡慕隔壁C++的STL…），不过有些常见的技巧/方法/模板，也是自己做了些总结，十分之不全面，比完赛会继续完善…
！！！！！提交结果时记得检查有无不该加的头文件，主类名是否为Main！！！！！！
2.优化输入输出时间（快速IO模板）：
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
InputReader in = new InputReader();
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
out.close();
}
static class InputReader{
private StringTokenizer st;
private BufferedReader bf;
public InputReader() {
bf = new BufferedReader(new InputStreamReader(System.in));
st = null;
}
public String next() throws IOException{
while(st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
public String nextLine() throws IOException{
return bf.readLine();
}
public int nextInt() throws IOException{
return Integer.parseInt(next());
}
public long nextLong() throws IOException{
return Long.parseLong(next());
}
public double nextDouble() throws IOException{
return Double.parseDouble(next());
}
public BigInteger nextBigInteger() throws IOException{
return new BigInteger(next());
}
public BigDecimal nextBigDecimal() throws IOException{
return new BigDecimal(next());
}
}
}
3.快速幂模板
long long FastPower(long long base, long long power) { //a是底数，b是幂数，ans是结果
long long result= 1;
while(power > 0) {
if(power & 1 != 0) {
result*= base;
}
base *= base;
b >>= 1;
}
return result;
}
4.自定义类排序
例如：
public class Main {
static class Point{
double x;
double y;
public Point() {}
public Point(double x, double y){
this.x = x;
this.y = y;
}
}
public static double INF = 2 << 19;
static InputReader in;
static PrintWriter out;
public static int n;
public static double dist(Point a, Point b) {
double aa = Math.pow(a.x - b.x, 2);
double bb = Math.pow(a.y - b.y, 2);
return Math.sqrt(aa + bb);
}
public static double merge(Point[] point, int left, int right) {
double d = INF;
if(left >= right)
return d;
if(left + 1 == right)
return dist(point[left], point[right]);
int mid = (left + right) >> 1;
double d1 = merge(point, left, mid);
double d2 = merge(point, mid+1, right);
d = Math.min(d1, d2);
int i, j, k = 0;
ArrayList<Point> tem = new ArrayList<>();
for(i = left; i <= right; ++i) {
if(Math.abs(point[mid].x - point[i].x) <= d) {
tem.add(point[i]);
k++;
}
}
Collections.sort(tem, new Comparator<Point>() {
@Override
public final int compare(Point pFirst, Point pSecond) {
if(pFirst.y < pSecond.y)
return -1;
if(pFirst.y > pSecond.y)
return 1;
if(pFirst.x < pSecond.x)
return -1;
if(pFirst.x > pSecond.x)
return 1;
return 0;
}
});
for(i = 0; i < k; i++) {
for(j = i + 1; j < k && (tem.get(j).y - tem.get(i).y) < d; j++) {
double d3 = dist(tem.get(j), tem.get(i));
if(d3 < d) d = d3;
}
}
return d;
}
public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
n = in.nextInt();
Point[] point = new Point[n];
for(int i = 0; i < n; i++) {
double x = in.nextDouble();
double y = in.nextDouble();
point[i] = new Point(x, y);
}
Arrays.sort(point, new Comparator<Point>() {
@Override
public int compare(Point pFirst, Point pSecond) {
if(pFirst.x < pSecond.x)
return -1;
if(pFirst.x > pSecond.x)
return 1;
if(pFirst.y < pSecond.y)
return -1;
if(pFirst.y > pSecond.y)
return 1;
return 0;
}
});
System.out.printf("%.4f", merge(point, 0, n-1));
}
5.归并排序模板
void sort_change(int l,int mid,int r){
//排序部分，把大区间再次分成小区间排序
int k1=l,k2=mid+1,k=l;
//初始化三个指针，一个指左区间左端点，一个指右区间左端点，一个指最终答案区间的左端点
while(k1<=mid&&k2<=r){
if(a[k1]>a[k2]){
temp[k]=a[k2];
k++,k2++;
}
else{
temp[k]=a[k1];
k++,k1++;
}
//每次取两个区间中最小的数字加入答案,指针右移
}
while(k1<=mid){
temp[k]=a[k1];
k++,k1++;
}//如果右区间的数字已经取完了，将左区间剩余数字按照一样从小到大的顺序放入答案
while(k2<=r){
temp[k]=a[k2];
k++,k2++;
}//如果左区间的数字已经取完了，将右区间剩余数字按照一样从小到大的顺序放入答案
for(int i=l;i<=r;i++) a[i]=temp[i];//将储存答案的数组的值赋回原来的数组
}
void sort_re(int l,int r){
if(l>=r) return ;//如果该区间不满足条件，即左边在右边的右边，return
int mid=(l+r)/2;//二分思想
sort_re(l,mid);//给左子区间排序
sort_re(mid+1,r);//给右子区间排序
sort_change(l,mid,r);//保证左右子区间排列得整整齐齐之后，才能并起来
//将大区间化成小区间然后排序
}
6.Int, Integer等数组类型转换
int[] data = {1,2,3};
// int[]转List<Integer>
// Arrays.stream(data): int[] -> IntStream
// IntStream.boxed(): IntStream -> Stream<Integer>
// Stream<Integer>.collect(Collectors.toList()): Stream<Integer> -> List<Integer>
List<Integer> list1 = Arrays.stream(data).boxed().collect(Collectors.toList());
// int[]转Integer[]
Integer[] arr1 = Arrays.stream(data).boxed().toArray(Integer[]::new);
// List<Integer>转int[]
// Collection<Integer>.stream(): Collection<Integer> -> Stream<Integer>
// Stream<Integer>.mapToInt(Integer::intValue): Stream<Integer> -> IntStream
// IntStream.toArray(): IntStream -> int[]
int[] arr2 = list1.stream().mapToInt(Integer::intValue).toArray();
// List<Integer>转Integer[]
Integer[] arr3 = list1.toArray(new Integer[0]);
// Integer[]转List<Integer>
List<Integer> list2 = Arrays.asList(arr3);
// Integer[]转int[]
int[] arr4 = Arrays.stream(arr1).mapToInt(Integer::valueOf).toArray();
7.sort降序排序
Integer[] arr={9,8,7,6,5,4,3,2,1};
Arrays.sort(arr,Collections.reverseOrder());
或
Integer[] arr={9,8,7,6,5,4,3,2,1};
Comparator cmp=new CMP();
Arrays.sort(arr,cmp);
class CMP implements Comparator<Integer>{
@Override //可以去掉。作用是检查下面的方法名是不是父类中所有的
public int compare(Integer a,Integer b){
// 升序排序的话反过来就行
return b-a;
}
或
List<Integer> integersList = Ints.asList(array);
Collections.reverse(integersList);//冒泡交换
System.out.println("Guava降序输出：");
for (int num : integersList) {
System.out.println(num);
}
或利用二维数组的自定义排序，如下：
int[][] arr = new int[3][2];
arr[0][0] = 5;
arr[0][1] = 3;
arr[1][0] = 1;
arr[1][1] = 4;
arr[2][0] = 6;
arr[2][1] = 2;
Arrays.sort(arr, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0]-b[0];
}
});
即按第一列升序排序：
1,4
5,3
6,2
8.高精度运算
1.valueOf(parament); 将参数转换为制定的类型
比如 int a=3;
BigInteger b=BigInteger.valueOf(a);
则b=3;
String s=”12345”;
BigInteger c=BigInteger.valueOf(s);
则c=12345；
2.add(); 大整数相加
BigInteger a=new BigInteger(“23”);
BigInteger b=new BigInteger(“34”);
a.add(b);
3.subtract(); 相减
4.multiply(); 相乘
5.divide(); 相除取整
6.remainder(); 取余
7.pow(); a.pow(b)=a^b
8.gcd(); 最大公约数
9.abs(); 绝对值
10.negate(); 取反数
11.mod(); a.mod(b)=a%b=a.remainder(b);
12.max(); min();
13.public int compareTo();
14.boolean equals(); 是否相等
15.BigInteger构造函数：
一般用到以下两种：
BigInteger(String val);
将指定字符串转换为十进制表示形式；
BigInteger(String val,int radix);
将指定基数的 BigInteger 的字符串表示形式转换为 BigInteger
int n;
BigInteger m;
n=cin.nextInt(); //读入一个int;
m=cin.nextBigInteger();//读入一个BigInteger;
- 前缀和/差分及其性质
（1）一维前缀和：
预处理：定义一个sum[]数组，sum[i]代表a数组中前i个数的和。
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
查询a数组中第left个数到第right个数的和：
sum[r]-sum[l-1]
（原理：
sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];
sum[l-1]=a[1]+a[2]+a[3]+a[l-1];
sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];
）
（2）二维前缀和：
预处理：
s[i] [j] = s[i-1][j] + s[i][j-1 ] + a[i] [j] - s[i-1][ j-1]
结论：
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]
差分：若a数组为b数组的前缀和数组，则b数组为a的差分数组
例如：a[i] = b[1] + b[2 ]+ b[3] +......+ b[i]
则：b[n] = a[n] - a[n-1];
若求对a数组中 [left，right] 区间每个数加上c，只需：
b[left] += c , b[right+1] -= c
二维差分：
构造差分数组：b[i][j]=a[i][j]?a[i?1][j]?a[i][j?1]+a[i?1][j?1]
求以（x1, y1)为左上角，（x2, y2)为右下角的子矩阵中所有元素加c，则：
b[x1,y1] += c;
b[x2+1, y1] -= c;
b[x1, y2+1] -= c;
b[x2+1, y2+1] += c;
10.最大公约数/最小公倍数
最大公约数：
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
最小公倍数：
两数乘积除以最大公约数
11.二分答案的两个模板：
（1）（最大值最小化）：
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))
{
r=mid;
}
else
{
l=mid+1;
}
}
（2）（最小值最大化）：
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
12.TreeSet找比某个数大 / 小的数
小于 lower
小于等于 floor
大于等于 ceiling
大于 higher
13、 KMP算法
（2）求next数组：
void GetNext(char T[])
{
int j=0,k=-1;
next[j]=k;
while(T[j]!='\0')
{
if(k==-1||T[j]==T[k])
{
j++;
k++;
next[j]=k;
}
else k=next[k];
}
}
（2）KMP主程序：
int KMP(char S[], char T[]) //KMP算法, S为主串，T为字串
{
int next[MaxSize],i=0,j=0;
GetNext(char T[]);
while (i<s.length && j<t.length)
{
if (j==-1 || s.data[i]==t.data[j])
{
i++;j++; //i,j各增1
}
else j=next[j]; //i不变,j后退，现在知道为什么这样让子串回退了吧
}
if (j>=t.length)
return(i-t.length); //返回匹配模式串的首字符下标
else
return(-1); //返回不匹配标志
}
14.线段树（模板题可至洛谷）：
（1）单点修改+区间查询（求区间和）（P3374）：
static long search(int i, int l, int r) {
if(tree[i].l >= l && tree[i].r <= r) {
return tree[i].sum;
}
if(tree[i].r < l || tree[i].l > r) {
return 0;
}
int sum = 0;
int mid = (tree[i].l + tree[i].r) >> 1;
if(tree[i].l <= mid) sum += search(i*2, l, r);
if(tree[i].r > mid) sum += search(i*2+1, l, r);
return sum;
}
static void add(int i, int x, long k) {
if(tree[i].l == tree[i].r) {
tree[i].sum += k;
return;
}
int mid = (tree[i].l + tree[i].r) >> 1;
if(x <= mid) add(i*2, x, k);
else add(i*2+1, x, k);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
return;
}
(2).区间修改+单点查询（P3368）（注：涉及区间修改的，要带懒标记（往往能用到））
void push_down(int i)
{
if(tree[i].lazy != 0)
{
tree[i << 1].lazy += tree[i].lazy;
tree[i << 1 | 1].lazy += tree[i].lazy;
int mid = (tree[i].l + tree[i].r) >> 1;
tree[i << 1].sum += tree[i].lazy * (mid - tree[i << 1].l + 1);
tree[i << 1 | 1].sum += tree[i].lazy * (tree[i << 1 | 1].r - mid);
tree[i].lazy = 0;
}
return;
}
void add(int i, int l, int r, int k)
{
if(tree[i].l >= l && tree[i].r <= r)
{
tree[i].sum += k * (tree[i].r - tree[i].l + 1);
tree[i].lazy += k;
return;
}
push_down(i);
int mid = (tree[i].l + tree[i].r) >> 1;
if(l <= mid) add(i*2, l, r, k);
if(r > mid) add(i*2+1, l, r, k);
tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
return;
}
ll search(int i, int x)
{
if(tree[i].l == x && tree[i].r == x)
{
return tree[i].sum;
}
push_down(i);
int mid = (tree[i].l + tree[i].r) >> 1;
if(x <= mid) return search(i*2, x);
else return search(i*2+1, x);
}
（3）区间修改+区间查询（P3372）：
static class Tree{
int l, r;
long sum, lazy;
}
static Tree[] tree;
static long[] input;
static void build(int i, int l, int r) {
tree[i] = new Tree();
tree[i].l = l;
tree[i].r = r;
tree[i].lazy = 0;
if(l == r) {
tree[i].sum = input[l];
return;
}
int mid = (l + r) >> 1;
build(i*2, l, mid);
build(i*2+1, mid+1, r);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
}
static long search(int i, int l, int r) {
if(tree[i].l >= l && tree[i].r <= r) {
return tree[i].sum;
}
if(tree[i].r < l || tree[i].l > r) {
return 0;
}
push_down(i);
long sum = 0;
if(tree[i*2].r >= l) {
sum += search(i*2, l, r);
}
if(tree[i*2+1].l <= r) {
sum += search(i*2+1, l, r);
}
return sum;
}
static void add(int i, int l, int r, long k) {
if(tree[i].l >= l && tree[i].r <= r) {
tree[i].sum += k*(tree[i].r - tree[i].l + 1);
tree[i].lazy += k;
return;
}
push_down(i);
if(tree[i*2].r >= l) add(i*2, l, r, k);
if(tree[i*2+1].l <= r) add(i*2+1, l, r, k);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
return;
}
static void push_down(int i) {
if(tree[i].lazy != 0) {
tree[i << 1].lazy += tree[i].lazy;
tree[i << 1 | 1].lazy += tree[i].lazy;
int mid = (tree[i].l + tree[i].r) >> 1;
tree[i << 1].sum += tree[i].lazy*(mid - tree[i].l + 1);
tree[i << 1 | 1].sum += tree[i].lazy*(tree[i].r - mid);
tree[i].lazy = 0;
}
return;
}
15.全排列：
static void fullSort(int[] arr, int start, int end) {
// 递归终止条件
if (start == end) {
.........
return;
}
for (int i = start; i <= end; i++) {
swap(arr, i, start);
fullSort(arr, start + 1, end);
swap(arr, i, start);
}
}
static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
16.关于求对数
（详解参见以下博客）
https://blog.csdn.net/xiaojin21cen/article/details/98944689?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165311820516781683965191%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=165311820516781683965191&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allbaidu_landing_v2~default-3-98944689-null-null.142v10control,157v4control&utm_term=java%E6%B1%82%E5%AF%B9%E6%95%B0&spm=1018.2226.3001.4187
总结：
X^Y = N 转化为 logxN = Y 转化为 logxN = Math.log(N) / Math.log(a)
