競技プログラミングで使うJava API

入力
- Scanner　★★★
  - 入力例と実装例
- BufferedReader　★★★
  - 先ほどと同じ入力例に対する実装例
出力
- System.out　★★★
- PrintWriter　★★
文字列
- String　★★★
- StringBuilder　★★
数値、数学
日付、時刻
- LocalDate　★
- 現在時刻取得　★
配列、コレクションユーティリティ
- Arrays　★★★
  - sort
  - binarySearch
  - fill
  - copyOf
- Collections　★★
List
- ArrayList　★★
Set
Map
- HashMap　★★
- TreeMap　★★
Queue
- ArrayDeque　★★
- PriorityQueue　★★
コレクションまとめ

使用頻度（★3段階で記載）、使用方法、使いどころなど思いつくことを書き綴ってみます。
だいたいは執筆時点までの1年半ほどの競プロ歴の中で自分が使ったことがあるものですが、これを書いている間に存在を知って、使えるかもと思ったものも載せています。
AtCoderのレート1000になる頃までには、使用頻度が低いもの以外はだいたい知っておきたいくらいの内容だと思います。

入力

Scanner　★★★

言語ごとの入出力例とかでよく紹介されていそうなやつ。
区切りごとに読み込めるし、受け取る型ごとに専用のメソッドがあるので扱いやすい。
入力が横にスペース区切りで並んでいても、縦に改行区切りで並んでいても、同じ実装で読み込める。
競プロでは滅多にないと思うが、スペースも文字として受け取りたい場合は多少ややこしくなるかも。
最大のデメリットは、遅いこと。入力が30万個以上とかあって、実行時間制限が厳しい問題では、入出力が遅いことで無用なTLEを出すことが稀にある。

入力例と実装例

$1 \leq N, D, A_i \leq 10^9$
$1 \leq L \leq 10^{18}$
$N, L, A_i$ は整数
$D$ は実数
$S_i$ は英小文字列
$T$ は英小文字とスペースからなる文字列

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long l = sc.nextLong();
double d = sc.nextDouble();

int[] a = new int[n];
for (int i = 0; i < n; i++) {
    a[i] = sc.nextInt();
}

String[] s = new String[n];
for (int i = 0; i < n; i++) {
    s[i] = sc.next();
}

sc.nextLine(); // カーソルがS_Nの直後にある状態のため、改行を捨ててTの直前に進む
String t = sc.nextLine();

BufferedReader　★★★

Scannerの1.5～2倍くらい？は高速。
readLineメソッドで1行ごとに読み込むのが基本なので、スペースで区切ったり数値に変換したりなどは自分で処理しなければならない。
以下のソースで、変数「sa」の添え字を間違えるリスクもある。

先ほどと同じ入力例に対する実装例

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" "); // スペースで分割
int n = Integer.parseInt(sa[0]);
long l = Long.parseLong(sa[1]);
double d = Double.parseDouble(sa[2]);

int[] a = new int[n];
sa = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
    a[i] = Integer.parseInt(sa[i]);
}

String[] s = new String[n];
for (int i = 0; i < n; i++) {
    s[i] = br.readLine();
}

String t = br.readLine();

出力

System.out　★★★

プログラミングの勉強を始めてほぼ一番最初に見るやつだと思う。
10万回以上とか呼び出していると、速度が気になる。
printfメソッドとかもあるけど自分が使いこなせていないので省略。

// xはint、String、char[]などの変数
System.out.print(x); // 末尾に改行なし
System.out.println(x); // 末尾に改行あり

PrintWriter　★★

たくさん出力する場合は、まとめて出力すればいくらか速度改善できるので、後述のStringBuilderで1つの長い文字列にしてから出力するか、PrintWriterでラッピングする。
System.outとほぼ同じメソッドが揃っているので、実装上はnewとflushを書く手間が余計にかかる程度の違いしかない。

PrintWriter pw = new PrintWriter(System.out);
pw.print(x); // 改行なし
pw.println(x); // 改行あり
pw.flush(); // これを呼び出さないと出力されない

文字列

String　★★★

とりあえず、どういうことができるメソッドが存在するのか、代表的なものをなんとなく知っていればいいのではないかと。
以下はおおよそ使用頻度の高そうな順。

メソッド名	内容
length	文字数を取得。文字数分ループしたい時とかに。
charAt	$i$ 番目（ $0 \leq i <$ length()）の文字を取得
toCharArray	文字配列（char[]）に変換。「s.charAt(i)」と書くのが面倒で、「s[i]」と書きたい時に。
equals	2つの文字列が等しいか比較（「==」を使っては駄目）
compareTo	2つの文字列の辞書順大小比較。
split	指定の区切り文字で分割。BufferedReaderで読み込む時くらいしか使わなそう。
valueOf	数値等を文字列に変換（staticメソッド）
substring	部分文字列を取得
indexOf	指定の文字(列)が出現する最初のインデックスを取得
toLowerCase	文字列に含まれる大文字を全て小文字に変換
toUpperCase	文字列に含まれる小文字を全て大文字に変換
replaceAll	文字列内に出現する指定の文字列を別の文字列に一括置換

String str = "abcDbF";
int a      = str.length(); // 6
char b     = str.charAt(5); // 'F'
char[] c   = str.toCharArray(); // {'a', 'b', 'c', 'D', 'b', 'F'}
boolean d  = str.equals("abcDbF"); // true
boolean e  = str.compareTo("abcE") < 0; // true（str < "abcE" の比較をする意図）
String[] f = str.split("b"); // {"a", "cD", "F"}
String g   = String.valueOf(123); // "123"
String h   = str.substring(1, 4); // "bcD"
int i      = str.indexOf("cDb"); // 2
String j   = str.toLowerCase(); // "abcdbf"
String k   = str.toUpperCase(); // "ABCDBF"
String l   = str.replaceAll("b", "xy"); // "axycDxyF"

StringBuilder　★★

文字列を頻繁に編集する場合はStringBuilderを使う。
例えば以下のように"a"を「+」で10万回連結するような処理を行うと、"a"、"aa"、"aaa"、 $\cdots$ という10万個のStringオブジェクトが生成されてしまい、MLEになったりする。

String str = "";
for (int i = 0; i < 100000; i++) {
    str += "a";
}

StringBuilderでは、文字(列)の追加、挿入、削除、置換などができる。挿入や削除を先頭の方に行うと、 $O($ 文字列の長さ $)$ くらいの時間がかかってしまうことに注意。
あとStringには存在しない操作として、reverseメソッドで文字列を逆順にすることができる。

StringBuilder sb = new StringBuilder("abcde");
sb.reverse();
System.out.println(sb.toString()); // edcba

$N$ 個の要素 $A_1$ ～ $A_N$ をスペース区切りで1行に出力することを求められる場合、最近のAtCoderでは改行区切りで $N$ 行に出力しても通ることが多いようだが、きちんとやる場合は例えば以下のようにする。

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append(a[i]).append(' ');
}
sb.deleteCharAt(sb.length() - 1); // 末尾のスペース削除
System.out.println(sb.toString());

数値、数学

Math　★★★

やはり、とりあえずどういうことができるメソッドが存在するのか、代表的なものをざっと知っておきたい。
以下はおおよそ使用頻度の高そうな順。

メソッド名	内容
min	2数の小さい方
max	2数の大きい方
abs	絶対値
ceil	切り上げ
floor	切り捨て
sqrt	平方根
cbrt	立方根
pow	累乗（自作した方が使い勝手が良いが一応）
hypot	$\sqrt {x^2+y^2}$ （2点間のユークリッド距離）
PI	円周率（定数）
atan2	アークタンジェント（ラジアン単位）
(sin等)	各三角関数とその逆関数ひと通り存在する

※全体的に戻り値がdouble型のメソッドが多いため、大きな値の場合は誤差に注意。例えば、 $10^{14}$ 以上くらいのlong値に対してsqrtとceilを使っても、平方根以上の最小の整数が得られるとは限らない。

int a    = Math.min(1, 2); // 1
int b    = Math.max(-1, -2); // -1
int c    = Math.abs(-1); // 1
double d = Math.ceil(1.23); // 2.0
double e = Math.ceil(-1.23); // -1.0
double f = Math.floor(-1.23); // -2.0
double g = Math.sqrt(4); // 2.0
double h = Math.cbrt(8); // 2.0
double i = Math.pow(2, 4); // 16.0
double j = Math.hypot(3, 4); // 5.0
double k = Math.PI; // 3.141592653589793
double l = Math.atan2(Math.sqrt(3), 1); // 1.0471975511965976（60度）

BigInteger　★

乱暴に言えば、桁数上限のない整数。非常に大きい数を素因数分解して扱ったりなど面倒なことをしなくても、そのまんま計算してしまえば大丈夫といったことがたまにある。
以下はまず四則演算等の基本的なもの。

メソッド名	内容
add	+
subtract	-
multiply	*
divide	/
remainder	%
mod	ほぼ%だが、引数は正整数のみ指定可
compareTo	比較
negate	$-1$ 倍

BigInteger b5 = BigInteger.valueOf(5);
BigInteger b3 = BigInteger.valueOf(3);

BigInteger a = b5.add(b3); // 8
BigInteger b = b5.subtract(b3); // 2
BigInteger c = b5.multiply(b3); // 15
BigInteger d = b5.divide(b3); // 1
BigInteger e = b5.remainder(b3); // 2
BigInteger f = b5.mod(b3); // 2
boolean g    = b5.compareTo(b3) > 0; // true（b5 > b3 の比較をする意図）
boolean h    = b5.compareTo(b3) == 0; // false（b5 == b3 の比較をする意図）
BigInteger i = b5.negate(); // -5

「a += b」のような意図で使いたい場合、代入が必要なことを初めは忘れがちかもしれない。

a.add(b); // 計算結果を捨てている
a = a.add(b); // a = a + b

使用頻度は低いが、一応ビット演算系のもの。
桁に関することは全て2進数表現での話。

メソッド名	内容
and	&
or	\|
xor	^
andNot	引数の値が1になっている桁を0にする
bitCount	1の桁数
bitLength	桁数
setBit	下から $N$ 桁目を1にする（ $0 \leq N$ ）
clearBit	下から $N$ 桁目を0にする（ $0 \leq N$ ）
flipBit	下から $N$ 桁目を反転する（ $0 \leq N$ ）
shiftLeft	<<
shiftRight	>>

bitCountはIntegerやLongクラスにもあるので大抵はそちらで十分。

BigInteger b9 = new BigInteger("1001", 2);
BigInteger b5 = new BigInteger("0101", 2);

BigInteger a = b9.and(b5); // 0001 = 1
BigInteger b = b9.or(b5); // 1101 = 13
BigInteger c = b9.xor(b5); // 1100 = 12
BigInteger d = b9.andNot(b5); // 1000 = 8
int e        = b9.bitCount(); // 2
int f        = b9.bitLength(); // 4
BigInteger g = b9.setBit(1); // 1011 = 11
BigInteger h = b9.clearBit(0); // 1000 = 8
BigInteger i = b9.flipBit(3); // 0001 = 1
BigInteger j = b9.flipBit(2); // 1101 = 13
BigInteger k = b9.shiftLeft(2); // 100100 = 36
BigInteger l = b9.shiftRight(1); // 100 = 4

それから、いくつかの便利メソッドもあるので、存在を知っておいてもいいかも。ただ、自作ライブラリを用意した方が、BigIntegerへの変換が伴わないので実装が楽で性能も良い。結局ライブラリ整備できるまでのその場しのぎ用でしかないかも。

メソッド名	内容
gcd	最大公約数
modInverse	逆元
modPow	累乗のmod

BigInteger b2 = BigInteger.valueOf(2);
BigInteger b3 = BigInteger.valueOf(3);
BigInteger b4 = BigInteger.valueOf(4);
BigInteger b5 = BigInteger.valueOf(5);
BigInteger b6 = BigInteger.valueOf(6);
BigInteger b9 = BigInteger.valueOf(9);
BigInteger bm = BigInteger.valueOf(1000000007);

BigInteger a = b6.gcd(b9); // 3
BigInteger b = b2.modInverse(bm); // 500000004
BigInteger c = b3.modPow(b4, b5); // 3^4 % 5  =  81 % 5  =  1

BigDecimal　★

小数を正確に計算できる。競プロでは何も考えずにdouble型で計算しても許容誤差に収まるように作られている問題が多いが、稀にある誤差をテーマとした問題では出番があるかも。
主に割り算の際に、小数点以下の桁数と丸め方（四捨五入、切り捨てなど）を指定する。その他の基本的な用法はBigIntegerと概ね同様。
結果を指数表記で出力したくない場合は、toPlainStringメソッドを使う。

なお、BigDecimal型に変換する過程でfloatやdouble型にしてはならない。それでは最初にBigDecimal型の値を得るまでの間に誤差が発生する可能性があり、BigDecimalを使う意味がない。
int、long、Stringからの変換であれば問題なし。

long a = 1234567890123456789L;
BigDecimal ba = BigDecimal.valueOf(a);
System.out.println(ba.toPlainString()); // 1234567890123456789：OK

double d = 1234567890123456789d;
BigDecimal bd = BigDecimal.valueOf(d);
System.out.println(bd.toPlainString()); // 1234567890123456770：NG

String s = "1234567890123456789";
BigDecimal bs = new BigDecimal(s);
System.out.println(bs.toPlainString()); // 1234567890123456789：OK

日付、時刻

LocalDate　★

今までにやった過去問全体で1～2回使ったかどうかくらいなので、クラス名だけで詳細は省略。
Java8で導入されたもので、昔のjava.util.Dateより使いやすくなっていると思う。
月の最終日とか、うるう年とか、曜日とか、自力実装が面倒な要素がある場合に、楽ができることがあるかもしれない。
時刻の場合は、自分で秒に換算したりしてもそれほど大したことはなく、あえてLocalTimeを使ったりする必要はあまりないのではないだろうか。
　

現在時刻取得　★

1970年1月1日0時を起点とした時刻（ミリ秒単位、long型）の取得方法。
使うのはマラソン（ヒューリスティック）型のコンテスト限定かも。
例えば実行時間制限が $2$ 秒だったら、現在時刻と処理の最初で取得しておいた時刻の差が $1800$ 以下の間実行し続けるというように、制限時間を使い切るような制御を行うのに使用する。

long a = System.currentTimeMillis();

long b = Instant.now().toEpochMilli();

配列、コレクションユーティリティ

Arrays　★★★

配列に関するユーティリティクラス。ソートだけは知らないと論外なレベルで非常によく使うが、それ以外はおまけ程度。
以下は全てstaticメソッド。 $N$ は配列の要素数。

メソッド名	内容	時間計算量
sort	昇順ソート	$O(NlogN)$
binarySearch	二分探索	$O(logN)$
fill	全要素に特定の値を設定	$O(N)$
copyOf	コピーを生成	$O(N)$

sort

プリミティブ型配列は引数に渡すだけで簡単だが、自然順序付けがないオブジェクト型配列はComparatorも指定する必要がある。
Comparatorの指定にはラムダ式を使うのが楽だと思う。以下のソースのように、昇順にソートしたい場合は「引数1(の項目) $-$ 引数2(の項目)」、降順の場合は「引数2(の項目) $-$ 引数1(の項目)」とすればよい。
reverseメソッドが存在しないことが不便で、reverseメソッドを自作でもしなければ、プリミティブ型配列は昇順ソートしかできない。数値ならば、各要素を $-1$ 倍してソートしてまた $-1$ 倍する方法も考えられるが。
自然順序付けがあるオブジェクト型配列の場合は、「Collections.reverseOrder()」（逆順を示すComparator）を指定することで降順ソートができる。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        // プリミティブ
        int[] a = {2, 5, 1, 4, 3};
        Arrays.sort(a); // {1, 2, 3, 4, 5}
        reverse(a); // {5, 4, 3, 2, 1}

        // 自然順序付けがあるオブジェクト
        String[] s = {"aaa", "b", "aa", "ba", "ab"};
        Arrays.sort(s); // {"aa", "aaa", "ab", "b", "ba"}
        Arrays.sort(s, Collections.reverseOrder()); // {"ba", "b", "ab", "aaa", "aa"}

        // 自然順序付けがないオブジェクト
        Hoge[] array = new Hoge[5];
        // ※要素を設定する部分省略
        Arrays.sort(array, (o1, o2) -> o1.a - o2.a); // aの昇順
        Arrays.sort(array, (o1, o2) -> o2.b - o1.b); // bの降順
        Arrays.sort(array, (o1, o2) -> o1.s.compareTo(o2.s)); // sの昇順
    }

    static class Hoge {
        int a, b;
        String s;
    }

    // ↓要自作
    static void reverse(int[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            int tmp = a[i];
            a[i] = a[a.length - 1 - i];
            a[a.length - 1 - i] = tmp;
        }
    }
}

binarySearch

一応取り上げてはおくものの、使える条件が結構限られる。あくまで、検索値と一致する要素を見つけることに重点が置かれている印象。

要素が昇順にソートされていること。降順にソートされているのは駄目。
検索値を持つ要素が複数存在する場合、どれが返されるかは保証なし。複数存在する場合は下端と上端のインデックスが知りたいというような場合は使えない。
検索値を持つ要素が存在しない場合、負の値が返される。戻り値を「~」でビット反転すると、「検索値よりも大きな最初の要素のインデックス」が得られる。
int型の配列に対してdoubleの検索値（目的の値-0.5と+0.5）を指定することで、下端のインデックスと上端のインデックス+1を得られると思うかもしれないが、配列と同じ型の検索値を指定するメソッドしか存在しない。　これに関しては、整数しか格納しないdouble型の配列であれば、できることはできるが。
いわゆる「答えの二分探索」のような、何らかの条件を満たす満たさないの境界を探すようなことはできない。検索値との大小比較のみ。

以上を考慮して使えないようであれば、「めぐる式二分探索」と呼ばれているものなどを参考に自力実装する。

// val: 0  →  idx: 0
// val: 1  →  idx: 0
// val: 5  →  idx: 2 or 3
// val: 9  →  idx: 5
int[] a = {1, 2, 5, 5, 8};
int idx = Arrays.binarySearch(a, val);
if (idx < 0) idx = ~idx;

// val: 4.5  →  idx: 1
// val: 5.5  →  idx: 4
double[] a = {1, 5, 5, 5, 9};
int idx = Arrays.binarySearch(a, val);
if (idx < 0) idx = ~idx;

fill

for文を書くより多少楽かな程度のもの。
以下の2つは同等の処理。（fillの中身が下のような処理）

int[] a = new int[n];
Arrays.fill(a, -1);

int[] a = new int[n];
for (int i = 0; i < n; i++) {
    a[i] = -1;
}

copyOf

これも自力実装より多少楽になった程度。
以下の3つは同等の処理。（copyOfの中身がSystem.arraycopy）

int[] a = {1, 2, 5, 6, 8};
int[] b = Arrays.copyOf(a, a.length);

int[] a = {1, 2, 5, 6, 8};
int[] b = new int[a.length];
System.arraycopy(a, 0, b, 0, a.length);

int[] a = {1, 2, 5, 6, 8};
int[] b = new int[a.length];
for (int i = 0; i < a.length; i++) {
    b[i] = a[i];
}

Collections　★★

Arraysは配列を扱うクラスだったが、CollectionsはCollection（特にList）を扱うユーティリティクラス。
以下は全てstaticメソッド。 $N$ はCollectionやListの要素数。

メソッド名	内容	時間計算量
sort	Listの昇順ソート	$O(NlogN)$
binarySearch	Listの二分探索	$O(logN)$
reverse	Listを逆順にする	$O(N)$
swap	List内の2要素を入れ替える	$O(1)$
min	Collection内の最小値	$O(N)$
max	Collection内の最大値	$O(N)$

用法は、Arraysの同名メソッドと同様であったりなどで、わかると思うので省略。
Collectionは、集合を表す最上位のインターフェースで、Listはその一種（サブインターフェース）であることに注意。
　

List

ArrayList　★★

Listインターフェースの最も基本的な実装クラス。
主な使いどころは、要素数が事前に決まっていなくて配列では扱いにくい場合。グラフの隣接リストとか。
用法は基本的なものが多いと思うが、Listに限らず、ここから先のものは全体的に計算量にも注意していきたい。

以下の $N$ は自身のListの要素数。 $M$ は引数のCollectionの要素数。

メソッド名	内容	時間計算量
get	指定位置の要素を取得	$O(1)$
size	要素数を取得	$O(1)$
isEmpty	size() == 0	$O(1)$
add	要素を末尾に追加／指定位置に挿入	$O(1)$ ／ $O(N)$
addAll	全要素を末尾に追加／指定位置に挿入	$O(M)$ ／ $O(N+M)$
remove	指定位置／指定要素を削除	$O(N)$
set	指定位置の要素を上書き	$O(1)$
contains	指定要素が含まれているか	$O(N)$
toArray	配列に変換	$O(N)$
clear	全ての要素を削除	$O(N)$

List<Integer> list = new ArrayList<>();
list.add(1); // [1]
list.add(5); // [1, 5]
list.add(3); // [1, 5, 3]
List<Integer> list2 = new ArrayList<>();
list2.add(4); // [4]
list2.add(6); // [4, 6]
list2.add(1, 2); // [4, 2, 6]

list.get(1); // 5
list.size(); // 3
list.isEmpty(); // false

list.addAll(list2); // [1, 5, 3, 4, 2, 6]
list.addAll(1, list2); // [1, 4, 2, 6, 5, 3, 4, 2, 6]

list.remove(4); // [1, 4, 2, 6, 3, 4, 2, 6]（index：4を削除）
Integer o = 4;
list.remove(o); // [1, 2, 6, 3, 4, 2, 6]（値：4の最初のものを削除）

list.set(0, 7); // [7, 2, 6, 3, 4, 2, 6]
list.contains(2); // true

Integer[] array = list.toArray(new Integer[0]);
list.clear(); // []

IntegerのListの場合、removeの引数にint型を指定するか、Integer型を指定するかで挙動が変わるので注意。
主にcontainsを使おうとしているのならば、Listでは $O(N)$ なのに対し、後述のHashSetは $O(1)$ なので、そちらを使えないか検討する。
　

Set

HashSet　★★

Setインターフェースの最も基本的な実装クラス。後述のHashMapのキーのみを使用し、値部分を無視したもの。
順序性のない重複しない要素の集合を扱う。
同じ要素を複数保持できないが、逆にその性質を利用して重複排除ができる。
特定要素が集合に存在するかどうかの判定を高速にできる。

※HashSetに格納する要素の型は、equalsメソッドとhashCodeメソッドが適切に実装されているものである必要がある。
ここでは説明しないが、標準の中ではInteger、Long、StringなどはOK。自前のオブジェクトでは上記2メソッドの実装が必須。

以下の $N$ は自身のSetの要素数。 $M$ は引数のCollectionの要素数。

メソッド名	内容	時間計算量
size	要素数を取得	$O(1)$
isEmpty	size() == 0	$O(1)$
add	要素を追加	$O(1)$
addAll	全要素を追加	$O(M)$
remove	指定要素を削除	$O(1)$
contains	指定要素が含まれているか	$O(1)$
toArray	配列に変換	$O(N)$
clear	全ての要素を削除	$O(N)$

用法は、ArrayListの同名メソッドとほぼ同様なので省略。
順序性がないため、位置を指定するメソッドは存在しない。

LinkedHashSet　★

HashSetに、要素を追加した順序の情報を持たせたもの。それ以外は同じ。
位置を指定した要素の取得などはできないが、拡張for文、toArrayメソッドなど全要素を取得するような処理で、要素を追加した順に取得できる。
使いどころはあまりないが、通ったノードの履歴を持ちながら深さ優先探索（DFS）を行う際、以下の両方の要求を満たす必要がある場合とか？

通ったノードの順番が後で必要になる（これだけならArrayListで可）
ある要素が履歴に存在するかの判定を高速で行う必要がある（これだけならHashSetで可）

自分の場合で言えば、一応順列を生成する処理で使っていた時期もあった。（ABC215-Cの解説を見たことをきっかけにbit表現を利用した方法に変えた）

import java.util.LinkedHashSet;

public class Main {
    static int n = 3;

    public static void main(String[] args) throws Exception {
        permutation(new LinkedHashSet<>());
    }

    static void permutation(LinkedHashSet<Integer> set) {
        if (set.size() == n) {
            for (int i : set) { // setに追加した順番に処理
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!set.contains(i)) { // 未使用の値の判定
                set.add(i);
                permutation(set);
                set.remove(i);
            }
        }
    }
}

実行結果

あとは、重複要素を排除したQueueとして使えるかも。（実際にやってみたことはなし。取り出せばまた同じ値を追加できるので、全体として重複排除できるわけではない。）
　

TreeSet　★★

HashSetに自動ソート機能を持たせたもの。
計算量は全体的にHashSetより悪いが、値の大小に関する便利なメソッドが多くある。

※TreeSetに格納する要素の型は、equalsメソッドとhashCodeメソッドの実装は不要だが、Comparableインターフェースを実装している必要がある。実装していない場合は、TreeSetの生成時にComparatorを指定する。（ComparatorについてはArrays.sortの節を参照）

重複要素を排除したPriorityQueueとして使うことも一応できなくはなく、例えば辺の数が多い場合のダイクストラ法で計算量改善が見込めることがある。通常は同じ頂点が大量にキューに入ってしまうところを1つにできるため。

そういった工夫ができる可能性も秘めた、非常に有用なデータ構造であると思う。

以下の $N$ は自身のSetの要素数。 $M$ は引数のCollectionの要素数。 $K$ は条件に合致する要素数。

メソッド名	内容	時間計算量
size	要素数を取得	$O(1)$
isEmpty	size() == 0	$O(1)$
add	要素を追加	$O(logN)$
addAll	全要素を追加	$O(Mlog(N+M))$
remove	指定要素を削除	$O(logN)$
contains	指定要素が含まれているか	$O(logN)$
toArray	配列に変換	$O(N)$
clear	全ての要素を削除	$O(1)$
lower	指定値未満で最大の要素を取得（なければnull）	$O(logN)$
floor	指定値以下で最大の要素を取得（なければnull）	$O(logN)$
ceiling	指定値以上で最小の要素を取得（なければnull）	$O(logN)$
higher	指定値超で最小の要素を取得（なければnull）	$O(logN)$
headSet	指定値未満の全要素を含んだSetを取得	$O(logN+K)$
subSet	第1引数以上第2引数未満の全要素を含んだSetを取得	$O(logN+K)$
tailSet	指定値以上の全要素を含んだSetを取得	$O(logN+K)$
pollFirst	最小の要素を削除して取得（Setが空だと例外発生）	$O(logN)$
pollLast	最大の要素を削除して取得（Setが空だと例外発生）	$O(logN)$
first	最小の要素を削除せず取得（Setが空だと例外発生）	$O(logN)$
last	最大の要素を削除せず取得（Setが空だと例外発生）	$O(logN)$

lower／floor／ceiling／higherは、Listを二分探索するよりも境界値を間違えにくく、非常に使いやすいと思う。
pollFirst／pollLast／first／lastも使用頻度は高め。

headSet／subSet／tailSetは指定の境界値を含むかどうかを指定できる。上記表内の説明は、含むかどうかの指定を省略した場合の動き。
headSet／subSet／tailSetの結果に対して行った操作は元のSetにも反映されるため、clearを併用することで、指定範囲の要素を削除する処理をすることができる。
なお、指定範囲の要素数を得るためにheadSet／subSet／tailSetとsizeを併用したくなることがあるが、その処理は $O(logN)$ ではなくおそらく $O(logN+K)$ なので注意（これで何度かTLEになった経験あり）。最悪計算量という意味では、 $K=N$ の場合なので、 $O(N)$ と言うべきかもしれないが。

TreeSet<Integer> set = new TreeSet<>();
set.add(2); // [2]
set.add(5); // [2, 5]
set.add(8); // [2, 5, 8]
set.add(1); // [1, 2, 5, 8]
set.add(6); // [1, 2, 5, 6, 8]
set.add(4); // [1, 2, 4, 5, 6, 8]

set.lower(5); // 4
set.floor(5); // 5
set.ceiling(5); // 5
set.higher(5); // 6

set.headSet(5); // [1, 2, 4]
set.subSet(4, 6); // [4, 5]
set.tailSet(5); // [5, 6, 8]

set.pollFirst(); // 1
set.pollLast(); // 8
set.first(); // 2
set.last(); // 6

Map

HashMap　★★

Mapインターフェースの最も基本的な実装クラス。＜キー、値＞の組（エントリ）を要素として持つ。
キー部分については、HashSetと同様に順序性がなく重複もない（重複があったらキーと呼べない）。
異なるキーに対して同じ値を持つことはある。

Setは重複しないキーだけの集合であったが、MapはSetの機能に加え、各キーに対応する付帯情報を何か1つ持てると思えばよい。
付帯情報を2つ以上持ちたい場合は、値を適当なオブジェクトにしたり、ListやSetにしたりする。

例えば＜値 $X$ 、 $X$ に該当する件数＞のようなデータの持ち方が考えられる。
これは $0 \leq X \leq 10^5$ のような連続した範囲であれば配列を使ってもよいが、0件の $X$ についてはエントリがない方が都合が良かったり、 $X$ の範囲がもっと広かったり（ただしエントリの数は $10^5$ 程度に収まる）、 $X$ が数値ではなく文字列であったりした場合はHashMapが適している。
より具体的な例として、素因数分解をした結果を＜底、指数＞の形で持つことができる。

以下の $N$ は自身のMapのエントリ数。

メソッド名	内容	時間計算量
get	指定キーに対応する値を取得	$O(1)$
size	エントリ数を取得	$O(1)$
isEmpty	size() == 0	$O(1)$
put	エントリを追加（キーが既存の場合上書き）	$O(1)$
remove	指定キーのエントリを削除	$O(1)$
containsKey	指定キーのエントリが含まれているか	$O(1)$
getOrDefault	containsKeyがtrueならget、falseなら指定値	$O(1)$
compute	指定キーのエントリについて、キーと値を元に指定処理を行った結果を新しい値として設定	$O(1)$
merge	指定キーのエントリについて、元の値と指定値を元に指定処理を行った結果を新しい値として設定	$O(1)$
keySet	キーのSetを取得	$O(1)$
values	値のCollectionを取得	$O(1)$
entrySet	エントリのSetを取得	$O(1)$
clear	全てのエントリを削除	$O(N)$

compute／mergeはJava8から導入されたメソッド。元々getやputを使ってやりたいことはできるはずで、慣れれば従来より短く書けるかもという程度のもの。
存在しないキーを指定した場合は指定キーのエントリが追加され、指定処理の結果がnullの場合はエントリが削除される。
時間計算量は $O(1)$ としているが、指定処理の計算量は別。
mergeは指定キーが存在しなければ指定処理が呼ばれないため、場合分けを減らせるメリットがあると思われる。

computeは指定キーが存在しなければ指定処理の第2引数がnullになるため、使い勝手が悪い気がする。
computeIfPresent／computeIfAbsent（指定キーが存在する／しない場合のみ指定処理実行）というメソッドもあるが、containsKeyなどで場合分けするのとどちらが楽なのか・・・。
以下の2通りの実装はほぼ同じ処理。パターン2は、computeIfPresentとcomputeIfAbsentの順序を逆にすると、キーなし時に1ではなく2になるのが紛らわしい。
パターン1でifとelse片方の中身しか処理がないような場合に向いているのだと思う。

// パターン1
if (map.containsKey(key)) {
    map.put(key, map.get(key) + 1);
} else {
    map.put(key, 1);
}

// パターン2
map.computeIfPresent(key, (k, v) -> v + 1);
map.computeIfAbsent(key, k -> 1);

keySet／values／entrySetは、全エントリに対して処理を行う際のアクセス手段として使うことになる。
時間計算量はキー／値／エントリの集合を取得するだけなら $O(1)$ だが、件数分ループして処理を行えばもちろん $O(N)$ となる。

Map<Integer, Integer> map = new HashMap<>();
map.put(1, 2); // {1=2}
map.put(3, 4); // {1=2, 3=4}
map.put(5, 2); // {1=2, 3=4, 5=2}
map.put(7, 8); // {1=2, 3=4, 5=2, 7=8}

map.get(1); // 2
map.get(2); // null
map.size(); // 4
map.isEmpty(); // false

map.remove(3); // {1=2, 5=2, 7=8}
map.containsKey(2); // false
map.getOrDefault(1, 0); // 2
map.getOrDefault(2, 0); // 0

// キー(7)と値(8)に対して指定処理(値+1)
map.compute(7, (k, v) -> v + 1); // {1=2, 5=2, 7=9}
// キー(8)が存在しない場合（※vがnullで指定処理が呼ばれることに注意）
map.compute(8, (k, v) -> k); // {1=2, 5=2, 7=9, 8=8}
// 指定処理の戻り値がnullの場合
map.compute(8, (k, v) -> null); // {1=2, 5=2, 7=9}

// キー(7)に対応する元の値(9)と指定値(10)に対して指定処理(足し算)
map.merge(7, 10, (org, prm) -> org + prm); // {1=2, 5=2, 7=19}
// キー(9)が存在しない場合
map.merge(9, 10, (org, prm) -> org + prm); // {1=2, 5=2, 7=19, 9=10}
// 指定処理の戻り値がnullの場合
map.merge(9, 10, (org, prm) -> null); // {1=2, 5=2, 7=19}

for (Integer key : map.keySet()) {
    // key = 1, 5, 7 （※順序は不定）の3回ループ
}
for (Integer val : map.values()) {
    // val = 2, 2, 19（※順序は不定） の3回ループ
}
for (Entry<Integer, Integer> entry : map.entrySet()) {
    Integer key = entry.getKey();
    Integer val = entry.getValue();
}
map.clear(); // {}

TreeMap　★★

HashMapのキーに自動ソート機能を持たせたもの。あるいはTreeSetに付帯情報を持てるようにしたものと見るか。

Setの方と同様に、HashMapのキーはequalsメソッドとhashCodeメソッドが必要で、TreeMapの場合はキーがComparableを実装しているか、生成時にComparatorが必要。

主なメソッドは、HashMapと同じ（計算量だけ悪い）か、TreeSetと少々メソッド名や戻り値の型が異なるだけのものがほとんど。

以下の $N$ は自身のMapのエントリ数。 $K$ は条件に合致するエントリ数。

メソッド名	内容	時間計算量
get	HashMapと同様	$O(logN)$
size	HashMapと同様	$O(1)$
isEmpty	HashMapと同様	$O(1)$
put	HashMapと同様	$O(logN)$
remove	HashMapと同様	$O(logN)$
containsKey	HashMapと同様	$O(logN)$
getOrDefault	HashMapと同様	$O(logN)$
compute	HashMapと同様	$O(logN)$
merge	HashMapと同様	$O(logN)$
keySet	キーのSetを取得（昇順）	$O(1)$
descendingKeySet	キーのSetを取得（降順）	$O(1)$
values	値のCollectionを取得（対応するキーの昇順）	$O(1)$
entrySet	エントリのSetを取得（対応するキーの昇順）	$O(1)$
clear	HashMapと同様	$O(1)$
lowerKey	指定値未満で最大のキーを取得（なければnull）	$O(logN)$
floorKey	指定値以下で最大のキーを取得（なければnull）	$O(logN)$
ceilingKey	指定値以上で最小のキーを取得（なければnull）	$O(logN)$
higherKey	指定値超で最小のキーを取得（なければnull）	$O(logN)$
headMap	キーが指定値未満の全エントリを含んだMapを取得	$O(logN+K)$
subMap	キーが第1引数以上第2引数未満の全エントリを含んだMapを取得	$O(logN+K)$
tailMap	キーが指定値以上の全エントリを含んだMapを取得	$O(logN+K)$
pollFirstEntry	最小のエントリを削除して取得（Mapが空だと例外発生）	$O(logN)$
pollLastEntry	最大のエントリを削除して取得（Mapが空だと例外発生）	$O(logN)$
firstKey	最小のキーを取得（Mapが空だと例外発生）	$O(logN)$
lastKey	最大のキーを取得（Mapが空だと例外発生）	$O(logN)$

clearの実装を見ると、HashMapでは全件nullを設定しているが、TreeMapでは根にnullを設定しているだけであり、これだけはHashMapよりTreeMapの方が早い。

lowerKey～lastKeyは、TreeSetのlower～lastと同じイメージで使えると思う。
lowerEntryなど、キーではなくエントリを取得するメソッドも各種存在する。
pollFirstKey／pollLastKeyは存在しない。（マップからキーだけ削除するという概念はない）

具体的な使用例は、HashMapやTreeSetとほぼ同様なので省略。
　

Queue

ArrayDeque　★★

Queue、Dequeインターフェースの実装クラス。（DequeはQueueのサブインターフェース）
Queueでは、追加した要素を追加した順に取り出せるようなメソッドのみが提供され、Dequeでは先頭と末尾どちらにも追加や削除ができるメソッドが追加で提供されている。
LinkedListも上記インターフェースを実装しているクラスだが、基本的にArrayDequeの方が性能が良いらしい？

Queueとしての主な使いどころは幅優先探索（BFS）。
Dequeとして使えば、追加するのを末尾ではなく先頭に変えるだけで深さ優先探索（DFS）にもなる。

以下はQueue、Deque共通のメソッド。
$N$ は自身のQueueの要素数。 $M$ は引数のCollectionの要素数。

メソッド名	内容	時間計算量
size	要素数を取得	$O(1)$
isEmpty	size() == 0	$O(1)$
add	要素を末尾に追加	$O(1)$
addAll	全要素を末尾に追加	$O(M)$
peek	先頭の要素を削除せず取得（Queueが空の場合null）	$O(1)$
poll	先頭の要素を削除して取得（Queueが空の場合null）	$O(1)$
contains	指定要素が含まれているか	$O(N)$
toArray	配列に変換	$O(N)$
clear	全ての要素を削除	$O(N)$

Queue<Integer> que = new ArrayDeque<>();
que.add(1); // [1]
que.add(4); // [1, 4]
List<Integer> list = Arrays.asList(5, 3, 7);
que.addAll(list); // [1, 4, 5, 3, 7]

que.size(); // 5
que.isEmpty(); // false

que.peek(); // 1   [1, 4, 5, 3, 7]
que.poll(); // 1   [4, 5, 3, 7]
que.peek(); // 4   [4, 5, 3, 7]

以下はDequeインターフェースのみのメソッド。

メソッド名	内容	時間計算量
addFirst	要素を先頭に追加	$O(1)$
addLast	要素を末尾に追加	$O(1)$
peekFirst	先頭の要素を削除せず取得（Dequeが空の場合null）	$O(1)$
peekLast	末尾の要素を削除せず取得（Dequeが空の場合null）	$O(1)$
pollFirst	先頭の要素を削除して取得（Dequeが空の場合null）	$O(1)$
pollLast	末尾の要素を削除して取得（Dequeが空の場合null）	$O(1)$
push	addFirstと同じ	$O(1)$
pop	pollFirstとほぼ同じだが、Dequeが空だと例外発生	$O(1)$

Deque<Integer> que = new ArrayDeque<>();
que.add(1); // [1]
que.addFirst(2); // [2, 1]
que.addLast(3); // [2, 1, 3]
que.push(4); // [4, 2, 1, 3]
List<Integer> list = Arrays.asList(5, 6, 7);
que.addAll(list); // [4, 2, 1, 3, 5, 6, 7]

que.peek();      // 4   [4, 2, 1, 3, 5, 6, 7]
que.peekFirst(); // 4   [4, 2, 1, 3, 5, 6, 7]
que.peekLast();  // 7   [4, 2, 1, 3, 5, 6, 7]

que.poll();      // 4   [2, 1, 3, 5, 6, 7]
que.pollFirst(); // 2   [1, 3, 5, 6, 7]
que.pollLast();  // 7   [1, 3, 5, 6]
que.pop();       // 1   [3, 5, 6]

ほとんど同じだが、要素がないなど例外的な場合だけ動きが異なるメソッド群がある。
offer／peek／poll・・・それぞれfalse／null／nullを返す
add(push)／element／remove(pop)・・・例外発生
個人的には、要素の追加はofferよりaddの方がタイピングが楽なのでadd（addで例外が発生することはまずない）、要素の取得は例外キャッチよりnull判定の方が楽な上、タイピングも楽なのでpeekやpollを使用するようにしている。
　

PriorityQueue　★★

追加した順ではなく、自然順序付けの昇順や、指定したComparatorでソートされた順に取り出すQueue。
Queueインターフェース以外のメソッドは特になし。
主な使いどころはダイクストラ法。

$N$ は自身のQueueの要素数。 $M$ は引数のCollectionの要素数。

メソッド名	内容	時間計算量
size	要素数を取得	$O(1)$
isEmpty	size() == 0	$O(1)$
add	要素を追加	$O(logN)$
addAll	全要素を追加	$O(Mlog(N+M))$
peek	先頭の要素を削除せず取得（Queueが空の場合null）	$O(logN)$
poll	先頭の要素を削除して取得（Queueが空の場合null）	$O(logN)$
contains	指定要素が含まれているか	$O(N)$
toArray	配列に変換	$O(N)$
clear	全ての要素を削除	$O(N)$

Queue<Integer> que = new PriorityQueue<>(Collections.reverseOrder()); // 降順
que.add(1); // [1]
que.add(4); // [4, 1]
List<Integer> list = Arrays.asList(5, 3, 7);
que.addAll(list); // [7, 5, 4, 3, 1]

que.peek(); // 7   [7, 5, 4, 3, 1]
que.poll(); // 7   [5, 4, 3, 1]
que.poll(); // 5   [4, 3, 1]

コレクションまとめ

以下のものは全部使用頻度★２としていたが、実際どれを極端に多く使ったり使わなかったりとかはあまりない気がする。
主に重複可否や順序性の特性により、用途に応じて使い分けられるようにする必要がある。

クラス	重複	順序性	取得・追加	削除	存在確認
ArrayList	可	追加順・index	$O(1)$	$O(N)$	$O(N)$
HashSet	不可	なし	$O(1)$	$O(1)$	$O(1)$
TreeSet	不可	値順自動ソート	$O(logN)$	$O(logN)$	$O(logN)$
HashMap	不可	なし	$O(1)$	$O(1)$	$O(1)$
TreeMap	不可	値順自動ソート	$O(logN)$	$O(logN)$	$O(logN)$
ArrayDeque	可	追加順	$O(1)$	$O(N)$	$O(N)$
PriorityQueue	可	値順自動ソート	$O(logN)$	$O(N)$	$O(N)$

入力

Scanner ★★★

入力例と実装例

BufferedReader ★★★

先ほどと同じ入力例に対する実装例

出力

System.out ★★★

PrintWriter ★★

文字列

String ★★★

StringBuilder ★★

数値、数学

Math ★★★

BigInteger ★

BigDecimal ★

日付、時刻

LocalDate ★

現在時刻取得 ★

配列、コレクション ユーティリティ

Arrays ★★★