Treeにおけるイテレータを実装する問題。next()メソッドで取得できる値は現時点での最小値となる。ノードは数値を持っていて以下の条件で数値の和が最大の値を見つける問題。つながれている隣同士のノードは取る事ができない。通常のHashTableの機能に加え、テーブル内の要素をランダムで返すメソッドを実装されているデータ構造を作る。データ構造内の要素は重複が許されており、重複した要素の数はランダムな要素を返す関数に影響する。通常のハッシュテーブルの機能に加えて、テーブル内の要素をランダムで取得するメソッドが実装されたデータ構造をデザインする問題。全ての操作はO(1)で行う必要がある。HashMapとArrayListを用いることで解くことができる。2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。単純にfor文を用いた解法だとO(√N)となり間に合わない。2文探索を用いることでO(logN)で解くことができる。LRUキャッシュとはキーとバリューをマッピングするデータ構造で、キャパティを超えたら最後に使われたキャッシュが削除されるという挙動をする。HashMapと双方向連結リストを利用することで実装することができる。xy平面上にN個の点が与えられる。HashMapを用いることでO(N2)で解くことができる。forループを2回使い2つの点を全列挙する。Pre-Oderで頑張る。通常の速さと、その2倍の速さでLinkedListを探索していくと、早いほうが末尾に到着する時に遅い方はちょうど中間地点にいる。中間地点まできたら、そこから末尾まで進むと同時にリストを逆順にしていく。rightプロパティを交換すればOK。文字列sが与えられ、以下の条件での最大の部分文字列の長さを出力する。条件は、部分文字列内には同じ文字は被ってはいけない。N√Nの解法だと間に合わない。素数の倍数は全て素数ではないという性質を使って解く。素数を見つけたら、その倍数を予め素数ではない印を付けておく。この解法の計算量はO(NloglogN)らしい。N個の整数を持つ配列が与えられる。隣接する要素は取れないという条件で、各要素の和の最大を求める問題。HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。Int型の配列が与えられて、出現回数が配列の要素数の過半数以上の物を出力する問題。マジョリティな要素は存在すると保証されている。HashMapを用いれば時間計算量O(N)で解けるが、空間計算量はO(N)になってしまう。与えられたInt型の配列numsの要素の内、3つ選んだ要素の和がtargetに最も近い値を見つける問題。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。