マツシタのお勉強

Hacker Rank

LinkedListから重複した要素を除く Hacker Rank

問題 www.hackerrank.com ソースコード

キューを使って2分木をレベル毎に探索する BST Level-Order Traversal in Hacker Rank

問題 2分木が与えられ、深さ順に探索する問題。 www.hackerrank.com ソースコード

再帰を用いて階乗を計算する Hacker Rank

問題 Programming Problems and Competitions :: HackerRank ソースコード

LinkedListが輪になっているかを判定する Hacker Rank

問題 LinkedListの先頭のノードheadが与えられ、そのリストがサイクルしているかを判定する問題 www.hackerrank.com 解法 異なるスピードで2箇所から探索を開始し、探索途中に2つの探索位置が一致した場合、そのリストは輪となっていることが分る。 ソース…

問題 2つの文字列が与えれる。2つの文字列がアナグラムとなるように文字を消す数を返す問題。 www.hackerrank.com 解法 ハッシュを用いて、それぞれの文字の出現回数を記録する。文字列はローワーケースのみだけなので、HashMapを使わずに配列を使うことで…

Arrays: Left Rotation in Hacker Rank

問題 www.hackerrank.com 解法 剰余を使ってインデックスを上手く操作してあげる。

DP: Coin Change in Hack Rank

問題 N枚の異なるコインと支払いたい金額moneyが与えれる。与えられたコインはそれぞれ無限に使える時、与えられたコインを使って合計金額がmoneyとなるような支払い方法の通り数を求める問題。 www.hackerrank.com 解法 動的計画法と用いることで計算量O(N*…

空間計算量O(1)で配列内のユニークな数字を見つけるBit Manipulation: Lonely Integer

問題 n個の要素(整数)の配列が与えらる。配列内の要素はただ1つを除いて、全て2回ずつ現れる。1回のみ出現するユニークな数字を求める問題。 www.hackerrank.com 解法 この問題は、XORを用いることで空間計算量O(1)で解くことができる。 上記のように配列…

動的計画法を用いて階段の登り方の通り数求める Davis' Staircase in Hacker Rank

問題 始め階段の0段目にいて、N段目までの登り方の方法の数を求める問題。 階段は1段、2段又は3段を一気に登る事ができる。 www.hackerrank.com 解法 全列挙するためには、今いる段から1段登るか2段登るか3段登るかの3通りを毎回行うので、3N通り行…

O(√N)で素数判定をする Time Complexity: Primality in Hacker Rank

問題 整数がNが与えられて、Nが素数か否かを判定するメソッドを実装する問題。 www.hackerrank.com 解法 素数とは、1と自身の数のみが約数となる1より大きい数の事。なので、2 ≦ i < Nのiでループを回し、Nがiで割り切れるかどうかを判定することで素数判…

Shortest Reach in a Graph in Hacker Rank

問題 n個のノードとm個のエッジによって構成されるグラフが与えられ、スタートノードからその他の全てノードまでの最短距離を求める問題。 www.hackerrank.com 解法 優先度付きキューを用いたダイクストラ法を使って解く 計算量 優先度付きキューに値を追加…

Connected Cell in a Grid in Hacker Rank

問題 R行C列の行列が与えれれる。行列の各マスは0か1のどちらかが書かれている。1の島の大きさ(マスの数)が最大を出力する問題。 ここで島の定義は、水平方向、垂直方向、斜め方向で1が隣同士ならばそれらは1つの島とすることができる。 www.hackerrank.com…

Merge Sort: Counting Inversions in HackerRank

問題 Int型の配列が与えられ、ソートするために必要なスワップの数をカウントするという問題 www.hackerrank.com 解き方 O(N2)の解法 この解法はバブルソートの要領で解く。 forループを2重にしてiを0 ≦ i < arr.length, jをi+1 ≦ j < arr.lengthのようにル…

Trie Tree in Java

What is Trie Tree Trie Tree is one of the tree structure to search element. The feature of this tree that each node dose not have element information, but also each edge has element information. Trie tree is used to search String like dict…