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

剑指offer刷题记——变态跳台阶

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

变态跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
n<=39(点我直接练习

分析

和上一道题比起来,如果使用递归那么无论是何种语言都会带来巨大的代价,所以还是需要分析规律。分析方法和之前类似:1个台阶为1,2个台阶为2,到了3个台阶的时候,除了加上1个台阶和2个台阶的情况,还需要再加上3个台阶自身的情况;4个台阶的时候,则为前面所有的情况总和再+1,即再加上直接跳上去的情况。所处规律已经很明朗了,本题的公式即为累加求和。

使用到的知识点

C++

循环

Python

同上

题解

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0)
            return 0;
        if(number == 1)
            return 1;
        if(number == 2)
            return 2;
        else{
            int pree = 1,current = 2,newstep = 0;
            for(int i = 0 ; i<number-2;i++){
                newstep = 1+pree+current;
                pree = pree+current;
                current = newstep;
                }
            return newstep;     
        }
    }
};
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        if number == 0:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        else:
            preeStep = 1
            currStep = 2
            newstep = 0
            for i in range(number-2):
                newstep = 1+preeStep+currStep
                preeStep,currStep = preeStep+currStep,newstep
            return newstep

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

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

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