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 を見たら、問題の種類から選べる画面があることに気がついて、これはこれで良さそうだ
26, 27 配列から{重複, 指定された要素}を取り除いたあとの要素数
両方とも Easy だけど、よくわからなかったので解説を読んだ。両方とも2つの変数を使って、先を行く変数と、後ろからついていく変数が指す配列中の値をつかって、条件に合う要素数を 数える。
- https://github.com/inohiro/LeetCode/blob/master/26_remove_duplicates_from_sorted_array/self.rb
- https://github.com/inohiro/LeetCode/blob/master/27_remove_element/solution.rb
26 は配列から、重複している数を取り覗いたあとの要素数を返すプログラムなので、Ruby で書くと nums.uniq.length でできてしまう。また、27 は配列から、指定された数字を取り除いたあとの要素数を数えるプログラムなので、nums.remove(val); nums.length でできてしまう。
プロコン（競プロ）だと上記のように解けばよいけど、コーディング面接だと配列の扱いとか、解法を思いつけるかというところが評価されるのでめんどくさいなと思う... 「そもそも実務ではこんなコード書かないだろう」とか本当に毎回思うけど、仕方ないのでこういう感情は抑えて解くしかない。
