読者です 読者をやめる 読者になる 読者になる

サイズ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を添え字にしてforループを2つネストすることで2つの配列における全ての要素の組合せを得られる。i, jをスワップさせた時に合計値が一致すればそれらを出力する。この解法の計算量は(O(A*B)) (2つの配列のサイズをそれぞれA, Bとする)

O(A + B)の解法

実は、配列Aから交換する要素が決定されれば、配列B内の交換するべき要素の候補は決定する。配列A, Bの総和をsumA, sumBとし、それぞれの配列内の交換するべき要素をa, bと置くと。 sumA - a + b = sumB - b + aが成り立つ。あとはaだけを全列挙すればbが決定されるので、計算して得たbが配列B内に存在するかをチェックしてあげれば良い。この解法の計算量はO(A + B)。

ソースコード

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

問題

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

例: 「2」を押すと'a', ‘b’, ‘c'のどれかとなる。
  「3」を押すと’d’, ‘e’, ‘f'のどれかとなる。

解法

全列挙で頑張る

全列挙を考えると、数字に対応する全ての文字のパターンを列挙し、辞書に存在するかを確認する方法が挙げられる。この解法の計算量はO(N4)となる。Nは入力値の桁数であり、1つの数字に対して対応する文字は最大4つなので、全パターンを列挙するためには約N4通り存在するからだ。この解法はとても遅い。

トライ木を用いた解法

上記の解法を少し工夫する。上記の解法で悪い点は、全てのパターンの文字列を生成している点である。中には始めの2文字を選んだ時点で辞書に乗っている単語か否かをチェックすることができれば、その文字は生成する必要がなく途中で処理を止めることができる。枝刈りができるわけだ。これを得意とするのがトライ木である。

事前準備をしてO(N)で解く

最も早い解法は、辞書の中身の単語を予め、ガラケーのキーボードに対応して数字に変換しておくことだ。辞書の単語とその単語を数字に変換したものをHashMapに保存しておけば、入力値の数字から辞書中に存在する単語はO(1)で取得するこができる。

ソースコード

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

線形構成法 Linear Design Method

直径最小化問題 Minimizing Diameter Problem

(n, d) グラフとは、接点数n, 各接点は出枝、入枝をそれぞれd本ずつもっているグラフのこと。このグラフの事をd正則有向グフラと呼ぶ。 また、経路の長さは、経路中の枝の数で決まる。そして、距離δ(i, j)はiからjへの最短経路の長さと定義する。

グラフの直径とは、グラフ内における2接点間距離の最大値。

(n, d)グラフの直径最小化問題を解きたい。

直径1以下の(5, 2)グラフは存在しない。

→ このグラフが(5, 2)グラフ最小化問題の解の1つ。

(n, d)グラフの直径の下界値

1 + d + d2 + d3 + … + dk = (dk+ 1 - 1)/(d - 1)

距離がk以下の接点数を最大化。

直径の下界値をmとすると

(dm - 1) / (d - 1) >= n

m >= 「log_d {n(d - 1) + 1}」 - 1 => l(n, d)

「x」= Smallest integer >= x

「log_d n」 - 1 <= l(n, d) <= 「log_d n」 (3.1)

線形構成法 Linear Design Method

定義 枝(i, j)とした時に、jは次式で計算される。

j ≡ (a*i + b) * d + α (mod n) , α = 0, 1, 2, 3, ,,,d - 1 (3.2)

a, b: 整数

定理1
式(3.2)が(n, d)グラフを構成するのは、a*dとnの最大公約数がdの約数のときである。

n = 6, d = 2, a = b = 1 => (n, d)グラフを構成できる

i = 0の時
j = (1 * 0 + 1) * 2 + 0 ≡ 2 (mod 6)
= (1 * 0 + 1) * 2 + 1 ≡ 3 (mod 6)
i = 1の時, j = 4, 5
i = 2の時, j = 0, 1
i = 3の時, j = 2, 3
i = 4の時, j = 4, 5
i = 5の時, j = 0, 1

これらのiとjは、iからjに枝が伸びている事を表す。

有向線形構成法 Effective Linear Design Method

定義

1 = ± 1 の場合の線形構成法

定理2
有向線形構成された(n, d)グラフの直径は、「log_d n」を超えない。

定理2と式(3.1)より有向形成された(n, d)グラフの直径は最適解と等しいか1大きい。

湖の大きさを列挙する

問題

{
{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にマッチすることができるのでtrueを返す。

解法

wordの先頭から1文字ずつaに変換する。

a -> c

a -> ca

a -> cat

といった具合だ。aが決まるとbが決定する。これは、pattern = “abbab"の中のabそれぞれの出現回数とwordのlengthによって求めることができる。aとbが決定したらpatternにそって文字列を生成し、wordと一致するかをチェックしてあげれば良い。

計算量

wordのサイズをNとすると、aを決定するためにO(N)。bはO(1)で決定し、aとbの部分文字列を生成するための処理と、patternを元に候補となる文字列を生成し比較する処理がそれぞれO(N)(これらはネストではない)ので空間計算量はO(N2)となる。

ソースコード