Javaアルゴリズムクイックリファレンス
リスト
初期化
List<Integer> 数値リスト = new ArrayList<>();
主なメソッド
add(Object 要素);size();get(int インデックス);isEmpty();contains(Object o);remove(int インデックス);
マップ
マップはキーと値のペアを保持するコレクションです。
初期化
Map<String, Integer> マップ = new HashMap<>();
主なメソッド
put(Object キー, Object 値);get(Object キー);size();containsKey(Object キー);remove(Object キー);
スタック
初期化
Stack<Integer> スタック = new Stack<>();
主なメソッド
Object push(Object 要素);Object pop();Object peek();boolean isEmpty();
キュー
初期化
Queue<Integer> キュー = new LinkedList<>();
主なメソッド
boolean add(Object 要素);Object poll();Object peek();boolean isEmpty();
優先度付きキュー
別名: ヒープ。要素を自然順序または指定されたコンパレータに従って自動的に並べ替えるデータ構造です。
初期化
PriorityQueue<Integer> 優先度付きキュー = new PriorityQueue<>();
配列のソート
Arrays.sort(int[] 配列)Arrays.sort(int[] 配列, (o1,o2)->o1-o2) ラムダ式を使用した昇順ソートArrays.sort(int[] 配列, (o1,o2)->o2-o1) ラムダ式を使用した降順ソート
public static void main (String[] args) {
Scanner scan = new Scanner(System.in);
// 一次元配列
Integer []昇順配列 = {14,22,3,4,5};
Arrays.sort(昇順配列, (o1,o2)->o2-o1);
for (int i = 0; i < 昇順配列.length; i++){
System.out.println(昇順配列[i]+"");
}
// 二次元配列
Integer [][]二次元配列 = {{2,3,4},{3,5,6}};
Arrays.sort(二次元配列, (o1,o2)->o2[0]-o1[0]);//最初の要素の値でソート
for (int i = 0; i < 二次元配列.length; i++){
for (int j = 0; j < 二次元配列[i].length; j++){
System.out.print(二次元配列[i][j]+" ");
}
System.out.println();
}
}
コレクションのソート
Collections.sort(List<> リスト)コレクションの要素をデフォルト（小さい順）でソートCollections.sort(List<> リスト,(o1,o2)->o1-o2) 昇順ソートCollections.sort(List<> リスト,(o1,o2)->o2-o1) 降順ソート
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
List<Integer> 数値リスト = new ArrayList<>();
数値リスト.add(1);
数値リスト.add(2);
数値リスト.add(3);
Collections.sort(数値リスト,(o1,o2)->o1-o2) // 昇順
for (int i = 0; i < 数値リスト.size(); i++) {
System.out.println(数値リスト.get(i)+" ");
}
}
文字列
初期化
- 引数なしコンストラクタ
String 文字列 = new String(); - 文字列を引数とするコンストラクタ
String 文字列 = new String("Java")
主なメソッド
char charAt(int インデックス)：指定されたインデックスの文字を返すint compareTo(Object o)：比較結果を返す（大きい場合1、等しい場合0、小さい場合-1）String concat(String 文字列)：指定された文字列をこの文字列の末尾に連結boolean equals(String 文字列)int indexOf(String 文字列)：指定された部分文字列が最初に出現するインデックスを返すint length()String substring(int 開始, int 終了);int compareTo(String 文字列);String[] split(String 文字列);
StringBuilder
初期化
引数なしコンストラクタ：StringBuilder 文字列ビルダー = new StringBuilder();
主なメソッド
void append(Object オブジェクト);int indexOf(String 文字列);StringBuilder reverse();：StringBuilderオブジェクトを逆順にしたものを返すboolean isEmpty();int charAt(int インデックス);insert(int インデックス, char 文字);
累積和
テンプレート
// 元の配列
int[] 元配列 = {1,2,3,4,5};
int[] 累積和配列 = new int[元配列.length+1]; //+1は配列のインデックスを1始まりにするため
for (int i = 0; i < 元配列.length; i++) {
累積和配列[i+1] = 累積和配列[i] + 元配列[i];
}
二分探索
テンプレート
値xの探索
int [] 昇順配列 = {1,2,3,4,5,6}; // ソート済み配列
int 左端 = 0, 右端 = n-1;
int 探索値 = 3;
while (左端 < 右端) {
int 中間 = (左端 + 右端)/2; // 区間が偶数の場合、中間値は左寄り
if (昇順配列[中間]>=探索値) 右端 = 中間;
else 左端 = 中間+1;
}
int [] 昇順配列 = {1,2,3,4,5,6}; // ソート済み配列
int 左端 = 0, 右端 = n-1;
int 探索値 = 3;
while (左端 < 右端) {
int 中間 = (左端 + 右端 + 1)/2; // 区間が偶数の場合、中間値は右寄り
if (昇順配列[中間]>探索値) 右端 = 中間 - 1;
else 左端 = 中間;
}
動的計画法
動的計画法は、問題を小さな部分問題に分割し、それらの解を組み合わせて全体の解を求めるアルゴリズム設計技法です。
最大公約数と最小公倍数
最大公約数(GCD)
public static long 最大公約数(long 数値1, long 数値2) {
return 数値2 == 0 ? 数値1 : 最大公約数(数値2, 数値1%数値2);
}
最小公倍数(LCM)
public static long 最小公倍数(long 数値1, long 数値2) {
return 数値1/最大公約数(数値1, 数値2)*数値2;
}
進数変換
//JavaのAPIを使用して、十進数を任意の進数に変換
String 変換結果 = Integer.toString(十進数, 目標進数);
//十進数は変換する数値、目標進数は変換後の進数
// 自作メソッド - 十進数以内の変換
public static String 進数変換(int 元の数値, int 目標進数) {
StringBuilder 結果 = new StringBuilder();
while (元の数値>0) {
結果.append(元の数値%目標進数);
元の数値/=目標進数;
}
return 結果.reverse().toString();
}