LeetCode – #70 爬楼梯(Top 100)

一起养成写作习惯!这是我参与「日新计划 4 月更文挑战」的第16天,点击查看活动详情。

前言

本题为 LeetCode 前 100 高频题

我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅leetcode官网读。

LeetCode 算法到目前我们已经更新了 69 期,我们会保持更新时间和进ios15度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在ios16上班路上阅读,长久积累会有很大提升。

不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力swifter满足大家的需求。

难度水平:简单

1. 描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

2. 示例

示例 1

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

面试例 2

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

约束条件:

  • 1Swift <= n <= 45

3. 答案

class ClimbingStairs {
    func climbStairs(_ n: Int) -> Int {
        if n < 0 {
            return 0
        }
        if n == 0 || n == 1 {
            return 1
        }
        var prev = 0, post = 1, total = 0
        for i in 1...n {
            total = prev + post
            prev = post
            post = total
        }
        return total
    }
}
  • 主要思想:动态编程,dp = dp + dp[i - 2]
  • 时间复杂度: O(n)
  • 空间复杂度: O(1leetcode在线编程网站)

该算法题解的仓库:LeetCode-Swift

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好ios下载者共ios是什么意思同维护,我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容,也整理收集优秀的学习资料。

发表评论

提供最优质的资源集合

立即查看 了解详情