LeetCode の解法メモ

Sep 19, 2020 ( Sep 22, 2020 更新 )

LeetCodeの解法メモです。

コーディング面接対策のために解きたいLeetCode 60問 | 新井康平 という記事を読んで、 LeetCode にまた挑戦したいと思った。 どうせ解いているうちに忘れていくので、解いたらなにかしらのメモを残していくことにした。

141. Liked List Cycle

ListNode という node が与えられる。 一連の node が循環しているかどうかを検証する。

すでに通った node を記録しておく

Linked List Cycle - Submission Detail - LeetCode

初手解法。 これだと他の submissions と比べてメモリを使ってしまう。

愚直に通った node を記録して、毎回検証していく。時間計算量と空間計算量が O(N) になる。(※ 解説より)

2 つのポインタを使う(解答より)

Linked List Cycle - Submission Detail - LeetCode

figure

こういうことらしい。 時間計算量は O(N) だけど 空間計算量は O(1) となる。 これ、知らないとできなくない?初見で思いつく人、すごいですね。算数とか数学のあるある解法であるのかな?

20. Valid Parentheses

stack っぽいものをつくる

Valid Parentheses - Submission Detail - LeetCode

Status: Output Limit Exceeded

おわた!

と思ったけど、無駄な print してると上記のエラーになるっぽい。

Valid Parentheses - Submission Detail - LeetCode

これはOK

解答を見て実装する

全然かんたんに実装できそうだった。

Valid Parentheses - Submission Detail - LeetCode


センスがなさすぎて消えたくなるけど次回もがんばるぞい

703. Kth Largest Element in a Stream

Kth Largest Element in a Stream - LeetCode

Retrun to top