LeetCodeに毎日挑戦してみた 70. Climbing Stairs(Python、Go)


はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門+アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

18問目(問題70)

70. Climbing Stairs

問題内容

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

(日本語訳)

あなたは階段を上っています。nトップに到達するためのステップが必要です。

1 登ったり、2足を踏み入れたりするたびに。いくつの明確な方法でトップに登ることができますか?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

考え方

  1. こちら冷静に考えてみるとn番目のフィボナッチ数を求めるのと同じ意味で出題されているとわかります。

  2. 今回はループ処理で解いてみました。再帰的に説くことも可能です。

  • 解答コード
class Solution:
    def climbStairs(self, n):
        a, b = 1, 1
        for i in range(n):
            tmp = b
            b = a + b
            a = tmp

        return a
  • Goでも書いてみます!
func climbStairs(n int) int {
    a := 1
    b := 1
    tmp := 0
    for i := 0; i < n; i++ {
        tmp = b
        b = a + b
        a = tmp
    }
    return a
}