LinkedListが回文になっているか否かを判定 Palindrome Linked List in LeetCode
問題
解法
通常の速さと、その２倍の速さでLinkedListを探索していくと、早いほうが末尾に到着する時に遅い方はちょうど中間地点にいる。 中間地点まできたら、そこから末尾まで進むと同時にリストを逆順にしていく。 ここまでの操作で、リストの後半の部分がひっくり返った状態で得られるので、あとはリストの前半部分と数値が一致するかを見ていく。
ソースコード
Google Code Jam 2016 B Rank and File 解法
問題
N×Nの行列を考える。各マスには数字が振られており、どの行もどの列も昇順になっている。
N×Nの行列では行と列の数は合計で2N個だが、この問題では2×N-1個の行か列のリストが与えられる。
取り除かれた行又は列のリストを出力する問題
Dashboard - Round 1A 2016 - Google Code Jam
解法
１行目と１列目の２つリストを考えた時に、それぞれの先頭の数字は同じ数字となる。このように列と行は必ず同じ数字を含んでいる。つまり、2N個のリストが与えられた場合、それぞれの数字の出現回数は必ず偶数個となる。よって取り除かれた数字を見つけるためには、出現回数が奇数の物をピックアップすればOK。この解法の計算量はO(N2)。
