LeetCode 練習メモ

Dec 22, 2019 ( Dec 24, 2019 更新 )

LeetCode の問題を解いていったときのメモとか感想などをここに書いていきます。 1ヶ月30問を解くペースを目標にしています。

課題の方針

課題の選び方

解き方

  • 1回目は自力で回答(制限時間: 30分目安)
    • とりあえずパスしたらOK
  • 解答を確認し、2回目をやる。一応30分目安で解くけど初見じゃないのでもう少し短い時間でできるはず

課題日記

2019/12/22 Sun

  • Add Two Numbers - LeetCode
    • 1回目
      • 全然うまくできなかった
      • ただ力技で回答しただけ
    • 解説
      • 解説は再帰使ってないけど、再帰使うと遅くなるのかな…わからん
      • 再帰を使わないバージョン
        • まだ遅いっぽいなーわからん。
        • なんか他の解法見てもたいしてやってること変わらないので、実行時の誤差と思ってもよいかもしれない

2019/12/23 Mon - 2019/12/24 Tue

  • 基本のデータ構造からStack
    • Climbing Stairs - LeetCode
      • 1:10 開始
      • Input: 4 のとき
        • 1 + 1 + 1 + 1
        • 2 + 2
        • 1 + 2 + 1
        • 2 + 1 + 1
        • 1 + 1 + 2
      • 1 引くケースと 2 引くケースを用意する。0 になるまで繰り返して、 0 になったら Output に 1 追加する
        • Stack 関係あるのだろうか… 違う解法のほうが効率いいかもだけど、一応書いてみる
        • 再帰したら out of memory に (1:49)
      • わからないので解答を見る。全然だめだな…
      • https://leetcode.com/problems/climbing-stairs/solution/
        • 書いたやり方だと Bruce Force で 2^n
      • 解法2) メモ化再帰
        • Time Complexity: O(n)
        • Space Complexity: O(n)
        • https://leetcode.com/submissions/detail/288017640/
        • 1度計算された結果を保持する
          • 合計 step 数が 2 の場合の計算結果は、全件探索時に 2回必要になる
          • 合計 step 数が 4 の場合の計算結果は、全件探索時に 5回必要になる
          • すでに計算されている結果を保持して返せば時間計算量、空間計算量ともに節約できる
      • 解法3) Dynamic Programming
      • 解法4) フィボナッチ数列
      • 解法5) Binets Method
      • 解法6) フィボナッチの公式

2019/12/25 Wed

Retrun to top