Matsushita's Blog

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

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

二分木のルートから葉までのルートを全列挙 Binary Tree Paths in LeetCode

問題 leetcode.com 解法 Pre-Oderで頑張る。 Tree traversal - Wikipedia

LinkedListが回文になっているか否かを判定 Palindrome Linked List in LeetCode

問題 leetcode.com 解法 通常の速さと、その2倍の速さでLinkedListを探索していくと、早いほうが末尾に到着する時に遅い方はちょうど中間地点にいる。 中間地点まできたら、そこから末尾まで進むと同時にリストを逆順にしていく。 ここまでの操作で、リスト…

2分木を左右対象にひっくり返す Invert Binary Tree in LeetCode

問題 leetcode.com それぞれのノードのleft, rightプロパティを交換すればOK。 ソースコード

Google Code Jam 2016 B Rank and File 解法

問題 N×Nの行列を考える。各マスには数字が振られており、どの行もどの列も昇順になっている。 N×Nの行列では行と列の数は合計で2N個だが、この問題では2×N-1個の行か列のリストが与えられる。 取り除かれた行又は列のリストを出力する問題 Dashboard - Roun…

Longest Substring Without Repeating Characters

問題 文字列sが与えられ、以下の条件での最大の部分文字列の長さを出力する。 条件は、部分文字列内には同じ文字は被ってはいけない。 leetcode.com 解法 ハッシュマップを用いて、キーに文字をバリューにその文字が出現した場所(index)を保存することでO(N…

N以下の素数の個数を求める Count Primes in LeetCode

問題 leetcode.com 解法 N√Nの解法だと間に合わない。 素数の倍数は全て素数ではないという性質を使って解く。 素数を見つけたら、その倍数を予め素数ではない印を付けておく。 ソースコード 参考 この解法の計算量はO(NloglogN)らしい。 www.youtube.com

隣接する要素は盗めない泥棒 House Robber in LeetCode 動的計画法

問題 N個の整数を持つ配列が与えられる。隣接する要素は取れないという条件で、各要素の和の最大を求める問題。 例 [1, 2, 3, 4, 5] という配列の場合は以下のようなとり方がある 1 , 3, 5 → 9 1, 4 → 5 1, 5 → 6 2, 4 → 6 2, 5 → 7 max = 9 leetcode.com 解…

2つのLinkedListが交わる点を見つける Intersection of Two Linked Lists in LeetCode

問題 2つのLinkedListが与えられ、2つが交差する点を見つける問題 leetcode.com 解法 HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。 以下の2つの処理を同時に行う リストAを順番に先頭から見ていき、末尾までいったらリストB…

Excel Sheet Column Number

問題 アルファベットの文字列が与えられ、それをエクセルシートに対応した数字を出力する問題 leetcode.com ソースコード アルファベットから数字へ 数字からアルファベットへ

配列の中のマジョリティーを探す Majority Element in LeetCode

問題 Int型の配列が与えられて、出現回数が配列の要素数の過半数以上の物を出力する問題。 必ずマジョリティな要素は存在すると保証されている。 leetcode.com 解き方 HashMapを用いれば時間計算量O(N)で解けるが、空間計算量はO(N)になってしまう。この問題…

Best Time to Buy and Sell Stock in LeetCode

問題 Best Time to Buy and Sell Stock | LeetCode OJ ソースコード

再帰を用いて階乗を計算する 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のようにル…

Google code jam 2017 Problem A. Alphabet Cake 解法

問題 Dashboard - Round 1A 2017 - Google Code Jam R行C列のグリッドが与えられる。各マスには?か異なるアルファベット1文字が書かれている。この時、以下の条件で?のマスを別のアルファベットで埋めるプログラムを書く。 条件 ?には入力値として既に登…

Javaのメモリー構造とガベージコレクションについて

JavaVM Java VMとは… Java仮想マシン (Java virtual machine、Java VM、JVM) は、Javaバイトコードとして定義された命令セットを実行するスタック型の仮想マシン。APIやいくつかのツールとセットでJava実行環境 (JRE) としてリリースされている。この環境を…

Knowledges about Java 【Interview preparation】

Introduction This article is for my preparation of technical interview. And this focuses on programming language “Java”. final keyword The final keyword in Java has different meaning depending on whether it is applied to a variable, class …

【グラフ理論とネットワーク理論】Network and Flow #3

Introduction Here is the article I wrote last time class. keita-matsushita.hatenablog.com Network and Flow Network is defined as below. ・Network : Graph G(V, E) in which branch capacity Ci(> 0) is defined. ・f(vi, vj) : Branch flow value …

AtCoder ABC056 C - Go Home

問題 時刻0に直線上の0地点にカンガルーがいる。時刻i - 1から時刻iにかけてカンガルーは現在地点pとするとp - i, p, p + 1のどれかに移動することができる。カンガルーが位置Xに到達する最短時間を求める問題。 C: Go Home - AtCoder Beginner Contest 056 …

AtCoder ABC057 D - Maximum Average Sets

問題 D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder N(1 <= N <= 50)個の品物が与えられ、それぞれの品物には価値Vi(1 <= i <= N)が設定されている。A個以上、B以下の品物を取ることが出来る時、選択した品物の価値の最大の平均値と、…

AtCoder ABC057 C - Digits in Multiplication

問題 C: Digits in Multiplication - AtCoder Beginner Contest 057 | AtCoder 整数N(1 <= N <= 1010)が与えられ、A * B = Nを満たすA, BについてF(A, B)の値が最小となるものを出力する問題。ここで、F(A, B)とはAとBの桁数を比べ小さい方の桁数を返り値す…