inohilog

/var/log/inohiro

160. Insersection of Two Linked Lists

スタートが異なる LinkedList が2つ与えられ、途中で合流しているか判定する問題。最初はそれぞれ次を読みながら、ぶつかるか読み切るまですすめる方法でやろうとしたが、途中で HashMap (HashSet)に入れたほうが楽じゃんと思って、そっちで書いた。もろもろ込みで20分くらい。LinkedList を読むだけというのは簡単だよね。繋ぎ変えがめんどくさい。

今回もRubyがサポート外だったので、Java で。最近お仕事でJavaを書いていることもあり、Javaへの心的なハードルが低くなっている。gradle init --type=java-application でサクッと新しい環境が作れるのも便利だし、Visual Studio Code で簡単にデバッグ実行できるし。

122, 136 and 141

122. Best Time to Buy and Sell Stock II

最初問題の意味がよくわからなかった。121では一度ずつの「買う」と「売る」しか許されてなくて、その制約の下で最大の利益(安く買って高く売る)を求める。122 では売って買ってを何度もできる(売るときは、買ったものがないといけない。また、もう買っているなら、売らないと買えない)。

とりあえず利益が出たらすぐ売るというアイデアで考えてみたら、いくつかの例ではうまく行きそうだったので、実装したら通った。26分くらい

136. Single number

数値の配列が与えられて、その中でひとつだけダブらないものを見つける。こういうのは HashMap だな、ということですぐ解けた。8分。

141. Linked List Cycle

Rubyで解かせてくれなかったので、Javaで解いた。最初は ListNode#val の値だけ HashMap に入れようとしたが、結局オブジェクトごと入れた。そんなに難しくなかったけど時間がかかった。

21. Merge two sorted lists

2つのソートされた Linked List が与えられて、マージした新しい Linked List を返す。解けず。

解説を読んだところ、再帰でやるやつと、while で最後のノードまで読みながらごにょごにょする方法が説明されていた。私は一度再帰でやろうとしてできず、while でごにょろうとしたが結局できず。複雑... もうちょっと余裕のあるときに見直す。