Binary Search Tree Iterator in LeetCode

問題

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

Binary Search Tree Iterator - LeetCode

ソースコード

House robber ⅲ in LeetCode

問題

2分木が与えられる。ノードは数値を持っていて以下の条件で数値の和が最大の値を見つける問題。

条件

  • 直接つながれている隣同士のノードは取る事ができない。

House Robber III - LeetCode

解き方

それぞれのノードについて、そのノードの値を和に含めるか否かの2パターンを試し、最大値となる和を取得する。その際、同じ条件での探索が複数存在するのでメモ化することで計算量を抑えることができる。

ソースコード

My Simple and Clear Java Solution With Using Memoization | LeetCode Discuss

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を用いることで解くことができる。問題はノードを削除する時だが、ArrayListからIndexを指定して要素を削除する場合、削除した分だけ要素をシフトさせる必要があるため、O(1)を実現できない。そこで以下の方法を取る。

  1. 削除したい要素のIndexを取得
  2. ArrayList内で最後の要素とIndexの要素をSwap
  3. ArrayListの最後の要素を削除(シフトさせる必要が無くなる)

ソースコード

Add One Row to Tree

問題

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

leetcode.com

ソースコード

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

結果

僕の環境では以下の値となった。言語はJava

  • 空間計算量O(N)とすると実際の使用容量はN byte程度
  • 時間計算量O(10x) とすると、10-1*(9-x) 秒程度

※オーダーの値が小さいと誤差は出る

Javaのメモリーサイズ

Javaのメモリーサイズはメソッドによって取得することができる。

Runtime (Java Platform SE 6)

maxMemoryとは、使用メモリーがtotalMemoryに近づいた時に、更にメモリーの使用を試みる値となる。

maxMemoryは大体2GBであることが分る。

空間計算量

Int型の整数1つのバイト数は1バイトとなる。つまりO(106)だと106バイトとなり、1MBとなる。 109個の場合は、1GBとなり、out of memory errorが発生する。

107の場合、10MBとなる。

実際に図ってみても使用メモリーは40MBと妥当な値を出している。

まとめると、空間計算量O(N)とすると実際の使用容量はN byte程になった。

時間計算量

処理時間はSystem.nanoTime()によってナノセカンドを得る事ができる。

O(107)だと13msで10^-2秒程となる。

  • O(109) : 1703ms → 2秒弱
  • O(108) : 127ms → 0.1秒 (10^-1秒)
  • O(107) : 13ms → 0.01秒 (10^-2秒)
  • O(106) : 6ms → (10^-3秒)

まとめると 時間計算量O(10x) の場合、10-1*(9-x) 秒かかる。