• 欢迎访问小澍的博客,编程记录,技术贴以及折腾的日常,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏我的博客吧

剑指offer刷题记——跳台阶

C++ root 2年前 (2019-03-17) 420次浏览 已收录 0个评论

跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
n<=39(点我直接练习

分析

经典的使用递归或者循环来解决的题目之一,在读完题目的时候一上来的思路就是先分析最简单的情况。1个台阶,就只有一种;2个台阶,则拥有一个一个上去和两个台阶直接上去的这两种方案。3往上就需要一种规律了,多写几个就发现,其实3以上的台阶,就是前面两个台阶数的总和。3个台阶的时候,就是1个台阶的情况和2个台阶的情况;4个台阶的时候,就是2个台阶和3个台阶的时候这两种情况之和;以此类推。无论是递归实现还是循环实现都是两三行代码的事情。为了专门联系一下递归,在写C++ 的时候使用了递归,而相同逻辑的递归代码换到python的时候,直接提示运行时间超时,无奈只能换成循环,不过这也造就了python效率比C++高的一次。

使用到的知识点

C++

递归

Python

同上

题解

class Solution {
public:
    int jumpFloor(int number) {
         if(number==0)
             return 0;
         if(number==1)
             return 1;
         if(number==2)
             return 2;
         else{
             return jumpFloor(number-1)+jumpFloor(number-2);
         }
    }
};
class Solution:
    def jumpFloor(self, number):
        if number == 0:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        else:
            preeStep = 1
            currStep = 2
            for i in range(number-2):
                preeStep,currStep = currStep,preeStep+currStep
            return currStep

XiaoShuBlog , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:剑指offer刷题记——跳台阶
喜欢 (0)
[gaosirgoo@foxmail.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址