技術メモ

神奈川在住のITエンジニアの備忘録。おもにプログラミングやネットワーク技術について、学んだことを自分の中で整理するためにゆるゆると書いています。ちゃんと検証できていない部分もあるのでご参考程度となりますが、誰かのお役に立てれば幸いです。

競技プログラミング

ダイクストラ法

ダイクストラ法で leetCode の問題を解いたので、参考のためにコードをここに残しておく。 Path with Maximum Probability - LeetCodeポイントは、コード中のコメントに記した。 PriorityQueue(heap) を使っているのは、キューの中で最大確率の (確定できる)…

最短経路問題

これまであまり解いてこなかった最短経路問題を解いたので、今後の参考のため、ここに実装したコードを残しておく。問題は以下。 https://leetcode.com/problems/shortest-path-in-binary-matrix/解答コードは以下。競技プロ界ではお馴染みの BFS を使用して…

Sliding Window

leetCode の「713. Subarray Product Less Than K」を Sliding Window アルゴリズムで解いたので、今後の参考のために、解説のコードをここに残しておく。 https://leetcode.com/problems/subarray-product-less-than-k/ public int numSubarrayProductLessT…

bitmask を使って部分集合を列挙する問題を解く

leetCode の「78. Subsets」の「Solution」に、面白い&今後も使えそうな解法があったので、それを元に実装したコードをブログに書いておく。 https://leetcode.com/problems/subsets/この解法は、与えられた集合体の部分集合を列挙する問題を解く問題などに…

深さ優先探索と幅優先探索

深さ優先探索(DFS)と幅優先探索(BFS)について、実装方法をよく忘れてしまうので、ここに簡単な例題を解く際の実装例としてメモしておく。今回は、以下のようなツリーをDFSとBFSで探索することにする。深さ優先探索(DFS)では、以下の順番で探索する。 0 -> 1 …

Java の Map をソートする。

プログラミングの問題を解いていて必要になったので、Javaの Map をソートする方法を以下に纏める。調べてみたところ、いろんな方法があるようだが、自分で試してみてうまくいった方法をここにメモしておく。例えば、以下の map をソートするとする。 Map<Integer, String> ma</integer,>…

Javaで 2つの配列の共通部分を取得する。

競技プログラミングの問題を解いていて必要になったので、Javaで 2つの配列の共通部分を取得するメソッドを作成した。1つ目のメソッドは int 用で、2つ目は String 用。 // 二つの数値の配列のうち、共通する項目を取り出す。 int[] getCommonNumbers (in…

指定した桁数の全ての2進数文字列を生成する。

競技プログラミングの問題を解いていて必要になったので、Javaで、指定した桁数の全ての2進数文字列のリストを生成するメソッドを作成した。 List<String> generateZeroOneCombination (int length) { if (length < 1) { throw new IllegalArgumentException("Input </string>…

Javaの優先度付きキュー

Javaで複数条件でソートする。 - ITエンジニアの技術メモ で扱った題材を優先度付きキュー PriorityQueue を使って実装してみた。以下のような感じになる。 Queue<Work> queue = new PriorityQueue(Comparator. comparing(Work::getReward, Comparator.reverseOrde</work>…

Javaで複数条件でソートする。

Javaでリストを複数の条件でソートしたい時は、Comparator クラスの comparing() と thenComparing() を使うと簡単に実現できる。例えば、以下の Work クラスのオブジェクトが複数入った List があるとする。 class Work { private int timeToFinish; // 仕…

Javaで Stringの配列中の単語の出現回数をカウントする。

競技プログラミングの問題を解く際の時間短縮のため、主題のメソッドを作成した。 // Stringの配列の中で、単語の出現回数をカウントする。 Map<String, Integer> countWordsAppearance(String[] words) { if (words == null || words.length == 0) { throw new IllegalArgume</string,>…

Javaで配列が昇順 or 降順かを調べる

競技プログラミングの問題を解く際の時間短縮のため、Javaで配列が昇順 or 降順かを調べるメソッドを作成した。配列の要素が一個しかない場合、どう判定しようか迷ったが、そもそも要素が一個しかない場合、このメソッドを使うべきではないので、例外を上げ…

Javaで配列の要素が全て同じか調べる

競プロの問題を解いていて必要になったので、今後の時間短縮のため、主題のメソッドを作成した。 // 配列の要素がすべて同じか調べる boolean isAllSame (int[] array) { if (array == null || array.length == 0) { throw new IllegalArgumentException("In…

Javaで文字列を反転する

競プロの問題を解いていると、文字列の反転が必要になることがある。以前は、文字列 (String) を char 型の配列に toCharArray() で変換し、char 型の配列を反転するロジックを自作してそれを使用し、その後に String.valueOf() で String に戻していた。 し…

Javaで配列中の最大値と2番目に大きい値を取得する。

Javaで、配列中の最大値を取得するメソッドと、2番目に大きい値を取得するメソッドを作成した。Javaにはこれらをする標準メソッドがないようなので、競プロの問題を解く時の時間短縮のため自作した。 // 配列の中の最大値を求める int getMax (int[] array) …

Javaでラムダ式を使ってListのソートを行う。

競技プログラミングで良く使う List のソートについて書く。例えば、以下のクラスのインスタンスを保持する List があって、それを age が若い順(昇順)にソートしたいとする。 class Person { String name; int age; Person(String name, int age) { this.na…

Javaで平方数かどうかを判定する。

Javaで平方数かどうかを判定するメソッドを作成した。 // 平方数かどうかを調べる。 boolean isSquareNumber (int number) { if (number < 0) { throw new IllegalArgumentException("Argument must be 0 and over."); } double sqrtOfNumber = Math.sqrt(nu…

Javaで最大公約数、最小公倍数を求める。

Javaで最大公約数、最小公倍数を求めるメソッドを作成した。引数で受け取った2つの引数の最大公約数、最小公倍数をそれぞれ求めて返す。 // 最大公約数を求める。 int calcGcd(int m, int n) { if (m <= 0 || n <= 0) { throw new IllegalArgumentException(…

Javaで配列のソート

Javaで配列をソートするには Arrays.sort() を使用する。ただ、Arrays.sort() では、プリミティブ型の配列に対しては昇順にしかソートできないので、プリミティブ型の配列を降順でソートするには、一度 Arrays.sort() で昇順にしてから逆順にするなどの手間…

Javaで、組み合わせ、順列、階乗を計算する。

競技プログラミングの問題を解く際、組み合わせ(nCr)、順列(nPr)、階乗(n!) の計算を行うことがちょくちょくあるので、今後の時短のため以下のメソッドを作成した。 // nCr を計算する。 // 計算結果は int max を超えやすいので long 型としている。 // lon…

Javaの整数型の最大値

最近、仕事と関連していて頭を使う新たな趣味を始めようと思い、週末などに競技プログラミング (AtCoder) の過去問を黙々と解いている。言語は、速度やライブラリの充実度を考えると C++ が良さそうだったのだが、仕事で一番馴染んでいるのがJavaだったので…