平面上の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を掛けた場合を考えると、５を２回掛けている事が分る。よってコードは以下のようになる。
LinkedListが回文になっているか否かを判定 Palindrome Linked List in LeetCode
問題
解法
通常の速さと、その２倍の速さでLinkedListを探索していくと、早いほうが末尾に到着する時に遅い方はちょうど中間地点にいる。 中間地点まできたら、そこから末尾まで進むと同時にリストを逆順にしていく。 ここまでの操作で、リストの後半の部分がひっくり返った状態で得られるので、あとはリストの前半部分と数値が一致するかを見ていく。
