101 & 121

101. Symmetric Tree

二分木がシンメトリーになっているか調べる。木を辿るときに右側から辿る方と、左側から辿る方を両方ともやって、値が等しいか確認する。私が実装したやつだと、それぞれ完全に終わりまで調べてから、その結果が左右で等しいか確認している。解説にある方法は、辿りながら値が揃わなかったところで即時 return しているので、そっちのほうが効率的だ。もう一つの方法はQueueに next を突っ込みながら、それぞれ値を確認する。何分で解いたか忘れたが、そんなにかからなかった。

• https://github.com/inohiro/LeetCode/blob/master/101_symmetric_tree/self.rb
• https://leetcode.com/problems/symmetric-tree/

121. Best Time to Buy and Sell Stock

株価を表す数字の配列が与えられて、最大の利益を求める。解けたけど1時間ちょい掛かってしまった。消えてなくなりたい。

最初に考えたやり方は買うときの額を配列の左側から、売るときの額を配列の右側から、添字がぶつかるところまで見て最大の利益を探す。これだと NxN = N² だけど、半分しか計算しないから全部計算するより効率的だろうと思っていた。しかし巨大な配列が与えられたときに TLE になってしまった。そもそも実行するまで O(N²) だったのに気がついてなかったのでダメだ。解く道筋を立ててからコーディングを始めることができたけど、ダメっぽいアルゴリズムには早く気が付きたい。

配列を見ながら最小値（買うべき額）と最大値（売るべき額）を更新しながら利益を計算する方法で書き直した。買う前に売れないので、買うべき額が更新されたら、売るべき額をリセットしないといけない。売るべき額は更新されても、買うべき額はリセットする必要はない。こういう感じでやれば O(N)。解説を読んだあとにコードを見返すと、添字 i, j は2つある必要はなかった。もっとエレガントに書きたい。

• https://github.com/inohiro/LeetCode/blob/master/121_best_time_to_buy_and_sell_stock/self_2.rb
• https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

83. Remove Duplicates from Sorted List

• https://github.com/inohiro/LeetCode/blob/master/83_remove_duplicates_from_sorted_list/self.rb
• https://leetcode.com/problems/remove-duplicates-from-sorted-list/

25分くらい掛かったけど一発で解けた。重複してる要素はスキップするというのを数日前の問題で見ていたので、LinkedList でも同じことをやればよかった。自分の実装では新しい ListNode を繋げてそれを結果としているけど、解説では与えられたListNodeを繋ぎ変えていて、そっちのほうが良いな。

Easy の問題でも安定して解けるようになりたいので（解けるべき問題が解けないのがやばい）、このまま続ける。

70. Climbing Stairs

登る階段のステップ数 n が渡されて、一度に一歩もしくは二歩登れるときに、登るパターンの総数を計算する。解けた、一発で解けたんだけど、なんか変な解き方をしてしまって、いまいちスッキリしない。

• https://github.com/inohiro/LeetCode/blob/master/70_climbing_stairs/self.rb
• https://leetcode.com/problems/climbing-stairs/

ナイーブにやると、一歩のときと二歩のときの全組み合わせを計算することになるので、なんだか（計算量が）まずそうだなと思った。とりあえずコードを書き始める前に、よく考えて方針を決めてから取り掛かる習慣をつけたいので、与えられるステップ数 n が変わったときに、組合せと結果がどう変わるかを書き出してみた。

すべてを一歩で登りきるとき、すべてを二歩で登りきるとき（ただし段数 n が偶数のとき）と数えていけば良さそうだが、一歩と二歩が混ざるときはそう簡単に計算できないことがわかった。総段数のうちで、二歩で歩く割合を徐々に増やしたときのパターンを数え上げれば良さそうだった。

書き出した組合せを見ると、それぞれのステップで、n 段数を登る試行 l のうち、二歩で登る回数が m のときの組合せ（lCm）の和が最終的な結果になることがわかった（このあと順列と組合せで混乱して、無駄に時間を使ってしまった)。一度配列を読むだけで良いので、計算量は O(n) 。

一方で、解説を読むと、あるステップ k のときの総パターン数はステップ k-1 と k-2 のときの和になっているので、フィボナッチ数を数えるように動的計画法で解けるねって書いてあって、なるほどーという感想だった。段数 1 のとき、2 のときがそれぞれわかってて、その先は (n-1) + (n-2) で数えていく。たしかに動的計画法だ。次回はもっと早く気が付きたい...

• https://github.com/inohiro/LeetCode/blob/master/70_climbing_stairs/solution_dp.rb

組合せの数の確認には、以下のサイトが便利だった。Ruby の Array#{combination, permutation} は知ってたけど、単純に数を数えてくれるメソッドがあると便利そうだ。

keisan.casio.jp