跳转至

# Java 进阶

注意

以下内容均基于 Java JDK 8 版本编写，不排除在更高版本中有部分改动的可能性．

## 更高速的输入输出

`Scanner` 和 `System.out.print` 在最开始会工作得很好，但是在处理更大的输入的时候会降低效率，因此我们会需要使用一些方法来提高 IO 速度．

### 使用 Kattio + StringTokenizer 作为输入

最常用的方法之一是使用来自 Kattis 的 Kattio.java 来提高 IO 效率．1这个方法会将 `StringTokenizer` 与 `PrintWriter` 包装在一个类中方便使用．而在具体进行解题的时候（假如赛会/组织方允许）可以直接使用这个模板．

下方即为应包含在代码中的 IO 模板，由于 Kattis 的原 Kattio 包含一些并不常用的功能，下方的模板经过了一些调整（原 Kattio 使用 MIT 作为协议）．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;
        // 标准 IO
        public Kattio() { this(System.in, System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        // 文件 IO
        public Kattio(String intput, String output) throws IOException {
            super(output);
            r = new BufferedReader(new FileReader(intput));
        }
        // 在没有其他输入时返回 null
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) {}
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }

而下方代码简单展示了 Kattio 的使用：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    class Test {
        public static void main(String[] args) {
            Kattio io = new Kattio();
            // 字符串输入
            String str = io.next();
            // int 输入
            int num = io.nextInt();
            // 输出
            io.println("Result");
            // 请确保关闭 IO 流以确保输出被正确写入
            io.close();
        }
    }

### 使用 StreamTokenizer 作为输入

在某些情况使用 `StringTokenizer` 会导致 MLE（Memory Limit Exceeded，超过内存上限），此时我们需要使用 `StreamTokenizer` 作为输入．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    import java.io.*;
    public class Main {
        // IO 代码
        public static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in), 32768));
        public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        public static double nextDouble() throws IOException { in.nextToken(); return in.nval; }
        public static float nextFloat() throws IOException { in.nextToken(); return (float)in.nval; }
        public static int nextInt() throws IOException { in.nextToken(); return (int)in.nval; }
        public static String next() throws IOException { in.nextToken(); return in.sval; }
        public static long nextLong() throws Exception { in.nextToken(); return (long)in.nval;}

        // 使用示例
        public static void main(String[] args) throws Exception {
            int n = nextInt();
            out.println(n);
            out.close();
        }
    }

### Kattio + StringTokenizer 的方法与 StreamTokenizer 的方法之间的分析与对比

1. `StreamTokenizer` 相较于 `StringTokenizer` 使用的内存较少，当 Java 标程 MLE 时可以尝试使用 `StreamTokenizer`，但是 `StreamTokenizer` 会丢失精度，读入部分数据时会出现问题；
   - `StreamTokenizer` 源码存在 `Type`，该 `Type` 根据输入内容来决定类型，如果输入类似于 `123oi` 以 数字开头 的字符串，他会强制认为的类型是 `double` 类型，因此在读入中以 `double` 类型去读 `String` 类型便会抛出异常；
   - `StreamTokenizer` 在读入 `1e14` 以上大小的数字会丢失精度；
2. 在使用 `PrintWriter` 情况下，需注意在程序结束最后 `close()` 关闭输出流或在需要输出的时候使用 `flush()` 清除缓冲区，否则内容将不会被写入到控制台/文件中．
3. `Kattio` 是继承自 `PrintWriter` 类，自身对象具有了 `PrintWriter` 的功能，因此可以直接调用 `PrintWriter` 类的函数输出，同时将 `StringTokenizer` 作为了自身的成员变量来修改．而第二种 `Main` 是同时将 `StreamTokenizer` 与 `PrintWriter` 作为了自身的成员变量，因此在使用上有些许差距．

综上所述，在大部分情况下，`StringTokenizer` 的使用处境要优越于 `StreamTokenizer`，在极端 MLE 的情况下可以尝试 `StreamTokenizer`，同时 `int` 范围以上的数据 `StreamTokenizer` 处理是无能为力的．

## BigInteger 与数论

`BigInteger` 是 Java 提供的高精度计算类，可以很方便地解决高精度问题．

### 初始化

`BigInteger` 常用创建方式有如下二种：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    import java.io.PrintWriter;
    import java.math.BigInteger;

    class Main {
        static PrintWriter out = new PrintWriter(System.out);
        public static void main(String[] args) {
            BigInteger a = new BigInteger("12345678910");  // 将字符串以十进制的形式创建 BigInteger 对象
            out.println(a);  // a 的值为 12345678910
            BigInteger b = new BigInteger("1E", 16);  // 将字符串以指定进制的形式创建 BigInteger 对象
            out.println(b);  // b 的值为 30
            out.close();
        }
    }

### 基本运算

以下均用 `this` 代替当前 `BigIntger`:

函数名 | 功能
--- | ---
`abs()` | 返回 `this` 的绝对值
`negate()` | 返回 `this` 的相反数
`add(BigInteger val)` | 返回 `this` 和 `val` 的和
`subtract(BigInteger val)` | 返回 `this` 和 `val` 的差
`multiply(BigInteger val)` | 返回 `this` 和 `val` 的积
`divide(BigInteger val)` | 返回 `this` 和 `val` 的商
`remainder(BigInteger val)` | 返回 `this` 除以 `val` 的余数
`mod(BigInteger val)` | 返回 `this` 对 `val` 取模的值
`pow(int val)` | 返回 `this` 的 `val` 次方
`and(BigInteger val)` | 返回 `this` 和 `val` 的按位与
`or(BigInteger val)` | 返回 `this` 和 `val` 的按位或
`not()` | 返回 `this` 的按位取反
`xor(BigInteger val)` | 返回 `this` 和 `val` 的按位异或
`shiftLeft(int n)` | 返回 `this` 左移 `n` 位
`shiftRight(int n)` | 返回 `this` 右移 `n` 位
`max(BigInteger val)` | 返回 `this` 与 `val` 的较大值
`min(BigInteger val)` | 返回 `this` 与 `val` 的较小值
`bitCount()` | 返回 `this` 的二进制中不包括符号位的 `1` 的个数
`bitLength()` | 返回 `this` 的二进制中不包括符号位的长度
`getLowestSetBit()` | 返回 `this` 的二进制中最右边的位置
`compareTo(BigInteger val)` | 比较 `this` 和 `val` 值大小
`toString()` | 返回 `this` 的十进制字符串表示形式
`toString(int radix)` | 返回 `this` 的 `raidx` 进制字符串表示形式

使用案例如下：

      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    import java.io.PrintWriter;
    import java.math.BigInteger;

    public class Main {
        static PrintWriter out = new PrintWriter(System.out);
        static BigInteger a, b;

        static void abs() {
            out.println("abs:");
            a = new BigInteger("-123");
            out.println(a.abs());  // 输出 123
            a = new BigInteger("123");
            out.println(a.abs());  // 输出 123
        }

        static void negate() {
            out.println("negate:");
            a = new BigInteger("-123");
            out.println(a.negate());  // 输出 123
            a = new BigInteger("123");
            out.println(a.negate());  // 输出 -123
        }

        static void add() {
            out.println("add:");
            a = new BigInteger("123");
            b = new BigInteger("123");
            out.println(a.add(b));  // 输出 246
        }

        static void subtract() {
            out.println("subtract:");
            a = new BigInteger("123");
            b = new BigInteger("123");
            out.println(a.subtract(b));  // 输出 0
        }

        static void multiply() {
            out.println("multiply:");
            a = new BigInteger("12");
            b = new BigInteger("12");
            out.println(a.multiply(b));  // 输出 144
        }

        static void divide() {
            out.println("divide:");
            a = new BigInteger("12");
            b = new BigInteger("11");
            out.println(a.divide(b));  // 输出 1
        }

        static void remainder() {
            out.println("remainder:");
            a = new BigInteger("12");
            b = new BigInteger("10");
            out.println(a.remainder(b));  // 输出 2
            a = new BigInteger("-12");
            b = new BigInteger("10");
            out.println(a.remainder(b));  // 输出 -2
        }

        static void mod() {
            out.println("mod:");
            a = new BigInteger("12");
            b = new BigInteger("10");
            out.println(a.mod(b));  // 输出 2
            a = new BigInteger("-12");
            b = new BigInteger("10");
            out.println(a.mod(b));  // 输出 8
        }

        static void pow() {
            out.println("pow:");
            a = new BigInteger("2");
            out.println(a.pow(10));  // 输出 1024
        }

        static void and() {
            out.println("and:");
            a = new BigInteger("3");  // 11
            b = new BigInteger("5");  // 101
            out.println(a.and(b));  // 输出 1
        }

        static void or() {
            out.println("or:");
            a = new BigInteger("2");  // 10
            b = new BigInteger("5");  // 101
            out.println(a.or(b));  // 输出 7
        }

        static void not() {
            out.println("not:");
            a = new BigInteger("2147483647");  // 01111111 11111111 11111111 11111111
            out.println(a.not());  // 输出 -2147483648 二进制为：10000000 00000000 00000000 00000000
        }

        static void xor() {
            out.println("xor:");
            a = new BigInteger("6");  // 110
            b = new BigInteger("5");  // 101
            out.println(a.xor(b));  // 011 输出 3
        }

        static void shiftLeft() {
            out.println("shiftLeft:");
            a = new BigInteger("1");
            out.println(a.shiftLeft(10));  // 输出 1024
        }

        static void shiftRight() {
            out.println("shiftRight:");
            a = new BigInteger("1024");
            out.println(a.shiftRight(8));  // 输出 4
        }

        static void max() {
            out.println("max:");
            a = new BigInteger("6");
            b = new BigInteger("5");
            out.println(a.max(b));  // 输出 6
        }

        static void min() {
            out.println("min:");
            a = new BigInteger("6");
            b = new BigInteger("5");
            out.println(a.min(b));  // 输出 5
        }

        static void bitCount() {
            out.println("bitCount:");
            a = new BigInteger("6");  // 110
            out.println(a.bitCount());  // 输出 2
        }

        static void bitLength() {
            out.println("bitLength:");
            a = new BigInteger("6");  // 110
            out.println(a.bitLength());  // 输出 3
        }

        static void getLowestSetBit() {
            out.println("getLowestSetBit:");
            a = new BigInteger("8");  // 1000
            out.println(a.getLowestSetBit());  // 输出 3
        }

        static void compareTo() {
            out.println("compareTo:");
            a = new BigInteger("8");
            b = new BigInteger("9");
            out.println(a.compareTo(b));  // 输出 -1
            a = new BigInteger("8");
            b = new BigInteger("8");
            out.println(a.compareTo(b));  // 输出 0
            a = new BigInteger("8");
            b = new BigInteger("7");
            out.println(a.compareTo(b));  // 输出 1
        }

        static void toStringTest() {
            out.println("toString:");
            a = new BigInteger("15");
            out.println(a.toString());  // 输出 15
            out.println(a.toString(16));  // 输出 f
        }

        public static void main(String[] args) {
            abs();
            negate();
            add();
            subtract();
            multiply();
            divide();
            remainder();
            mod();
            pow();
            and();
            or();
            not();
            xor();
            shiftLeft();
            shiftRight();
            max();
            min();
            bitCount();
            bitLength();
            getLowestSetBit();
            compareTo();
            toStringTest();
            out.close();
        }
    }

### 数学运算

以下均用 `this` 代替当前 `BigIntger`:

函数名 | 功能
--- | ---
`gcd(BigInteger val)` | 返回 `this` 的绝对值与 `val` 的绝对值的最大公约数
`isProbablePrime(int val)` | 返回一个表示 `this` 是否是素数的布尔值
`nextProbablePrime()` | 返回第一个大于 `this` 的素数
`modPow(BigInteger b, BigInteger p)` | 返回 `this` 的 `b` 次方模 `p` 的值
`modInverse(BigInteger p)` | 返回 `this` 在模 `p` 意义下的乘法逆元

使用案例如下：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    import java.io.PrintWriter;
    import java.math.BigInteger;

    public class Main {
        static PrintWriter out = new PrintWriter(System.out);
        static BigInteger a, b, p;

        static void gcd() {  // 最大公约数
            a = new BigInteger("120032414321432144212100");
            b = new BigInteger("240231431243123412432140");
            out.println(String.format("gcd(%s,%s)=%s", a.toString(), b.toString(), a.gcd(b).toString()));  // gcd(120032414321432144212100,240231431243123412432140)=20
        }

        static void isPrime() {  // 基于米勒罗宾判定该数是否是素数，参数越大准确性越高，复杂度越高．准确性为 (1-1/(val*2))
            a = new BigInteger("1200324143214321442127");
            out.println("a:" + a.toString());
            out.println(a.isProbablePrime(10) ? "a is prime" : "a is not prime");  // a is not prime
        }

        static void nextPrime() {  // 找出该数的下一个素数
            a = new BigInteger("1200324143214321442127");
            out.println("a:" + a.toString());
            out.println(String.format("a nextPrime is %s", a.nextProbablePrime().toString()));  // a nextPrime is 1200324143214321442199
        }

        static void modPow() {  // 快速幂，比正常版本要快，内部有数学优化
            a = new BigInteger("2");
            b = new BigInteger("10");
            p = new BigInteger("1000");
            out.println(String.format("a:%s b:%s p:%s", a, b, p));
            out.println(String.format("a^b mod p:%s", a.modPow(b, p).toString()));//  24
        }

        static void modInverse() {  // 逆元
            a = new BigInteger("10");
            b = new BigInteger("3");
            out.println(a.modInverse(b));  // a ^ (p-2) mod p = 1
        }

        public static void main(String[] args) {
            gcd();
            isPrime();
            nextPrime();
            modPow();
            modInverse();
            out.close();
        }
    }

关于米勒罗宾相关知识可以查阅 Miller–Rabin 素性测试．

## 基本数据类型与包装数据类型

### 简介

由于基本类型没有面向对象的特征，为了他们参加到面向对象的开发中，Java 为八个基本类型提供了对应的包装类，分别是 `Byte`、`Double`、`Float`、`Integer`、`Long`、`Short`、`Character` 和 `Boolean`．两者之间的对应关系如下：

基本数据类型 | 包装数据类型
--- | ---
`byte` | `Byte`
`short` | `Short`
`boolean` | `Boolean`
`char` | `Character`
`int` | `Integer`
`long` | `Long`
`float` | `Float`
`double` | `Double`

### 区别

此处以 `int` 与 `Integer` 举例：

1. `Integer` 是 `int` 的包装类，`int` 则是 Java 的一种基本类型数据．
2. `Integer` 类型实例后才能使用，而 `int` 类型不需要．
3. `Integer` 实际对应的引用，当 `new` 一个 `Integer` 时，实际上生成了一个对象，而 `int` 则是直接存储数据．
4. `Integer` 的默认值是 `null`，可接受 `null` 和 `int` 类型的数据，`int` 默认值是 0，不能接受 `null` 类型的数据．
5. `Integer` 判定二个变量是否相同使用 `==` 可能会导致不正确的结果，只能使用 `equals()`，而 `int` 可以直接使用 `==`．

### 装箱与拆箱

此处以 `int` 与 `Integer` 举例：

`Integer` 的本质是对象，`int` 是基本类型，两个类型之间是不能直接赋值的．需要转换时，应将基础类型转换为包装类型，这种做法称为装箱，反过来则称为拆箱．

    1
    2
    3
    4
    5
    6
    // 基本类型
    int value1 = 1;
    // 装箱转换为包装类型
    Integer integer = Integer.valueOf(value1);
    // 拆箱转换为基本类型
    int value2 = integer.intValue();

Java 5 引入了自动装箱拆箱机制：

    1
    2
    Integer integer = 1;
    int value = integer;

注意

虽然 JDK 增加了自动装箱拆箱的机制，但在声明变量时请选择合适的类型，因为包装类型 `Integer` 可以接受 `null`，而基本类型 `int` 不能接受 `null`．因此，对使用 `null` 值的包装类型进行拆箱操作时，会抛出异常．如下代码展示了这一行为．

    1
    2
    3
    4
    5
    Integer integer = Integer.valueOf(null);
    integer.intValue();  // 抛出 java.lang.NumberFormatException 异常

    Integer integer = null;
    integer.intValue();  // 抛出 java.lang.NullPointerException 异常

## 继承

基于已有的设计创造新的设计，就是面向对象程序设计中的继承．在继承中，新的类不是凭空产生的，而是基于一个已经存在的类而定义出来的．通过继承，新的类自动获得了基础类中所有的成员，包括成员变量和方法，包括各种访问属性的成员，无论是 `public` 还是 `private`．显然，通过继承来定义新的类，远比从头开始写一个新的类要简单快捷和方便．继承是支持代码重用的重要手段之一．

在 Java 中，继承的关键字为 `extends`，且 Java 只支持单继承，但可以实现多接口．

在 Java 中，所有类都是 `Object` 类的子类．

子类继承父类，所有的父类的成员，包括变量和方法，都成为了子类的成员，除了构造方法．构造方法是父类所独有的，因为它们的名字就是类的名字，所以父类的构造方法在子类中不存在．除此之外，子类继承得到了父类所有的成员．

每个成员有不同的访问属性，子类继承得到了父类所有的成员，但是不同的访问属性使得子类在使用这些成员时有所不同：有些父类的成员直接成为子类的对外的界面，有些则被深深地隐藏起来，即使子类自己也不能直接访问．

下表列出了不同访问属性的父类成员在子类中的访问属性：

父类成员访问属性 | 在父类中的含义 | 在子类中的含义
--- | --- | ---
`public` | 对所有类开放 | 对所有类开放
`protected` | 只有包内其它类、自己和子类可以访问 | 只有包内其它类、自己和子类可以访问
缺省（`default`） | 只有包内其它类可以访问 | 如果子类与父类在同一个包内，只有包内其它类可以访问；否则相当于 `private`，不能访问
`private` | 只有自己可以访问 | 不能访问

## 多态

在 Java 中当把一个对象赋值给一个变量时，对象的类型必须与变量的类型相匹配．但由于 Java 有继承的概念，便可重新定义为 一个变量可以保存其所声明的类型或该类型的任何子类型．

如果一个类型实现了接口，也可以称之为该接口的子类型．

Java 中保存对象类型的变量是多态变量．「多态」这个术语（字面意思是许多形态）是指一个变量可以保存不同类型（即其声明的类型或任何子类型）的对象．

多态变量：

1. Java 的对象变量是多态的，它们能保存不止一种类型的对象．
2. 它们可以保存的是声明类型的对象，或声明类型子类的对象．
3. 当把子类的对象赋给父类的变量的时候，就发生了向上转型．

## 泛型

泛型指在类定义时不设置类中的属性或方法参数的具体类型，而是在使用（或创建对象）时再进行类型的定义．泛型本质是参数化类型，即所操作的数据类型被指定为一个参数．

泛型提供了编译时类型安全检测的机制，该机制允许编译时检测非法类型．

## 接口

### 简介

接口（Interface）在 Java 中是一个抽象类型，是抽象方法的集合，通常以 `interface` 来声明．一个类通过实现接口的方式，从而来继承接口的抽象方法．

接口并不是类，编写接口的方式和类很相似，但是它们属于不同的概念．类描述对象的属性和方法．接口则包含类要实现的方法．

除非实现接口的类是抽象类，否则该类要定义接口中的所有方法．

接口无法被实例化，但是可以被实现．一个实现接口的类，必须实现接口内所描述的所有方法，否则就必须声明为抽象类．另外，在 Java 中，接口类型可用来声明一个变量，他们可以成为一个空指针，或是被绑定在一个以此接口实现的对象．

### 与类的区别

1. 接口不能用于实例化对象．
2. 接口没有构造方法．
3. 接口中所有的方法必须是抽象方法，Java 8 之后接口中可以使用 `default` 关键字修饰的非抽象方法．
4. 接口不能包含成员变量，除了 static 和 final 变量．
5. 接口不是被类继承了，而是要被类实现．
6. 接口支持多继承，类不支持多继承．

### 声明

    1
    2
    3
    4
    [可见度] interface 接口名称 [extends 其他的接口名] {
            // 声明变量
            // 抽象方法
    }

### 实现

    1
    ...implements 接口名称[, 其他接口名称, 其他接口名称..., ...] ...

## Lambda 表达式

### 简介

lambda 表达式也可称为闭包，是 Java 8 的最重要的新特性．

lambda 表达式允许把函数作为一个方法的参数（函数作为参数传递进方法中）．

使用 lambda 表达式可以使代码变的更加简洁紧凑．

### 语法

- 可选类型声明：不需要声明参数类型，编译器可以统一识别参数值．
- 可选的参数圆括号：一个参数无需定义圆括号，但多个参数需要定义圆括号．
- 可选的大括号：如果主体包含了一个语句，就不需要使用大括号．
- 可选的返回关键字：如果主体只有一个表达式返回值则编译器会自动返回值，大括号需要指定表达式返回了一个数值．

lambda 表达式声明方式如下：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    // 1. 不需要参数，返回值为 5
    () -> 5

    // 2. 接收一个参数（数字类型），返回其 2 倍的值
    x -> 2 * x

    // 3. 接受 2 个参数（数字）并返回他们的差值
    (x, y) -> x – y

    // 4. 接收 2 个 int 类型整数并返回他们的和
    (int x, int y) -> x + y

    // 5. 接受一个 String 对象并在控制台打印，不返回任何值（看起来像是返回 void）
    (String s) -> System.out.print(s)

以字符串数组按长度排序的自定义比较器为例，lambda 表达式可以按如下形式应用．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    import java.util.Arrays;

    public class Main {
        static PrintWriter out = new PrintWriter(System.out);

        public static void main(String[] args) {
            String[] plants = {"Mercury", "venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
            Arrays.sort(plants, (String first, String second) -> (first.length() - second.length()));
            for (String word : plants) {
                out.print(word + " ");
            }
            out.close();
        }
    }

也可以类似下面的例子在 lambda 表达式中使用多条语句．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    import java.io.PrintWriter;
    import java.util.Arrays;

    public class Main {
        static PrintWriter out = new PrintWriter(System.out);

        public static void main(String[] args) {
            String[] plants = {"Mercury", "venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
            Arrays.sort(plants, (first, second) ->
            {
                // 形参不写类型，可以从上下文判断出
                int result = first.length() - second.length();
                return result;
            });
            for (String word : plants) {
                out.print(word + " ");
            }
            out.close();
        }
    }

其中，`->` 是一个推导符号，表示前面的括号接收到参数，推导后面的返回值（其实就是传递了方法）．

### 函数式接口

1. 是一个接口，符合 Java 接口定义．
2. 只包含一个抽象方法的接口．
3. 因为只有一个未实现的方法，所以 lambda 表达式可以自动填上去．

函数式接口使用方式如下：

输出长度为 2 的倍数的字符串

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    import java.io.PrintWriter;

    public class Main {
        static PrintWriter out = new PrintWriter(System.out);

        public static void main(String[] args) {
            String[] plants = {"Mercury", "venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
            Test test = s -> {  // lambda 表达式作为函数式接口的实例
                if (s.length() % 2 == 0) {
                    return true;
                }
                return false;
            };
            for (String word : plants) {
                if (test.check(word)) {
                    out.print(word + " ");
                }
            }
            out.close();
        }
    }

    interface Test {
        public boolean check(String s);
    }

实现加减乘除四则运算

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    import java.io.PrintWriter;

    public class Main {
        static PrintWriter out = new PrintWriter(System.out);

        public static double calc(double a, double b, Calculator util) {
            return util.operation(a, b);
        }

        public static void main(String[] args) {
            Calculator util[] = new Calculator[4];  // 定义函数式接口数组
            util[0] = (a, b) -> a + b;
            util[1] = (a, b) -> a - b;
            util[2] = (a, b) -> a * b;
            util[3] = (a, b) -> a / b;
            double a = 20, b = 15;
            for (Calculator c : util) {
                System.out.println(calc(a, b, c));
            }
            out.close();
        }
    }

    interface Calculator {
        public double operation(double a, double b);
    }

## Collection

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

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

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

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

### 容器定义

当定义泛型容器类时，需要在定义时指定数据类型．如果不指定数据类型，而当成 `Object` 类型随意添加数据，在 Java 8 中虽能编译通过，但会有很多警告风险．

例如，如下定义方式是安全的，容器中只接受 `Integer` 类型．

    1
    List<Integer> list1 = new LinkedList<>();

而如下定义方式会出现警告．

    1
    2
    3
    4
    5
    6
    List list = new ArrayList<>();
    list.add(1);
    list.add(true);
    list.add(1.01);
    list.add(1L);
    list.add("I am String");

因此，如果没有特殊需求的话不推荐第 2 种行为，编译器无法帮忙检查存入的数据是否安全．`list.get(index)` 取值时无法明确数据的类型（取到的数据类型都为 `Object`），需要手动转回原来的类型，稍有不慎可能出现误转型异常．

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

### List

#### ArrayList

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

##### 初始化

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    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<Integer> list1 = new ArrayList<>();  // 创建一个名字为 list1 的可自增数组，初始长度为默认值（10）
            List<Integer> list2 = new ArrayList<>(30);  // 创建一个名字为list2的可自增数组，初始长度为 30
            List<Integer> list3 = new ArrayList<>(list2);  // 创建一个名字为 list3 的可自增数组，使用 list2 里的元素和 size 作为自己的初始值
        }
    }

#### LinkedList

`LinkedList` 是双链表．

##### 初始化

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    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<Integer> list1 = new LinkedList<>();  // 创建一个名字为 list1 的双链表
            List<Integer> list2 = new LinkedList<>(list1);  // 创建一个名字为 list2 的双链表，将 list1 内所有元素加入进来
        }
    }

#### 常用方法

以下均用 `this` 代替当前 `List<Integer>`：

函数名 | 功能
--- | ---
`size()` | 返回 `this` 的长度
`add(Integer val)` | 在 `this` 尾部插入 `val` 元素
`add(int idx, Integer e)` | 在 `this` 的 `idx` 位置插入 `e` 元素
`get(int idx)` | 返回 `this` 中第 `idx` 位置的值，若越界则抛出异常
`set(int idx, Integer e)` | 修改 `this` 中第 `idx` 位置的值为 `e`

使用案例及区别对比：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    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<Integer> array = new ArrayList<>();
        static List<Integer> 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)
        }

    }

#### 遍历

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    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<Integer> array = new ArrayList<>();
        static List<Integer> 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<Integer> iterator1 = array.iterator();
            Iterator<Integer> 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` 实现普通队列，底层是链表模拟队列．

##### 初始化

    1
    Queue<Integer> q = new LinkedList<>();

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

#### ArrayDeque

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

##### 初始化

    1
    Queue<Integer> 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` 的栈和队列行为都是 𝑂(1)O(1) 时间复杂度，`ArrayDeque` 的入栈和入队有可能会触发扩容，但从均摊分析上看依然是 𝑂(1)O(1) 时间复杂度．
6. 额外内存消耗上：`ArrayDeque` 在数组的头指针和尾指针外部有闲置空间，而 `LinkedList` 在节点上增加了前驱和后继指针．

#### PriorityQueue

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

##### 初始化

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

#### 常用方法

下表中队列定义为 `Queue<Integer>`．

函数名 | 功能
--- | ---
`size()` | 返回当前队列长度
`add(Integer val)` | 将 `val` 插入队列，如果插入时违反了队列的容量限制，将抛出异常
`offer(Integer val)` | 将 `val` 插入队列，如果插入时违反了队列的容量限制，则插入失败，但不会抛出异常
`isEmpty()` | 判断队列是否为空，为空则返回 `true`
`peek()` | 返回队头元素，若队列为空返回 `null`
`poll()` | 返回并删除队头元素，若队列为空返回 `null`

使用案例及区别对比：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    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<Integer> q1 = new LinkedList<>();
        static Queue<Integer> 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)
        }
    }

#### 遍历

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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<Integer> q1 = new LinkedList<>();
        static Queue<Integer> q2 = new PriorityQueue<>();

        static void test() {
            while (!q1.isEmpty()) {  // 复杂度为 O(n)
                out.println(q1.poll());
            }
            while (!q2.isEmpty()) {  // 复杂度为 O(nlogn)
                out.println(q2.poll());
            }
        }

    }

### Deque

`Deque` 是 `Java` 中的双端队列，我们通常用其进行队列的操作以及栈的操作．

#### 主要函数

下表中队列定义为 `Deque<Integer>`．

函数名 | 功能
--- | ---
`addFirst(Integer val)` | 将 `val` 插入队头，如果插入时违反了队列的容量限制，将抛出异常
`offerFirst(Integer val)` | 将 `val` 插入队头，如果插入时违反了队列的容量限制，则插入失败，但不会抛出异常
`removeFirst()` | 返回并删除队头元素，如果队列为空，将抛出异常
`pollFirst()` | 返回并删除队头元素，如果队列为空，则返回 `null`
`peekFirst()` | 返回队头元素，如果队列为空，则返回 `null`
`push(Integer val)` | 将 `val` 插入队头，等效于 `addFirst`
`pop()` | 返回并删除队头元素，等效于 `removeFirst`
`remove()` | 删除队头元素，等效于 `removeFirst`
`poll()` | 删除队头元素，等效于 `pollFirst`
`addLast(Integer val)` | 将 `val` 插入队尾，如果插入时违反了队列的容量限制，将抛出异常
`offerLast(Integer val)` | 将 `val` 插入队尾，如果插入时违反了队列的容量限制，则插入失败，但不会抛出异常
`removeLast()` | 返回并删除队尾元素，如果队列为空，将抛出异常
`pollLast()` | 返回并删除队尾元素，如果队列为空，则返回 `null`
`peekLast()` | 返回队尾元素，如果队列为空，则返回 `null`
`add(Integer val)` | 将 `val` 插入队尾，等效于 `addLast`
`offer(Integer val)` | 将 `val` 插入队尾，等效于 `offerLast`

#### 栈的操作

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    import java.util.ArrayDeque;
    import java.util.Deque;

    public class Main {
        static Deque<Integer> stack = new ArrayDeque<>();
        static int[] a = {1, 2, 3, 4, 5};

        public static void main(String[] args) {
            for (int v : a) {
                stack.push(v);
            }
            while (!stack.isEmpty()) { //输出 5 4 3 2 1
                System.out.println(stack.pop());
            }
        }
    }

#### 双端队列的操作

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    import java.util.ArrayDeque;
    import java.util.Deque;

    public class Main {
        static Deque<Integer> deque = new ArrayDeque<>();

        static void insert() {
            deque.addFirst(1);
            deque.addFirst(2);
            deque.addLast(3);
            deque.addLast(4);
        }

        public static void main(String[] args) {
            insert();
            while (!deque.isEmpty()) { //输出 2 1 3 4
                System.out.println(deque.poll());
            }
            insert();
            while (!deque.isEmpty()) { //输出 4 3 1 2
                System.out.println(deque.pollLast());
            }
        }
    }

### Set

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

#### HashSet

随机位置插入的 `Set`．

##### 初始化

    1
    Set<Integer> s1 = new HashSet<>();

#### LinkedHashSet

保持插入顺序的 `Set`．

##### 初始化

    1
    Set<Integer> s2 = new LinkedHashSet<>();

#### TreeSet

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

##### 初始化

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

##### TreeSet 的更多使用

这些方法是 `TreeSet` 新创建并实现的，我们无法使用 `Set` 接口调用以下方法，因此我们创建方式如下：

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

下表中均用 `this` 代替当前 `TreeSet<Integer>`．

函数名 | 功能
--- | ---
`first()` | 返回 `this` 中第一个元素，无则返回 `null`
`last()` | 返回 `this` 中最后一个元素，无则返回 `null`
`floor(Integer val)` | 返回 `this` 中小于等于 `val` 的第一个元素，无则返回 `null`
`ceiling(Integer val)` | 返回 `this` 中大于等于 `val` 的第一个元素，无则返回 `null`
`higher(Integer val)` | 返回 `this` 中大于 `val` 的第一个元素，无则返回 `null`
`lower(Integer val)` | 返回 `this` 中小于 `val` 的第一个元素，无则返回 `null`
`pollFirst()` | 返回并删除 `this` 中第一个元素，无则返回 `null`
`pollLast()` | 返回并删除 `this` 中最后一个元素，无则返回 `null`

代码示例：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    import java.util.TreeSet;

    public class Main {
        static int[] a = {4,7,1,2,3,6};

        public static void main(String[] args) {
            TreeSet<Integer> set = new TreeSet<>();
            for(int v:a) {
                set.add(v);
            }
            Integer a2 = set.first();
            System.out.println(a2); //返回 1
            Integer a3 = set.last();
            System.out.println(a3); //返回 7
            Integer a4 = set.floor(5);
            System.out.println(a4); //返回 4
            Integer a5 = set.ceiling(6);
            System.out.println(a5); //返回 6
            Integer a6 = set.higher(7);
            System.out.println(a6); //返回 null
            Integer a7 = set.lower(2);
            System.out.println(a7); //返回 1
            Integer a8 = set.pollFirst();
            System.out.println(a8); //返回 1
            Integer a9 = set.pollLast();
            System.out.println(a9); //返回 7
        }
    }

#### Set 常用方法

函数名 | 功能
--- | ---
`size()` | 返回当前集合的大小
`add(Integer val)` | 将 `val` 插入集合
`contains(Integer val)` | 判断集合中是否有元素 `val`
`addAll(Collection e)` | 将容器 `e` 里的所有元素添加进当前集合
`retainAll(Collection e)` | 删除当前集合中未出现在容器 `e` 中的元素，即求当前集合与 `e` 的交集
`removeAll(Collection e)` | 删除当前集合中出现在容器 `e` 中的元素，即求当前集合与 `e` 的差集

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    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<Integer> s1 = new HashSet<>();
        static Set<Integer> 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<Integer> res = new HashSet<>();
            res.addAll(s1);
            res.addAll(s2);
        }

        static void test2() {  // s1 与 s2 的交集
            Set<Integer> res = new HashSet<>();
            res.addAll(s1);
            res.retainAll(s2);
        }

        static void test3() {  // 差集：s1 - s2
            Set<Integer> res = new HashSet<>();
            res.addAll(s1);
            res.removeAll(s2);
        }
    }

#### 遍历

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    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<Integer> s1 = new HashSet<>();
        static Set<Integer> s2 = new LinkedHashSet<>();

        static void test() {
            for (int key : s1) {
                out.println(key);
            }
            out.close();
        }
    }

### Map

`Map` 是维护键值对 `<Key, Value>` 的一种数据结构，其中 `Key` 唯一．

#### HashMap

随机位置插入的 `Map`．

##### 初始化

    1
    Map<Integer, Integer> map1 = new HashMap<>();

#### LinkedHashMap

保持插入顺序的 `Map`．

##### 初始化

    1
    Map<Integer, Integer> map2 = new LinkedHashMap<>();

#### TreeMap

保持 `key` 有序的 `Map`，默认升序．

##### 初始化

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

#### 常用方法

以下均用 `this` 代替当前 `Map<Integer, Integer>`：

函数名 | 功能
--- | ---
`put(Integer key, Integer value)` | 将 `<key, value>` 插入 `this`
`size()` | 返回 `this` 的大小
`containsKey(Integer key)` | 判断 `this` 中是否有存在某个元素的键为 `key`
`get(Integer key)` | 返回 `this` 中键为 `key` 的元素对应的值
`keySet()` | 将 `this` 中所有元素的键作为集合返回

使用案例：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    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<Integer, Integer> map1 = new HashMap<>();
        static Map<Integer, Integer> map2 = new LinkedHashMap<>();
        static Map<Integer, Integer> map3 = new TreeMap<>();
        static Map<Integer, Integer> 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();
        }
    }

#### 遍历

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    import java.io.PrintWriter;
    import java.util.HashMap;
    import java.util.Map;

    public class Main {
        static PrintWriter out = new PrintWriter(System.out);

        static Map<Integer, Integer> map1 = new HashMap<>();

        static void print() {
            for (int key : map1.keySet()) {
                out.println(key + " " + map1.get(key));
            }
        }
    }

当然，键值的类型也可以更改．例如 `Map` 也可以定义为：

    1
    Map<String, Set<Integer>> map = new HashMap<>();

## Arrays

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

### Arrays.sort()

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

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    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<Integer>() {  // 3
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });
            Arrays.sort(b, firstIdx, lastIdx, new Comparator<Integer>() {  // 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)O(n 2)．
2. 当 `Arrays.sort` 的参数数组元素类型为非基本数据类型时，则默认为 `legacyMergeSort` 和 `TimSort`（归并排序），复杂度为 𝑂(𝑛 l o g⁡𝑛)O(n log⁡n)．

可以通过如下代码验证：

Codeforces 1646B - Quality vs Quantity

有 𝑛 n 个整数，你需要将其分为两组，是否能存在某一组的长度小于另一组，同时和大于它．

例题代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    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 修改为 int 会导致 TLE
            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();
        }
    }

### Arrays.binarySearch()

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

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    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
        }
    }

源码如下：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    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` 的元素类型均为对象类型，所以始终是归并排序去处理．

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

底层源码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

### Collections.binarySearch()

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

    1
    Collections.binarySearch(list, key);

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

### Collections.swap()

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

    1
     Collections.swap(list, i, j);

## 其他

### 数值比较问题

在 Java 中，如果单纯是数值类型，`-0.0 = 0.0`．若是对象类型，则 `-0.0 != 0.0`．如果尝试用 `Set` 统计斜率数量时，这个问题就会带来麻烦．提供的解决方式是在所有的斜率加入 `Set` 前将值增加 `0.0`．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    import java.io.PrintWriter;

    public class Main {
        static PrintWriter out = new PrintWriter(System.out);

        static void A() {
            Double a = 0.0;
            Double b = -0.0;
            out.println(a.equals(b));  // false
        }

        static void B() {
            Double a = 0.0;
            Double b = -0.0 + 0.0;
            out.println(a.equals(b));  // true
        }

        static void C() {
            double a = 0.0;
            double b = -0.0;
            out.println(a == b);  // true
        }

        public static void main(String[] args) {
            A();
            B();
            C();
            out.close();
        }
    }

## 参考资料

1. Input & Output - USACO Guide ↩

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, 1804040636, aofall, HeRaNO, shuzhouliu, yusancky, c-forrest, caopengrun, CCXXXI, ImpleLee, megakite, optimize-2, Qubik65536, untitledunrevised, ZnPdCo
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用