Java
leetCode の「Game of Life」を解いているときに、ちょっとハマったので、メモしておく。 https://leetcode.com/problems/game-of-life/いつも Javaのintの配列を複製する時は、以下のようにしている。 int[] orgArrya1 = {1,2,3}; int[] clonedArrya1 = org…
leetCode の Rotate Image を解いてみた。 https://leetcode.com/problems/rotate-image/この問題は、int型の２次元配列を右に回転させるというもの。例えば、以下のような感じ。 インプット [1,2,3] [4,5,6] [7,8,9] アウトプット [7,4,1] [8,5,2] [9,6,3]…
leetCode の「Product of the Last K Numbers」を解いた。 https://leetcode.com/problems/product-of-the-last-k-numbers/提出したコードは以下。工夫した点は、一度計算した結果(積)をキャッシュ (productCache) に追加して、getProduct の際にキャッシュ…
leetCode の「Generate Parentheses」を解いてみた。 https://leetcode.com/problems/generate-parentheses/この問題は、与えられた数 n に対応する、"(" と ")" の妥当な組み合わせを全て作成するというもの。 例えば、n = 3 の時は以下になる。 [ "((()))"…
leetCode の「Product of Array Except Self」を解いてみた。 https://leetcode.com/problems/product-of-array-except-self/この問題は、例えば以下のように、Inputの配列に対して、i 番目の数を除いたすべての積を Output の配列にする、というもの。 Inpu…
leetCode の「Apply Discount Every n Orders」を解いてみた。 https://leetcode.com/problems/apply-discount-every-n-orders/この問題は、商品の価格や割引の情報を受け取り、それに基づいて料金の計算をするというもの。なお、n 番目および n で割れる数…
leetCode の「Kth Smallest Element in a BST」を解いた。 https://leetcode.com/problems/kth-smallest-element-in-a-bst/この問題は、引数で与えられたバイナリーツリーの中で k 番目に小さい数を戻り値として返すメソッドを作成するというもの。提出した…
leetCodeの「Subsets」を解いてみた。 https://leetcode.com/problems/subsets/この問題は、引数で与えられたintの配列について、全ての部分集合を返すというもの。 再帰を使って書くと簡単そうに思えたので、再帰を使って書いてみた。numsを前から辿りなが…
先日、Listのリストから取得した異なるIntegerオブジェクト同士 (中身のint値は同じ) を「==」で比較するという定番の間違いをしてしまったのだが、なぜか「等しい」と判定された。Javaでは、異なるオブジェクト同士を「==」で比較したら、「等しくない」と…
深さ優先探索(DFS)と幅優先探索(BFS)について、実装方法をよく忘れてしまうので、ここに簡単な例題を解く際の実装例としてメモしておく。今回は、以下のようなツリーをDFSとBFSで探索することにする。深さ優先探索(DFS)では、以下の順番で探索する。 0 -> 1 …
Java で wait() を呼ぶ時は、該当スレッドで synchronized していることが必要となる。これをしておかないと、wait() を読んだ時に、IllegalMonitorStateException が発生する。なので、これまでは無条件に synchronized してから wait() していた。 しかし…
整数の入ったリストを加算する場合、普段、以下のようなコードを書いている。 // リストから一個一個取り出して、加算して戻す。 List<Integer> numlist = new ArrayList<>(Arrays.asList(1, 2, 3)); for (int i = 0; i < numlist.size(); i++) { int num = numlist.g</integer>…
Java で、List を走査しながら要素を削除すると、ConcurrentModificationException が発生することがある。例えば、以下のようなケース。 List<Integer> nums = new ArrayList<>(); nums.add(1); nums.add(2); nums.add(3); nums.add(-1); nums.add(4); nums.add(-2);</integer>…
プログラミングの問題を解いていて必要になったので、Javaの Map をソートする方法を以下に纏める。調べてみたところ、いろんな方法があるようだが、自分で試してみてうまくいった方法をここにメモしておく。例えば、以下の map をソートするとする。 Map<Integer, String> ma</integer,>…
競技プログラミングの問題を解いていて必要になったので、Javaで ２つの配列の共通部分を取得するメソッドを作成した。１つ目のメソッドは int 用で、２つ目は String 用。 // 二つの数値の配列のうち、共通する項目を取り出す。 int[] getCommonNumbers (in…
Java で、int型の配列に特定の値が入っているかどうか確認するために、以下のようなコードを書いたら、意図通りに動かなかった。 int[] intArray = new int[]{0, 1, 2}; if (Arrays.asList(intArray).contains(1)) { System.out.print("Found from intArray"…
競技プログラミングの問題を解いていて必要になったので、Javaで、指定した桁数の全ての2進数文字列のリストを生成するメソッドを作成した。 List<String> generateZeroOneCombination (int length) { if (length < 1) { throw new IllegalArgumentException("Input </string>…
Javaで複数条件でソートする。 - ITエンジニアの技術メモ で扱った題材を優先度付きキュー PriorityQueue を使って実装してみた。以下のような感じになる。 Queue<Work> queue = new PriorityQueue(Comparator. comparing(Work::getReward, Comparator.reverseOrde</work>…
Javaでリストを複数の条件でソートしたい時は、Comparator クラスの comparing() と thenComparing() を使うと簡単に実現できる。例えば、以下の Work クラスのオブジェクトが複数入った List があるとする。 class Work { private int timeToFinish; // 仕…
競技プログラミングの問題を解く際の時間短縮のため、主題のメソッドを作成した。 // Stringの配列の中で、単語の出現回数をカウントする。 Map<String, Integer> countWordsAppearance(String[] words) { if (words == null || words.length == 0) { throw new IllegalArgume</string,>…
競技プログラミングの問題を解く際の時間短縮のため、Javaで配列が昇順 or 降順かを調べるメソッドを作成した。配列の要素が一個しかない場合、どう判定しようか迷ったが、そもそも要素が一個しかない場合、このメソッドを使うべきではないので、例外を上げ…
JavaプログラムのCPU使用率が高騰するパターンの一つについて簡単に纏める。 一時的に負荷が上がり、Javaプログラムのメモリ使用量が増大する。 メモリリソースが逼迫し、Javaが不要なメモリを解放するため、GCが頻繁に走るようになる。 GCがCPUリソースを消…
競プロの問題を解いていて必要になったので、今後の時間短縮のため、主題のメソッドを作成した。 // 配列の要素がすべて同じか調べる boolean isAllSame (int[] array) { if (array == null || array.length == 0) { throw new IllegalArgumentException("In…
競プロの問題を解いていると、文字列の反転が必要になることがある。以前は、文字列 (String) を char 型の配列に toCharArray() で変換し、char 型の配列を反転するロジックを自作してそれを使用し、その後に String.valueOf() で String に戻していた。 し…
Javaで、配列中の最大値を取得するメソッドと、2番目に大きい値を取得するメソッドを作成した。Javaにはこれらをする標準メソッドがないようなので、競プロの問題を解く時の時間短縮のため自作した。 // 配列の中の最大値を求める int getMax (int[] array) …
競技プログラミングで良く使う List のソートについて書く。例えば、以下のクラスのインスタンスを保持する List があって、それを age が若い順(昇順)にソートしたいとする。 class Person { String name; int age; Person(String name, int age) { this.na…
Javaで平方数かどうかを判定するメソッドを作成した。 // 平方数かどうかを調べる。 boolean isSquareNumber (int number) { if (number < 0) { throw new IllegalArgumentException("Argument must be 0 and over."); } double sqrtOfNumber = Math.sqrt(nu…
Javaで最大公約数、最小公倍数を求めるメソッドを作成した。引数で受け取った2つの引数の最大公約数、最小公倍数をそれぞれ求めて返す。 // 最大公約数を求める。 int calcGcd(int m, int n) { if (m <= 0 || n <= 0) { throw new IllegalArgumentException(…
Javaで配列をソートするには Arrays.sort() を使用する。ただ、Arrays.sort() では、プリミティブ型の配列に対しては昇順にしかソートできないので、プリミティブ型の配列を降順でソートするには、一度 Arrays.sort() で昇順にしてから逆順にするなどの手間…
競技プログラミングの問題を解く際、組み合わせ(nCr)、順列(nPr)、階乗(n!) の計算を行うことがちょくちょくあるので、今後の時短のため以下のメソッドを作成した。 // nCr を計算する。 // 計算結果は int max を超えやすいので long 型としている。 // lon…
