蓝桥杯爪哇速通

简单题：枚举、找规律、模拟

复杂题：DP、图论、数论、二分、贪心

数据结构

1. 哈希表

分为HashSet和HashMap

Set set=new HashSet();set.add(1);//添加元素set.remove(1);//删除元素if(set.contains(1)) {...}//判断是否包含某个元素int len=set.size();//获得集合长度12345Map map=new HashMap();map.put("a", 1);int num1=map.get("a");int num2=map.getOrDefault("a",0);map.replace("a",2);map.remove("a");123456

2. 堆

使用优先队列(PriorityQueue)实现，默认是小根堆

(相关资料图)

Queue q=new PriorityQueue();//创建一个小根堆Queue q=new PriorityQueue((e1,e2)->e2-e1);//创建一个大根堆//(e1,e2)->e2-e1代表升序，可以自定义其他排序规则

时间相关

1. String转Date

import java.text.ParseException;import java.text.SimpleDateFormat;String s1 = "2021-7-24";String s2 = "2022-7-24";//yyyy-MM-dd，注意MM必须大写SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");// 转换成date1需要抛出异常try {    Date date1 = sdf.parse(s1);} catch (ParseException e) {    e.printStackTrace();}123456789101112

2. Date转String(标准格式化)

Date date = new Date(120000000);SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");System.out.println(sdf.format(date));123

3. Calender类（日历，星期）

Calender的月份MONTH是从0开始，也就是1-12月对应 0-11，但日期和年份是从1开始的。DAY_OF_WEEK从1开始，也就是周日到周六对应 1-7。周日是1，周一是2，周六是7。1月是0，12月是11。

// 创建Calendar实例Calendar c = Calendar.getInstance();// 用日期赋值2021年7月1日，或者是用Date赋值c.setTime(Date date);c.set(2021, 7 - 1, 1);System.out.println(c.get(Calendar.YEAR));//年System.out.println(c.get(Calendar.MONTH) + 1);//月System.out.println(c.get(Calendar.DATE));//日System.out.println(c.get(Calendar.DAY_OF_WEEK));// 星期几，1是星期日// 这年的第几天，从1开始算System.out.println(c.get(Calendar.DAY_OF_YEAR));// 这个月的第几天，从1开始算System.out.println(c.get(Calendar.DAY_OF_MONTH));// 这个月的第几周，从1开始算System.out.println(c.get(Calendar.DAY_OF_WEEK_IN_MONTH));

4. 计算时间间隔

主要是通过使用SimpleDateFormat，先把时间写成String，然后再转成Date， 用getTime函数转成毫秒，相减得到相差的毫秒数。注意1s = 1000ms，SimpleDateFormat中，HH代表24小时制，hh是12小时制，MM是月份，mm是分钟。

String start = "2021-7-13 13:14:20";String end = "2021-7-10 13:14:20";// 注意HH是24小时，hh是12小时SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");Date date1 = sdf.parse(start);Date date2 = sdf.parse(end);// 因为不知道谁大谁小，所以要用abslong diff = Math.abs(date1.getTime() - date2.getTime());System.out.println("相差" + diff + "毫米");// 注意1s = 1000mslong seconds = diff / 1000;//秒long minutes = diff / 1000 / 60;//分钟long hours = diff / 1000 / 60 / 60;//小时long day = diff / 1000 / 60 / 60 / 24;//天

字符串

1.int和String的互相转换

//int转Stringint i=1;  String s=""+i://String转intString s=”3”;int i=Integer.parseInt(s);12345

2.判断一个字符串是否是回文

方法一：判断字符串的i到j位是否是回文

public static boolean isPalindrome(String s, int i, int j){        while(i

方法二：快速判断，一个数字是否是回文

class Solution {    public boolean isPalindrome(int x) {        StringBuffer s=new StringBuffer(Integer.toString(x));        String a=s.toString();//创建一个新字符串记录原来的值        return a.equals(s.reverse().toString())?true:false;    }}

BigInteger与BigDecimal

1.BigInteger

import java.math.BigInteger;import java.util.Scanner;public class Main {    public static void main(String[] args) {        // 传入字符串才能形成大数，默认是把字符串当成十进制        BigInteger bs = new BigInteger("15666666666666666");        BigInteger bs1 = new BigInteger("100002123123123");        //加减乘除        bs.add(bs1);bs.subtract(bs1);bs.multiply(bs1);bs.divide(bs1);//取商                // 取余        bs.mod(bs1);bs.remainder(bs1);        // 返回大整数的double、float类型        bs.doubleValue();bs.floatValue();        // 求最大公约数        bs.gcd(bs1);        // 9、将当前大整数转成十进制字符串形式        System.out.println(bs.toString());        // 也可以把字符串当成二进制传入，生成十进制大数        BigInteger bs2 = new BigInteger("100000", 2);        System.out.println(bs2);    }}1234567891011121314151617181920212223

2.BigDecimal

对BigDecimal做加、减、乘时，精度不会丢失，但是做除法时，存在无法除尽的情况，这时，就必须指定精度以及如何进行截断。

package Chapter_5;import java.math.BigDecimal;import java.math.BigInteger;import java.math.RoundingMode;import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scan = new Scanner(System.in);        // 大小数        BigDecimal bs = scan.nextBigDecimal();        // 获取小数位数，如果是整数则输出负数，表示末尾0的个数        System.out.println(bs.scale());        // 去掉小数末尾无用的0        System.out.println(bs.stripTrailingZeros());        // 设置小数位数，可以选择四舍五入或者直接截断        System.out.println(bs.setScale(4, RoundingMode.HALF_UP));  // 四舍五入        // 对BigDecimal做加、减、乘时，精度不会丢失，但是做除法时，存在无法除尽的情况，这时，就必须指定精度以及如何进行截断。        BigDecimal d1 = new BigDecimal("123.456");        BigDecimal d2 = new BigDecimal("23.456789");        BigDecimal d3 = d1.divide(d2, 10, RoundingMode.HALF_UP); //保留10位小数并四舍五入        BigDecimal d4 = d1.divide(d2); // 报错：ArithmeticException，因为除不尽        //比较两个BigDecimal，不能用equals()因为小数的个数问题，要用compareTo()        //它根据两个值的大小分别返回负数、正数和0，分别表示小于、大于和等于        d1.compareTo(d2)    }}

质数和公约数

1.判断一个数是否是质数

假设该数为n， 我们只需要判断[2,sqrt{n}]内是否有n的因子。如果有，则n为合数，否则，n为质数。这种方法被称为试除法， 即试着除一下所有可能的因子。

public static Boolean isprime(int n){    if(n == 1) return false;    for(int i = 2; i<= n/i ; i++){        if(n % i == 0){            return false;        }    }    return true;}123456789

2.求两个数的最大公约数

//递归（返回最大公约数）int gcd(int a,int b){    return b==0?a:gcd(b,a%b);}

3.求两个数最小公倍数

//递归（返回最大公约数）int gcd(int a,int b){    return b==0?a:gcd(b,a%b);}// 借用gcdint lcm(int a, int b){return a * b / gcd(a,b);}

4.分解质因数

设一个质数为p.如果n%p == 0，那么p就是n的一个质因数，接下来就是求p的指数，我们让n = n/p, 这样就从n中剔除了一个p,接着重复上述两步，直到n%p ！= 0

public static void prime(int n){    for(int i = 2; i <= n/i ; i++){//判断条件用n/i，以防i*i<=n发生溢出        int a = 0;//每次循环都要清零        while(n % i == 0){            n /= i;            a++;        }        if(a > 0)            System.out.println(i + "" + a);//i的a次方    }    //若该数是质数，那么应该将自身(n)也加入    if(n > 1) System.out.println(n + " " + 1);

BFS和回溯DFS框架

回溯DFS

回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：1、路径：也就是已经做出的选择。2、选择列表：也就是你当前可以做的选择。3、结束条件：也就是到达决策树底层，无法再做选择的条件。

代码方面，回溯算法的框架：result = [] def backtrack(路径, 选择列表):    if 满足结束条件:        result.add(路径)        return    for 选择 in 选择列表:        做选择        backtrack(路径, 选择列表)        撤销选择

BFS

本质上就是一幅「图」，让你从一个起点，走到终点，问最短路径，这就是 BFS 的本质。图可能会走回头路，所以要用visited数组存储已经访问过的节点。

/ 计算从起点 start 到终点 target 的最近距离int BFS(Node start, Node target) {    Queue q; // 核心数据结构    HashSet visited; // 保存已经访问过的节点，避免走回头路    q.offer(start); // 将起点加入队列    visited.add(start);    int step = 0; // 记录扩散的步数    while (!q.isEmpty) {        int sz = q.size();        /* 将当前队列中的所有节点向四周扩散 */        for (int i = 0; i < sz; i++) {            Node cur = q.poll();            /* 划重点：这里判断是否到达终点 */            if (cur is target)                return step;            /* 将 cur 的相邻节点加入队列 */            for (Node x : cur.adj())                if (x not in visited) {                    q.offer(x);                    visited.add(x);                }        }        /* 划重点：更新步数在这里 */        step++;    }}

进制转换

/** 十进制转其他进制* Integer.toBinaryString 返回 int 的 二进制 String* Integer.toOctalString 返回 int 的 八进制 String* Integer.toHexString 返回 int 的 十六进制 String* Integer.toString 返回 int 的 X进制 String（两个参数，第一个对应 int 第二个对应X）* */String s1 = Integer.toBinaryString(16);System.out.println(s1);String s2 = Integer.toOctalString(16);System.out.println(s2);String s3 = Integer.toHexString(16);System.out.println(s3);String s4 = Integer.toString(16, 9);System.out.println(s4);/** 其他进制转十进制* Integer.parseInt 返回 X进制的String 的 十进制 Integer（两个参数， 第一个对应String 第二个对应X）* Integer.valueOf 返回 X进制的String 的 十进制 int （两个参数， 第一个对应String 第二个对应X）* */String s5 = "10010";System.out.println(Integer.parseInt(s5, 2));String s6 = "761";System.out.println(Integer.valueOf(s6, 8));

快速幂

• 快速幂用处: O(log n)复杂度计算a^n的值（常用于n可能很大时)
• 原理:分治
• 如果n是奇数，则计算a^floor(n/2)，然后将这个数平方，并乘多一个a。
• 如果n是偶数，则计算a^(n/2)，然后将这个数平方。
• 不断递归下去
• 复杂度低，不会爆栈。

// 递归版本long long fastpow2(long long a,int n){if(n==1)return a;long long tmp = fastpow2(a,n: n/2);if(n%2==1) return tmp*tmp*a;else return tmp*tmp;}

// 非递归版本 更优long long fastpow1 (long long a,int n){long long ans = 1;while(n){if(n&1) ans*=a;a*=a;n>>=1;}return ans;}

线性筛法求质数

private static int cnt;    private static int[] primes = new int[10010];    private static boolean[] st = new boolean[10010];    public static void get_primes(int n){        for(int i = 2; i <= n; i++){            if(!st[i]) primes[cnt++] = i;            for(int j = 0; primes[j] <= n / i; j++){                st[primes[j] * i] = true;                if(i % primes[j] == 0) break;            }        }    }

算术基本定理

又称为正整数的唯一分解定理，即：每个大于1的自然数，若不是本身就是质数，就是可写为2个以上的质数的积

这个定理又叫做算术基本定理（或者叫正整数的唯一分解定理），是数论中非常重要的一个定理。它的表述是：

任何一个大于1的正整数n，都可以唯一地写成n=p1α1*p2α2...pk^αk的形式，其中p1,p2,...,pk是不同的质数，α1,α2,...,αk是正整数。

这个定理的意思是，任何一个大于1的正整数n，都可以写成若干个质数的乘积的形式，并且这种分解方式是唯一的。例如，60可以分解为2^2 * 3^1 * 5^1，其中2、3、5是不同的质数，2的指数为2，3的指数为1，5的指数为1。

对于一个大于1正整数n可以分解质因数：n=p1^α1*p2^α2...*pk^αk则n的正约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1)。其中a1、a2、a3…ak是p1、p2、p3，…pk的指数。证明：n可以分解质因数：n=p1^α1*p2^α2...*pk^αk由约数定义可知p1^α1的约数有:p1^0, p1^1, p1^2, ...,p1^α1,共（a1+1）个,同理p2的约数有（a2+1）个；……；pk^αk的约数有（ak+1）个。

根据乘法原理：n的约数的个数就是 (a1+1)(a2+1)(a3+1)…(ak+1)。例：将378000分解质因数378000=2^4×3^3×5^3×7^1由约数个数定理可知378000共有正约数(4+1)×(3+1)×(3+1)×(1+1)=160个。

知道约数个数，然后就可以求约数之和一个数所有约数之和等于:先把每个质因数从0次幂一直加到其最高次幂,再把每个相应质因数幂的和相乘.若一个数分解为(a^m)*(b^n),则这个数所有约数的和为:(a^0+a^1+a^2+a^3+…+a^m)(b^0+b^1+b^2+b^3+…+b^n).例如:(1)12=2²*3,则12所有约数的和为：(2^0+2^1+2^2）*(3^0+3^1)=7*4=28;(2)60=2²*3*5=(2^0+2^1+2^2)*(3^0+3^1)*(5^0+5^1)=7*4*6=168.

Java Lambda 表达式

Java Lambda 表达式是 Java 8 中引入的一种新特性，它可以看作是一种简化了的函数定义形式，可以使代码更加简洁、易读。

Lambda 表达式的基本语法如下：

(parameters) -> expression或(parameters) -> { statements; }

其中，parameters 表示 Lambda 表达式的参数列表，可以为空或包含一个或多个参数，多个参数之间用逗号隔开。expression 或 statements 表示 Lambda 表达式的函数体，可以是一个表达式或一个语句块。

下面是一个使用 Lambda 表达式的例子，假设有一个列表 Listnumbers，我们要对其进行排序，并输出排序结果：

List numbers = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);Collections.sort(numbers, (a, b) -> a.compareTo(b));System.out.println(numbers);

这里使用了 Collections.sort() 方法对列表进行排序，第二个参数使用了 Lambda 表达式，其中 (a, b) -> a.compareTo(b) 表示一个比较函数，它的作用是比较两个数的大小。这个比较函数使用了箭头符号 ->，箭头符号左侧是参数列表，右侧是函数体，这个比较函数的函数体是 a.compareTo(b)，它表示比较 a 和 b 的大小，并返回比较结果。

Lambda 表达式可以用在很多地方，例如函数式接口、Stream API、并发编程等。它可以使代码更加简洁、易读，同时也可以提高代码的性能和可维护性。

Collection

Collection是 Java 中的接口，被多个泛型容器接口所实现。在这里，Collection是指代存放对象类型的数据结构。

Java 中的 Collection元素类型定义时必须为对象，不能为基本数据类型。

以下内容用法均基于 Java 里多态的性质，均是以实现接口的形式出现。

常用的接口包括 List、Queue、Set和 Map。

容器定义

1. 当定义泛型容器类时，需要在定义时指定数据类型。

例如：

List list1 = new LinkedList<>();

倘若不指定数据类型，而当成 Object类型随意添加数据，在 Java 8 中虽能编译通过，但会有很多警告风险。

如果是明确了类型如 List，此时编译器会检查放入的数据类型，只能放入整数的数据。声明集合变量时只能使用包装类型 List或者自定义的 Class，而不能是基本类型如 List。

List

ArrayList

ArrayList是支持可以根据需求动态生长的数组，初始长度默认为 10。如果超出当前长度便扩容 。

初始化

import java.io.PrintWriter;import java.util.ArrayList;import java.util.List;public class Main {    static PrintWriter out = new PrintWriter(System.out);    public static void main(String[] args) {        List list1 = new ArrayList<>();  // 创建一个名字为 list1 的可自增数组，初始长度为默认值（10）        List list2 = new ArrayList<>(30);  // 创建一个名字为list2的可自增数组，初始长度为 30        List list3 = new ArrayList<>(list2);  // 创建一个名字为 list3 的可自增数组，使用 list2 里的元素和 size 作为自己的初始值    }}

LinkedList

LinkedList是双链表。

初始化

import java.io.PrintWriter;import java.util.LinkedList;import java.util.List;public class Main {    static PrintWriter out = new PrintWriter(System.out);    public static void main(String[] args) {        List list1 = new LinkedList<>();  // 创建一个名字为 list1 的双链表        List list2 = new LinkedList<>(list1);  // 创建一个名字为 list2 的双链表，将 list1 内所有元素加入进来    }}

常用方法

以下均用 this代替当前 List：

使用案例及区别对比：

import java.io.PrintWriter;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;public class Main {    static PrintWriter out = new PrintWriter(System.out);    static List array = new ArrayList<>();    static List linked = new LinkedList<>();    static void add() {        array.add(1);  // 时间复杂度为 O(1)        linked.add(1);  // 时间复杂度为 O(1)    }    static void get() {        array.get(10);  // 时间复杂度为 O(1)        linked.get(10);  // 时间复杂度为 O(11)    }    static void addIdx() {        array.add(0, 2);  // 最坏情况下时间复杂度为 O(n)        linked.add(0, 2);  // 最坏情况下时间复杂度为 O(n)    }    static void size() {        array.size();  // 时间复杂度为 O(1)        linked.size();  // 时间复杂度为 O(1)    }    static void set() {  // 该方法返回值为原本该位置元素的值        array.set(0, 1);  // 时间复杂度为 O(1)        linked.set(0, 1);  // 最坏时间复杂度为 O(n)    }}

遍历

import java.io.PrintWriter;import java.util.ArrayList;import java.util.Iterator;import java.util.LinkedList;import java.util.List;public class Main {    static PrintWriter out = new PrintWriter(System.out);    static List array = new ArrayList<>();    static List linked = new LinkedList<>();       static void function1() {  // 朴素遍历        for (int i = 0; i < array.size(); i++) {            out.println(array.get(i));  // 遍历自增数组，复杂度为 O(n)        }        for (int i = 0; i < linked.size(); i++) {            out.println(linked.get(i));  // 遍历双链表，复杂度为 O(n^2)，因为 LinkedList 的 get(i) 复杂度是 O(i)        }    }    static void function2() {  // 增强 for 循环遍历        for (int e : array) {            out.println(e);        }        for (int e : linked) {            out.println(e);  // 复杂度均为 O(n)        }    }    static void function3() {  // 迭代器遍历        Iterator iterator1 = array.iterator();        Iterator iterator2 = linked.iterator();        while (iterator1.hasNext()) {            out.println(iterator1.next());        }        while (iterator2.hasNext()) {            out.println(iterator2.next());        }  // 复杂度均为 O(n)    }}

注意

不要在 for/foreach遍历 List的过程中删除其中的元素，否则会抛出异常。

原因也很简单，list.size()改变了，但在循环中已循环的次数却是没有随之变化。原来预计在下一个 index的数据因为删除的操作变成了当前 index的数据，运行下一个循环时操作的会变为原来预计在下下个 index的数据，最终会导致操作的数据不符合预期。

Queue

LinkedList

可以使用 LinkedList实现普通队列，底层是链表模拟队列。

初始化

Queue q = new LinkedList<>();

LinkedList底层实现了 List接口与 Deque接口，而 Deque接口继承自 Queue接口，所以 LinkedList可以同时实现 List与 Queue。

ArrayDeque

可以使用 ArrayDeque实现普通队列，底层是数组模拟队列。

初始化

Queue q = new ArrayDeque<>(); 

ArrayDeque底层实现了 Deque接口，而 Deque接口继承自 Queue接口，所以 ArrayDeque可以实现 Queue。

LinkedList 与 ArrayDeque 在实现 Queue 接口上的区别

1. 数据结构：在数据结构上，ArrayDeque和 LinkedList都实现了 Java Deque 双端队列接口。但 ArrayDeque没有实现了 Java List 列表接口，所以不具备根据索引位置操作的行为。
2. 线程安全：ArrayDeque和 LinkedList都不考虑线程同步，不保证线程安全。
3. 底层实现：在底层实现上，ArrayDeque是基于动态数组的，而 LinkedList是基于双向链表的。
4. 在遍历速度上：ArrayDeque是一块连续内存空间，基于局部性原理能够更好地命中 CPU 缓存行，而 LinkedList是离散的内存空间对缓存行不友好。
5. 在操作速度上：ArrayDeque和 LinkedList的栈和队列行为都是 时间复杂度，ArrayDeque的入栈和入队有可能会触发扩容，但从均摊分析上看依然是 时间复杂度。
6. 额外内存消耗上：ArrayDeque在数组的头指针和尾指针外部有闲置空间，而 LinkedList在节点上增加了前驱和后继指针。

PriorityQueue

PriorityQueue是优先队列，默认是小根堆。

初始化

Queue q1 = new PriorityQueue<>();  // 小根堆 Queue q2 = new PriorityQueue<>((x, y) -> {return y - x;});  // 大根堆 `

常用方法

以下均用 this代替当前 Queue:

使用案例及区别对比：

import java.io.PrintWriter;import java.util.LinkedList;import java.util.PriorityQueue;import java.util.Queue;public class Main {    static PrintWriter out = new PrintWriter(System.out);    static Queue q1 = new LinkedList<>();    static Queue q2 = new PriorityQueue<>();    static void add() {  // add 和 offer 功能上没有差距，区别是是否会抛出异常        q1.add(1);  // 时间复杂度为 O(1)        q2.add(1);  // 时间复杂度为 O(logn)    }    static void isEmpty() {        q1.isEmpty();  // 时间复杂度为 O(1)        q2.isEmpty();  // 空间复杂度为 O(1)    }    static void size() {        q1.size();  // 时间复杂度为 O(1)        q2.size();  // 返回 q2 的长度    }    static void peek() {        q1.peek();  // 时间复杂度为 O(1)        q2.peek();  // 时间复杂度为 O(logn)    }    static void poll() {        q1.poll();  // 时间复杂度为 O(1)        q2.poll();  // 时间复杂度为 O(logn)    }}

​

遍历

import java.io.PrintWriter;import java.util.LinkedList;import java.util.PriorityQueue;import java.util.Queue;public class Main {    static PrintWriter out = new PrintWriter(System.out);    static Queue q1 = new LinkedList<>();    static Queue q2 = new PriorityQueue<>();    static void test() {        while (!q1.isEmpty()) {  // 复杂度为 O(n)            out.println(q1.poll());        }        while (!q2.isEmpty()) {  // 复杂度为 O(nlogn)            out.println(q2.poll());        }    }}

实现一个泛型为Pair的PriorityQueue，以Pair的第二个元素大小进行排序

import java.util.Comparator;import java.util.PriorityQueue;public class PairPriorityQueue {    public static void main(String[] args) {        PriorityQueue> pq = new PriorityQueue<>(new Comparator>() {            @Override            public int compare(Pair p1, Pair p2) {                return p1.getValue().compareTo(p2.getValue());            }        });        pq.offer(new Pair<>(1, 3));        pq.offer(new Pair<>(2, 2));        pq.offer(new Pair<>(3, 1));        while (!pq.isEmpty()) {            System.out.println(pq.poll());        }    }    static class Pair {        private final K key;        private final V value;        public Pair(K key, V value) {            this.key = key;            this.value = value;        }        public K getKey() {            return key;        }        public V getValue() {            return value;        }        @Override        public String toString() {            return "[" + key + ", " + value + "]";        }    }}

或者实现如下：

import java.util.*;public class PriorityQueueDemo {    public static void main(String[] args) {        // 创建一个泛型为的PriorityQueue，并自定义Comparator        PriorityQueue> pq = new PriorityQueue<>(new Comparator>() {            @Override            public int compare(Map.Entry o1, Map.Entry o2) {                return o2.getValue() - o1.getValue();            }        });        // 添加测试数据        pq.add(new AbstractMap.SimpleEntry<>("hello", 2));        pq.add(new AbstractMap.SimpleEntry<>("world", 3));        pq.add(new AbstractMap.SimpleEntry<>("java", 1));        pq.add(new AbstractMap.SimpleEntry<>("programming", 4));        // 输出队列中的元素        while (!pq.isEmpty()) {            Map.Entry entry = pq.poll();            System.out.println(entry.getKey() + ": " + entry.getValue());        }    }}

Set

Set是保持容器中的元素不重复的一种数据结构。

HashSet

随机位置插入的 Set。

初始化

Set s1 = new HashSet<>(); 

LinkedHashSet

保持插入顺序的 Set。

初始化

Set s2 = new LinkedHashSet<>(); 

TreeSet

保持容器中元素有序的 Set，默认为升序。

初始化

Set s3 = new TreeSet<>(); Set s4 = new TreeSet<>((x, y) -> {return y - x;});  // 降序 

常用方法

以下均用 this代替当前 Set:

使用案例：求并集、交集、差集。

import java.io.PrintWriter;import java.util.HashSet;import java.util.LinkedHashSet;import java.util.Set;public class Main {    static PrintWriter out = new PrintWriter(System.out);    static Set s1 = new HashSet<>();    static Set s2 = new LinkedHashSet<>();    static void add() {        s1.add(1);    }    static void contains() {  // 判断 set 中是否有元素值为 2，有则返回 true，否则返回 false        s1.contains(2);    }    static void test1() {  // s1 与 s2 的并集        Set res = new HashSet<>();        res.addAll(s1);        res.addAll(s2);    }    static void test2() {  // s1 与 s2 的交集        Set res = new HashSet<>();        res.addAll(s1);        res.retainAll(s2);    }    static void test3() {  // 差集：s1 - s2        Set res = new HashSet<>();        res.addAll(s1);        res.removeAll(s2);    }}

遍历

import java.io.PrintWriter;import java.util.HashSet;import java.util.LinkedHashSet;import java.util.Set;public class Main {    static PrintWriter out = new PrintWriter(System.out);    static Set s1 = new HashSet<>();    static Set s2 = new LinkedHashSet<>();    static void test() {        for (int key : s1) {            out.println(key);        }        out.close();    }}

实现一个泛型为Pair的TreeSet，以Pair的第二个元素大小进行排序

import java.util.Comparator;import java.util.TreeSet;public class PairTreeSet {    public static void main(String[] args) {        Comparator> comparator = new Comparator>() {            @Override            public int compare(Pair p1, Pair p2) {                return p1.getValue().compareTo(p2.getValue());            }        };        TreeSet> set = new TreeSet<>(comparator);        set.add(new Pair<>(1, 3));        set.add(new Pair<>(2, 2));        set.add(new Pair<>(3, 1));        for (Pair pair : set) {            System.out.println(pair.getKey() + " " + pair.getValue());        }    }}class Pair {    private final K key;    private final V value;    public Pair(K key, V value) {        this.key = key;        this.value = value;    }    public K getKey() {        return key;    }    public V getValue() {        return value;    }}

Map

Map是维护键值对 的一种数据结构，其中 Key唯一。

HashMap

随机位置插入的 Map。

初始化

Map map1 = new HashMap<>();

LinkedHashMap

保持插入顺序的 Map。

初始化

Map map2 = new LinkedHashMap<>(); 

TreeMap

保持 key有序的 Map，默认升序。

初始化

Map map3 = new TreeMap<>(); Map map4 = new TreeMap<>((x, y) -> {return y - x;});  // 降序 

常用方法

以下均用 this代替当前 Map：

使用案例:

import java.io.PrintWriter;import java.util.HashMap;import java.util.LinkedHashMap;import java.util.Map;import java.util.TreeMap;public class Main {    static PrintWriter out = new PrintWriter(System.out);    static Map map1 = new HashMap<>();    static Map map2 = new LinkedHashMap<>();    static Map map3 = new TreeMap<>();    static Map map4 = new TreeMap<>((x,y)->{return y-x;});    static void put(){  // 将 key 为 1、value 为 1 的元素返回        map1.put(1, 1);    }    static void get(){  // 将 key 为 1 的 value 返回        map1.get(1);    }    static void containsKey(){  // 判断是否有 key 为 1 的键值对        map1.containsKey(1);    }    static void KeySet(){        map1.keySet();    }}

遍历

import java.io.PrintWriter;import java.util.HashMap;import java.util.Map;public class Main {    static PrintWriter out = new PrintWriter(System.out);    static Map map1 = new HashMap<>();    static void print() {        for (int key : map1.keySet()) {            out.println(key + " " + map1.get(key));        }    }}

当然，在面向对象的世界里，你的参数是什么都可以，包括 Collection与自定义类型。

例如 Map也可以定义为：

Map> map = new HashMap<>(); 

泛型为,按第String大小进行降序排序

import java.util.*;public class TreeMap {    public static void main(String[] args) {        // 创建一个泛型为的TreeMap，并自定义Comparator       TreeMap map = new TreeMap<>(new Comparator() {            @Override            public int compare(String s1, String s2) {                return s1.compareTo(s2); // 降序排序            }        });        }    }}

Arrays

Arrays是 java.util中对数组操作的一个工具类。方法均为静态方法，可使用类名直接调用。

Arrays.sort()

Arrays.sort()是对数组进行的排序的方法，主要重载方法如下：

import java.util.Arrays;import java.util.Comparator;public class Main {    static int a[] = new int[10];    static Integer b[] = new Integer[10];    static int firstIdx, lastIdx;    public static void main(String[] args) {        Arrays.sort(a);  // 1        Arrays.sort(a, firstIdx, lastIdx);  // 2        Arrays.sort(b, new Comparator() {  // 3            @Override            public int compare(Integer o1, Integer o2) {                return o2 - o1;            }        });        Arrays.sort(b, firstIdx, lastIdx, new Comparator() {  // 4            @Override            public int compare(Integer o1, Integer o2) {                return o2 - o1;            }        });        // 由于 Java 8 后有 Lambda 表达式，第三个重载及第四个重载亦可写为        Arrays.sort(b, (x, y) -> {  // 5            return y - x;        });        Arrays.sort(b, (x, y) -> {  // 6            return y - x;        });    }}

序号所对应的重载方法含义：

1. 对数组 a 进行排序，默认升序。
2. 对数组 a 的指定位置进行排序，默认升序，排序区间为左闭右开 [firstIdx, lastIdx)。
3. 对数组 a 以自定义的形式排序，第二个参数 -第一个参数为降序,第一个参数 -第二个参数为升序，当自定义排序比较器时，数组元素类型必须为对象类型。
4. 对数组 a 的指定位置进行自定义排序，排序区间为左闭右开 [firstIdx, lastIdx)，当自定义排序比较器时，数组元素类型必须为对象类型。
5. 和 3 同理，用 Lambda 表达式优化了代码长度。
6. 和 4 同理，用 Lambda 表达式优化了代码长度。

Arrays.sort()底层函数：

1. 当你 Arrays.sort的参数数组元素类型为基本数据类型（byte、short、char、int、long、double、float）时，默认为 DualPivotQuicksort（双轴快排），复杂度最坏可以达到 。
2. 当你 Arrays.sort的参数数组元素类型为非基本数据类型时），则默认为 legacyMergeSort和 TimSort(归并排序），复杂度为。

可以通过如下代码验证：

Codeforces 1646B - Quality vs Quantity

题意概要：有n个数，你需要将其分为 2 组，是否能存在 1 组的长度小于另 1 组的同时和大于它。

例题代码

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.Arrays;import java.util.StringTokenizer;public class Main {    static class FastReader {        StringTokenizer st;        BufferedReader br;        public FastReader() {            br = new BufferedReader(new InputStreamReader(System.in));        }        String next() {            while (st == null || !st.hasMoreElements()) {                try {                    st = new StringTokenizer(br.readLine());                } catch (IOException e) {                    e.printStackTrace();                }            }            return st.nextToken();        }        int nextInt() {            return Integer.parseInt(next());        }        long nextLong() {            return Long.parseLong(next());        }        double nextDouble() {            return Double.parseDouble(next());        }        String nextLine() {            String str = "";            try {                str = br.readLine();            } catch (IOException e) {                e.printStackTrace();            }            return str;        }    }    static PrintWriter out = new PrintWriter(System.out);    static FastReader in = new FastReader();    static void solve() {        int n = in.nextInt();        Integer a[] = new Integer[n + 10];        for (int i = 1; i <= n; i++) {            a[i] = in.nextInt();        }        Arrays.sort(a, 1, n + 1);        long left = a[1];        long right = 0;        int x = n;        for (int i = 2; i < x; i++, x--) {            left = left + a[i];            right = right + a[x];            if (right > left) {                out.println("YES");                return;            }        }        out.println("NO");    }    public static void main(String[] args) {        int t = in.nextInt();        while (t-- > 0) {            solve();        }        out.close();    }}

如果你将以上代码的 a 数组类型由 Integer修改为 int，会导致 TLE。

Arrays.binarySearch()

Arrays.binarySearch()是对数组连续区间进行二分搜索的方法，前提是数组必须有序，时间复杂度为 ，主要重载方法如下：

import java.util.Arrays;public class Main {    static int a[] = new int[10];    static Integer b[] = new Integer[10];    static int firstIdx, lastIdx;    static int key;    public static void main(String[] args) {        Arrays.binarySearch(a, key);  // 1        Arrays.binarySearch(a, firstIdx, lastIdx, key);  // 2    }}

源码如下：

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {        int low = fromIndex;        int high = toIndex - 1;        while (low <= high) {            int mid = (low + high) >>> 1;            int midVal = a[mid];            if (midVal < key)                low = mid + 1;            else if (midVal > key)                high = mid - 1;            else                return mid; // key found        }        return -(low + 1);  // key not found.    }

序号所对应的重载方法含义：

1. 从数组 a 中二分查找是否存在 key，如果存在，便返回其下标。若不存在，则返回一个负数。
2. 从数组 a 中二分查找是否存在 key，如果存在，便返回其下标,搜索区间为左闭右开 [firstIdx,lastIdx)。若不存在，则返回一个负数。

Arrays.fill()

Arrays.fill()方法将数组中连续位置的元素赋值为统一元素。其接受的参数为数组、fromIndex、toIndex和需要填充的数。方法执行后，数组左闭右开区间 [firstIdx,lastIdx)内的所有元素的值均为需要填充的数。

Collections

Collections是 java.util中对集合操作的一个工具类。方法均为静态方法，可使用类名直接调用。

Collections.sort()

Collections.sort()底层原理为将其中所有元素转化为数组调用 Arrays.sort()，完成排序后再赋值给原本的集合。又因为 Java 中 Collection的元素类型均为对象类型，所以始终是归并排序去处理。

该方法无法对集合指定区间排序。

底层源码：

default void sort(Comparator c) {        Object[] a = this.toArray();        Arrays.sort(a, (Comparator) c);        ListIterator i = this.listIterator();        for (Object e : a) {            i.next();            i.set((E) e);        }    }

Collections.binarySearch()

Collections.binarySearch()是对集合中指定区间进行二分搜索,功能与 Arrays.binarySearch()相同。

Collections.binarySearch(list, key); 

该方法无法对指定区间进行搜索。

Collections.swap()

Collections.swap()的功能是交换集合中指定二个位置的元素。

Collections.swap(list, i, j);