'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(N2)となる。
ソースコード
平面上のN個の点を最も多く通る線を見つける
問題
xy平面上にN個の点が与えられる。最も多くの点を通るように直線を引いた時の点の最大値を求める問題
解法
HashMapを用いることでO(N2)で解くことができる。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を掛けた場合を考えると、５を２回掛けている事が分る。よってコードは以下のようになる。
