122, 136 and 141
122. Best Time to Buy and Sell Stock II
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
- https://github.com/inohiro/LeetCode/blob/master/122_best_time_to_buy_and_sell_stock_2/self.rb
最初問題の意味がよくわからなかった。121では一度ずつの「買う」と「売る」しか許されてなくて、その制約の下で最大の利益（安く買って高く売る）を求める。122 では売って買ってを何度もできる（売るときは、買ったものがないといけない。また、もう買っているなら、売らないと買えない）。
とりあえず利益が出たらすぐ売るというアイデアで考えてみたら、いくつかの例ではうまく行きそうだったので、実装したら通った。26分くらい
136. Single number
- https://leetcode.com/problems/single-number/
- https://github.com/inohiro/LeetCode/blob/master/136_single_number/self.rb
数値の配列が与えられて、その中でひとつだけダブらないものを見つける。こういうのは HashMap だな、ということですぐ解けた。8分。
141. Linked List Cycle
- https://leetcode.com/problems/linked-list-cycle/
- https://github.com/inohiro/LeetCode/blob/master/141_linked_list_cycle/src/main/java/Solution.java
Rubyで解かせてくれなかったので、Javaで解いた。最初は ListNode#val の値だけ HashMap に入れようとしたが、結局オブジェクトごと入れた。そんなに難しくなかったけど時間がかかった。
21. Merge two sorted lists
- https://leetcode.com/problems/merge-two-sorted-lists/
- https://github.com/inohiro/LeetCode/tree/master/21_merge_two_sorted_lists
2つのソートされた Linked List が与えられて、マージした新しい Linked List を返す。解けず。
解説を読んだところ、再帰でやるやつと、while で最後のノードまで読みながらごにょごにょする方法が説明されていた。私は一度再帰でやろうとしてできず、while でごにょろうとしたが結局できず。複雑... もうちょっと余裕のあるときに見直す。
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 = N2 だけど、半分しか計算しないから全部計算するより効率的だろうと思っていた。しかし巨大な配列が与えられたときに TLE になってしまった。そもそも実行するまで O(N2) だったのに気がついてなかったのでダメだ。解く道筋を立ててからコーディングを始めることができたけど、ダメっぽいアルゴリズムには早く気が付きたい。
配列を見ながら最小値（買うべき額）と最大値（売るべき額）を更新しながら利益を計算する方法で書き直した。買う前に売れないので、買うべき額が更新されたら、売るべき額をリセットしないといけない。売るべき額は更新されても、買うべき額はリセットする必要はない。こういう感じでやれば O(N)。解説を読んだあとにコードを見返すと、添字 i, j は2つある必要はなかった。もっとエレガントに書きたい。
