Kotlin Leetcode - 70. Climbing Stairs

題目連接

class Solution {
    fun climbStairs(n: Int): Int {
    }
}

解題思路

這一題是基礎的遞迴題目

不過如果純使用遞迴解題，會遇到時間過長問題

要對解法進行一些最佳化

Kotlin 參考解答

根據遞迴的想法，我們可以想到以下解法

class Solution {
    fun climbStairs(n: Int): Int {
        return when {
            n == 0 -> 0
            n == 1 -> 1
            n == 2 -> 2
            else -> climbStairs(n-1) + climbStairs(n-2)
        }
    }
}

直接使用這個解法的話，會因為呼叫的函數個數過多

導致運算的時間過長

為了避免這個問題

我們可以改用迴圈

class Solution {
    fun climbStairs(n: Int): Int {
        if (n <= 2) {
            return n
        }
        var result = 0
        var n1 = 1
        var n2 = 2
        (3..n).forEach { _ ->
            result = n1 + n2
            n1 = n2
            n2 = result
        }
        return result
    }
}

或者，我們可以利用 kotlin 的 tailrec 關鍵字

利用尾遞迴的方式進行改寫

讓 kotlin 編譯器協助這段程式的最佳化

class Solution {
    fun climbStairs(n: Int): Int {
        return climbStairsRec(n, 1, 1)
    }

    private tailrec fun climbStairsRec(n: Int, first: Int, second: Int): Int {
        return when (n) {
            1 -> second
            else -> climbStairsRec(n - 1, second, first + second)
        }
    }
}

---

• 回到 leetcode 列表
• 回到 Grind 75 列表