leetCode
leetCode の以下の問題を解いた。 https://leetcode.com/problems/string-compression/文字列中の連続する同じ文字をグルーピングするという問題。 こういうのは、これまで、文字列を前から見て行って、同じ文字の連続が途切れたら、その１つ前までを１グル…
golang で map を使って leetCode の典型的な問題を解いたので、今後の参考のために、書いたコードをここに残しておく。 重要そうなところは、ソース中のコメントに記載した。 type MagicDictionary struct { lengthToWords map[int][]string } func Constru…
leetCode の以下の問題を Union-Find 木を使って解いた。 https://leetcode.com/problems/smallest-string-with-swaps/今後の参考のために、自分の書いたコードを載せておく。 import java.util.*; public class SmallestString { public String smallestStr…
leetCode の「452. Minimum Number of Arrows to Burst Balloons」を解いた。 https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/この問題は、苦手な interval 系なので、今後の参考のために、解答をここに残しておく。 public int…
leetCode の「713. Subarray Product Less Than K」を Sliding Window アルゴリズムで解いたので、今後の参考のために、解説のコードをここに残しておく。 https://leetcode.com/problems/subarray-product-less-than-k/ public int numSubarrayProductLessT…
leetCodeの「216. Combination Sum III」を解いた。(苦手な) dfs の良い練習になったので、今後の参考にため、書いたコードをここに残しておく。 https://leetcode.com/problems/combination-sum-iii/ class Solution { private int numCount; private int t…
leetCodeの「497. Random Point in Non-overlapping Rectangles」を解いた。 https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/初めて Map#ceilingKey() を使ったので、今後の参考のため、解答コードをここに残しておく。 import …
leetCode の「824. Goat Latin」を解いた。 https://leetcode.com/problems/goat-latin/leetCode の掲示板に、単語 (String) が文字 (char) を含んでいるのか、簡単に判定する方法があったので、今後の参考のため、その方法を使った実装例をここに残しておく…
leetCode の「1032. Stream of Characters」を解いた。 https://leetcode.com/problems/stream-of-characters/Trie木の実装の良い練習になったので、今後の参考のために自分の解答をここに残しておく。なお、通常の Trie 木と異なり、この問題では、単語を逆…
leetCodeの「1286. Iterator for Combination」を解いた。 https://leetcode.com/problems/iterator-for-combination/Iteratorの作り方など、いろいろ参考になることが多い問題だったので、コメント付きの解答をここに残しておく。 import java.util.ArrayLi…
leetCodeの「435. Non-overlapping Intervals」を解いた。 https://leetcode.com/problems/non-overlapping-intervals/解法を理解するのにちょっと時間がかかったので、ここにコメント付きの解答コードを残しておく。 public int eraseOverlapIntervals(int[…
leetCodeの「260. Single Number III」を解いた。 https://leetcode.com/problems/single-number-iii/この問題に取り組んでいる中で、Javaのコレクションから配列に変換する簡単な方法を見つけたので、それも含めて解答をここに残しておく。 public int[] si…
leetCode の「347. Top K Frequent Elements」の Discuss を読んでいて、Bucket Sort というソート方法による解法が出てきたので、今後の参考のためここにメモしておく。 https://leetcode.com/problems/top-k-frequent-elements/ちなみに、Bucket Sort とい…
leetCode の「67. Add Binary」を解いた。 https://leetcode.com/problems/add-binary/Java の char 型の引き算の結果の型など、気を付ける点があったので、ここに解答を残しておく。 public String addBinary(String a, String b) { StringBuilder sb = new…
leetCodeの「347. Top K Frequent Elements」を解いた。 https://leetcode.com/problems/top-k-frequent-elements/Map#getOrDefault() や PriorityQueue など、今後も使えそうなテクニックが幾つか出てくるので、参考のためここに解答を残しておく。 public …
leetCodeの「190. Reverse Bits」を解いた。bit 演算の良い練習になったので、今後の参考のために、自分の解答をここに残しておく。 https://leetcode.com/problems/reverse-bits/ public int reverseBits(int n) { int ans = 0; int len = 32; for (int i =…
leetCode の「15. 3Sum」を解いた。 https://leetcode.com/problems/3sum/細かいテクニックで、今後使えそうなものが幾つかあるので、ここに解答を残しておく。 import java.util.*; public class Solution { public List<List<Integer>> threeSum(int[] nums) { if (nums.</list<integer>…
leetCode の「210. Course Schedule II」を解いた。 https://leetcode.com/problems/course-schedule-ii/トポロジカルソートの良い練習問題なので、今後の参考のため自分の解答をここに残しておく。 import java.util.ArrayDeque; import java.util.Queue; p…
leetCodeの「1079. Letter Tile Possibilities」を解いた。 https://leetcode.com/problems/letter-tile-possibilities/ 典型的なバックトラッキングの問題で、今後の参考になりそうなので、解法をここに残しておく。 import java.util.HashSet; import java…
leetCodeの「406. Queue Reconstruction by Height」を解いた。 https://leetcode.com/problems/queue-reconstruction-by-height/この問題では、二次元配列のソートや、List から int 配列への変換など、競技プログラミングに使えそうなテクニックが満載だっ…
leetCode の「Populating Next Right Pointers in Each Node」を解いた。 https://leetcode.com/problems/populating-next-right-pointers-in-each-node/この問題を解く際、Binary Tree を BFS (幅優先探索) で探索しながら、階層ごとに処理するということを…
leetCode の「Implement Trie (Prefix Tree)」を解いた。 https://leetcode.com/problems/implement-trie-prefix-tree今後、Trie 木を実装する際のヒントにしたいので、作成したプログラムをここに残しておく。 import java.util.HashMap; import java.util.…
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を前から辿りなが…
leetCodeの「Add and Search Word - Data structure design」を解いてみた。 https://leetcode.com/problems/add-and-search-word-data-structure-design/この問題は、簡易版の辞書を作成するというもの。機能としては、単語の登録と検索がある。検索では「.…
