合計の入れ替え Cracking The Coding Interview

問題

２つの整数配列が与えられる。それぞれの配列から１つずつ要素を決め、それらを交換した時に２つの配列の要素の合計値が一致するようなペアを見つける問題。

入力: {4, 1, 2, 1, 1, 2} と {3, 6, 3, 3}
出力: {1, 3}

解法

全列挙の解法 O(A*B)

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

ソースコード

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

問題

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

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

解法

全列挙で頑張る

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

トライ木を用いた解法

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

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

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

ソースコード

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

線形構成法 Linear Design Method

直径最小化問題 Minimizing Diameter Problem

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

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

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

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

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

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

1 + d + d² + d³ + … + d^k = (d^{k+ 1} - 1)/(d - 1)

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

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

(d^m - 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:　整数

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

例

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 の場合の線形構成法

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

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

湖の大きさを列挙する

問題

{
{0, 2, 1, 0},
{0, 1, 0, 1},
{1, 1, 0, 1},
{0, 1, 0, 1}
}

が与えられる。0の部分が湖で、縦横斜めで０が連なっている所は同じ湖とする。全ての湖のサイズを列挙する問題。

ソースコード

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

問題

文字列wordとパターンを表すpatternが入力値として与えれる。patternは'a'と'b'のみで構成されている。wordがpatternにマッチするか否かを求める問題。

例

word = “catcatgocatgo”, pattern = “abbab”
a -> cat
b -> go
とすればwordはpatternにマッチすることができるのでtrueを返す。

解法

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

a -> c

a -> ca

a -> cat

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

計算量

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

ソースコード

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

問題

xy平面上にN個の点が与えられる。最も多くの点を通るように直線を引いた時の点の最大値を求める問題

leetcode.com

解法

HashMapを用いることでO(N²)で解くことができる。forループを２回使い２つの点を全列挙する。２つの点のを結ぶ傾きをキーとして、HashMapに保存する。バリューには１つの座標を固定した時に、傾きが同じ値になるものの出現回数を保存する。

傾きを比較するために小数値ではなく分数で扱う。

少数値を比較するためには誤差を考慮する必要があるので、分数のまま扱うことにする。分母と分子をプロパティとして持つクラスを定義してあげる。 分数を作る際に、約分できる時は約分をする。約分するためにユークリッドの互除法を用いて最大公約数を計算する

keita-matsushita.hatenablog.com

分母がゼロになる時を注意する

傾きを計算する時に、２つの点のｘ座標が等しいと分母が0となってしまい傾きがINFとなる。この時は、Lineクラスに傾きがINFか否かをチェックするためのプロパティを用意し場合分けに使う

同一点を考慮する

入力値として与えられる点は、全く同じ座標のものも含まれる。よって同一座標の数をカウント(dup)することで対応する。

コード

階乗のゼロ Cracking the Coding the Interview

問題

整数Nが与えら、Nの階乗を計算した時に、末尾に連なる0の数を求める問題。

解き方

どんな時に末尾に０が来るか考える。階乗の計算では足し算はなく掛け算のみなので、10を掛けた時に末尾に0がつく。また、１０は2×5なので２と５を掛けた回数分、０が着くことが分る。また、５を掛ける回数は２を掛ける回数に比べ多いので、５を掛ける回数を数えれば良い。

例
N = 10の時
階乗は1×2×3×4×5×6×7×8×9×10

上記で５を掛けているのは２回(5, 10)なので末尾には0が２つ着く。これはN / 5で求められる。また、25を掛けた場合を考えると、５を２回掛けている事が分る。よってコードは以下のようになる。