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) で数えていく。たしかに動的計画法だ。次回はもっと早く気が付きたい...
組合せの数の確認には、以下のサイトが便利だった。Ruby の Array#{combination, permutation} は知ってたけど、単純に数を数えてくれるメソッドがあると便利そうだ。
Weekly Contest 60 に参加
733. Flood Fill
- https://github.com/inohiro/LeetCode/blob/master/contests/60_2017_11_25/a.rb
- https://github.com/inohiro/LeetCode/blob/master/contests/60_2017_11_25/a_solution.rb
二次元配列の探索系問題。再帰でDFSしようとするところまでは良かったが、正しい終了条件が見つけられず stack too deep のまま解決できなかった。フォーラムに投稿されている解法のうち、シンプルに実装されているものを ruby で書き直した。わかりやすい。
734. Sentence Similarity
- https://github.com/inohiro/LeetCode/blob/master/contests/60_2017_11_25/b.rb
- https://github.com/inohiro/LeetCode/blob/master/contests/60_2017_11_25/b_solution.rb
2つの文字列の配列と、単語のペアの配列が渡されて、片方の文字列の単語をペアに基づいて置き換えるともう片方の文字列と一致するかチェックするもの。ハッシュマップを使うというのはすぐにわかったが、辞書の中である単語に対応する語が複数存在するパターンが考えられていなくて、最初にそこでエラーになった。最終的に解くことができたが、デバッグなどに無駄に時間をかけてしまい、時間内には解けなかった（3分オーバー）。
a と同様に、他の人の解法を参考に読んでみたが、簡潔でわかりやすかった。私の書いたコードでは words1 を置き換えたものと words2 がチェックしたあと、逆の関係（words2を置き換えたものと words1が一致するか）もチェックしていたが、不要だったようだ。よく考えればまあそうか :thinking_face:
Easy の問題は時間内に解けるようにしたい。Medium, Hard は前回と同様手がつかず。
11. Container With Most Water
O(n2) なアルゴリズムを書いてTLEを食らって、枝刈りするようにしてみたが結局解けず。
解説を読んだところ、配列の始まりと終わりから範囲を狭めながら、得られる面積の最大値を求める。確かに最大の面積を求めたいのだから、狭い範囲から探すよりも、広い範囲から探すほうが理にかなっているか。2つの添字を動かしながらなんとかする、という問題が続いた。解き方のアイデアさえも思い浮かばないことが多いけど、数をこなせばふわっとわかるようになるんだろうか...
- あまり考えずに手を動かしてしまうことが多いので、よく考えてから動くようにしている。結局やろうとしていることを説明できないといけないわけで。
- 久しぶりに HackerRank を見たら、問題の種類から選べる画面があることに気がついて、これはこれで良さそうだ
