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?

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

Constraints:

1 <= n <= 45

Hint 1:

To reach nth step, what could have been your previous steps? (Think about the step sizes)

題目翻譯

今天有 n 個階梯，然後可以一次採 1 階或 2 階。計算在 n 個階梯之後，可以有幾種登階的可能性

解法解析

恩，很簡單就是一個費氏數列。差別的地方在於，最後的結果要怎麼儲存，可以使用一個陣列去儲存每次的結果，但是這樣就會花費一個陣列的記憶體空間。覺得最後的方式還是只使用一個變數儲存最後的值就好了。不變 Time complexity 的情況下，有最少的 Space complexity。

程式範例

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    if (n < 2) {
        return n;
    }
    let first = 1;
    let second = 2;
    for (let i = 3; i <= n; i++) {
        const third = first + second;
        first = second;
        second = third;
    }
    return second;
};

Go

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }

    n1, n2 := 1, 2

    for i := 3; i <= n; i++ {
        n2, n1 = n1+n2, n2
    }
    return n2
}

Swift

class Solution {
    func climbStairs(_ n: Int) -> Int {
        if n < 3 { return n }

        var cur = 2
        var pre = 1
        for i in 3...n {
            let temp = pre
            pre = cur
            cur = cur + temp
        }
        return cur
    }
}

Kotlin

class Solution {
    fun climbStairs(n: Int): Int {
        return when {
            n < 2 -> n
            else -> {
                var first = 1
                var second = 2

                for (i in 3..n) {
                    val temp = first + second
                    first = second
                    second = temp
                }

                second
            }
        }
    }
}

LeetCode Solution, Easy, 70. Climbing Stairs

Comments

LeetCode Solution

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

我的 MacBook Pro (Apple Silicon) 設定

ChatGPT 下的發展預想

一些覺得有用的工具蒐藏

LeetCode Solution, Medium, 607. Sales Person

70. Climbing Stairs

題目敘述

題目翻譯

解法解析

程式範例

Python

JavaScript

Go

Swift

Kotlin

Command Palette

Comments

LeetCode Solution

More from this blog

70. Climbing Stairs

題目敘述

題目翻譯

解法解析

程式範例

Python

JavaScript

Go

Swift

Kotlin