Matsushita's Blog

筋肉をつけるために

最近 細マッチョになりたくて筋トレをはじめました。 近所の市民ジム的な所でいそいそとやっています。 プロテインも買いました。ついでにシェーカーも。 牛乳で割ると案外美味しい。 スポーツドリンクの役割は水分補給だけじゃない 最近はじめて知ったので…

Binary Search Tree Iterator in LeetCode

問題 Binary Search Treeにおけるイテレータを実装する問題。next()メソッドで取得できる値は現時点での最小値となる。 Binary Search Tree Iterator - LeetCode ソースコード

House robber ⅲ in LeetCode

問題 2分木が与えられる。ノードは数値を持っていて以下の条件で数値の和が最大の値を見つける問題。 条件 直接つながれている隣同士のノードは取る事ができない。 House Robber III - LeetCode 解き方 それぞれのノードについて、そのノードの値を和に含め…

Serialize and Deserialize BST in LeetCode

問題 2分木に対するSerializeとDeserializeを実装するクラスを作る問題 leetcode.com ソースコード My simple and clear Java solution | LeetCode Discuss

Insert Delete GetRandom O(1) - Duplicates allowed

問題 通常のHashTableの機能に加え、テーブル内の要素をランダムで返すメソッドを実装されているデータ構造を作る。データ構造内の要素は重複が許されており、重複した要素の数はランダムな要素を返す関数に影響する。 leetcode.com ソースコード

Insert Delete GetRandom O(1)

問題 通常のハッシュテーブルの機能に加えて、テーブル内の要素をランダムで取得するメソッドが実装されたデータ構造をデザインする問題。 全ての操作はO(1)で行う必要がある。 leetcode.com 解法 HashMapとArrayListを用いることで解くことができる。問題は…

Add One Row to Tree

問題 2分木が与えられ、与えられた深さに1行分ノードを追加するという問題 leetcode.com ソースコード

オーダー計算量と実際の処理時間と使用容量を比較する

結果 僕の環境では以下の値となった。言語はJava。 空間計算量O(N)とすると実際の使用容量はN byte程度 時間計算量O(10x) とすると、10-1*(9-x) 秒程度 ※オーダーの値が小さいと誤差は出る Javaのメモリーサイズ Javaのメモリーサイズはメソッドによって取得…

Design TinyURL in LeetCode

Problem TinyUrl is a URL that a original URL is compressed. This problem is how should we design TinyURL services. https://leetcode.com/problems/design-tinyurl/#/solutionsDesign TinyURL - LeetCode How to code First, I prepare two HashMap t…

2分探索木からノードを削除する Delete Node in a BST in LeetCode

問題 2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。 leetcode.com 解法 以下のステップで解く 2分探索でkeyを見つける 削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。 右側のサブツリーから…

Perfect SquareかをO(logN)で判定する LeetCode

問題 leetcode.com 解法 単純にfor文を用いた解法だとO(√N)となり間に合わない。 2文探索を用いることでO(logN)で解くことができる。 ソースコード

【グラフ理論とネットワーク理論】Extended Complete Graph

Connectivity and Damage Index Connectivity Connectivity express the reliability of the graph Node Connectivity Cv(G) : Minimum number of nodes to be removed to make a graph unconnected. Branch Connectivity Ce(G) : Minimum number of branche…

サイズNの配列からM個の要素をランダムに取り出す

問題 サイズNの配列からM個の要素を取り出し新たな配列を返すメソッドを実装する。各要素が選ばれる確率は全て等確率になるようにする。 解き方 はじめに元々の配列の先頭からM個取り出して配列を作る。後は、インデックスがm以上の要素と以下の要素を交換す…

Least Recently Used (LRU) cache を実装する

問題 LRUキャッシュとはキーとバリューをマッピングするデータ構造で、キャパティを超えたら最後に使われたキャッシュが削除されるという挙動をする。 leetcode.com 解法 HashMapと双方向連結リストを利用することで実装することができる。 リストを用いるこ…

合計の入れ替え Cracking The Coding Interview

問題 2つの整数配列が与えられる。それぞれの配列から1つずつ要素を決め、それらを交換した時に2つの配列の要素の合計値が一致するようなペアを見つける問題。 入力: {4, 1, 2, 1, 1, 2} と {3, 6, 3, 3} 出力: {1, 3} 解法 全列挙の解法 O(A*B) i, jを添…

古い携帯電話 ガラケーのキーボード

問題 ガラケーのキーボードにおいて、入力値としてキーボード上の押した数字が与えられる(連打回数は無視)。 この時に、押した数字によって得られる単語の組合せの内、辞書に乗っているものを出力する問題。辞書は予め与えられ、データ構造は自由に設定でき…

【グラフ理論とネットワーク理論】線形構成法

線形構成法 Linear Design Method 直径最小化問題 Minimizing Diameter Problem (n, d) グラフとは、接点数n, 各接点は出枝、入枝をそれぞれd本ずつもっているグラフのこと。このグラフの事をd正則有向グフラと呼ぶ。 また、経路の長さは、経路中の枝の数で…

湖の大きさを列挙する

問題 { {0, 2, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}, {0, 1, 0, 1} } が与えられる。0の部分が湖で、縦横斜めで0が連なっている所は同じ湖とする。全ての湖のサイズを列挙する問題。 ソースコード

'a'と'b'でパターンマッチ

問題 文字列wordとパターンを表すpatternが入力値として与えれる。patternは'a'と'b'のみで構成されている。wordがpatternにマッチするか否かを求める問題。 例 word = “catcatgocatgo”, pattern = “abbab” a -> cat b -> go とすればwordはpatternにマッチ…

平面上のN個の点を最も多く通る線を見つける

問題 xy平面上にN個の点が与えられる。最も多くの点を通るように直線を引いた時の点の最大値を求める問題 leetcode.com 解法 HashMapを用いることでO(N2)で解くことができる。forループを2回使い2つの点を全列挙する。2つの点のを結ぶ傾きをキーとして、H…

階乗のゼロ Cracking the Coding the Interview

問題 整数Nが与えら、Nの階乗を計算した時に、末尾に連なる0の数を求める問題。 解き方 どんな時に末尾に0が来るか考える。階乗の計算では足し算はなく掛け算のみなので、10を掛けた時に末尾に0がつく。また、10は2×5なので2と5を掛けた回数分、0が着…

JavaのCollectionsクラスのshuffleメソッドの実装を覗く

はじめに リストをランダムに入れ替える方法を考える時にどのようにするのが実装するのがベストなのか疑問に思い、JavaのCollectionsに定義されているshuffleメソッドの実装を見てみる。 Collections.shuffle 上記のコードで実際にランダム化している箇所は…

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

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

キューを使って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