LinkedListが輪になっているかを判定する Hacker Rank
問題
LinkedListの先頭のノードheadが与えられ、そのリストがサイクルしているかを判定する問題
解法
異なるスピードで２箇所から探索を開始し、探索途中に２つの探索位置が一致した場合、そのリストは輪となっていることが分る。
ソースコード
DP: Coin Change in Hack Rank
問題
N枚の異なるコインと支払いたい金額moneyが与えれる。与えられたコインはそれぞれ無限に使える時、与えられたコインを使って合計金額がmoneyとなるような支払い方法の通り数を求める問題。
解法
動的計画法と用いることで計算量O(N*money)で解くことができる。
コインは配列で与えれる。配列のインデックスをiと置く。i番目から最後の要素までのコインを使って、これまでの金額の総和がsumとなるような支払い方法の通り数を求める関数をwayToPay(int i, int sum)と置く。すると
watToPay(i, sum) = Σ(i ≦ k < n) wayToPay(k, sum + coins[k])
と書くことができる。後はこれを再帰を用いて解いてあげれば良い。また、処理中にiとsumの組合せは何度も登場するので、その値を配列に保存し、一度登場した組合せは保存した値を再利用することで計算量を大幅にカットすることができる。
重複した組合せを数えないために、先程の式の右辺の第一引数ではkを指定することにも注意。
ソースコード
空間計算量O(1)で配列内のユニークな数字を見つけるBit Manipulation: Lonely Integer
問題
n個の要素(整数)の配列が与えらる。配列内の要素はただ１つを除いて、全て２回ずつ現れる。１回のみ出現するユニークな数字を求める問題。
解法
この問題は、XORを用いることで空間計算量O(1)で解くことができる。
上記のように配列内の全ての要素をXORすることでユニークな値を見つけることができる。これにはXORの以下の性質があるからだ。
a) どんな数字でも自分自身とXORを取ると０になる。
b) どんな数字でも０とXORを取るとその数字自身になる。
今回の問題では、１つを除いて配列内の数字は同じ数字がちょうど２回出現する。もし、配列内の全ての数字がちょうど２回ずつ出現するとしたら、それらのXORは０となる。実際には１つだけ出現回数が１回のものがあるので、０とユニークな数字をXORすると、そのユニークな数字が得られる。
