Android防重复点击 HTML框架 numpy 分布式服务 class datetime templates layout vuejs2 sqlalchemy dns camera 河南普通话考试报名官网 jquery第一个子元素 jquery选择子元素 idea大小写转换快捷键 matlab网页版 python读文件 python免费教程 python的lambda函数 python服务器开发 java的substring java的方法 java中instanceof java对象序列化 java八大基本数据类型 win10计算器下载 销售单软件 神剪辑教程 反转颜色 emit flash制作工具 tomcat修改端口 小米游戏鼠标 服务器文件共享软件 web聊天室 cad文件 dns劫持怎么解决 rdpwrap 例程
当前位置: 首页 > 学习教程  > 编程语言

[剑指 offer]10 - 2 青蛙跳台阶问题 Java实现

2020/12/5 10:01:36 文章标签:

题目 剑指 Offer 10- II. 青蛙跳台阶问题 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e97(1000000007),如计算初始结果为:1000000008&#xff0…

在这里插入图片描述

题目

剑指 Offer 10- II. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2
示例 2:

输入:n = 7
输出:21
示例 3:

输入:n = 0
输出:1
提示:

0 <= n <= 100

代码

他来了他来了 他带着跳台阶问题走来了
上一题的时候我还在想下一题会不会是那个…跳台阶的问题
然后…我很莽的用递归写下了以下代码…

class Solution {
    public int numWays(int n) {
        return start(n) % 1000000007;
    }
        public int start(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 0) {
            return 1;
        }else  if ( n < 0 ){
            return 0;
        }
        return start(n - 1) + start(n - 2);
    }
}

然后就…就超时了, 输入44就超时了…挺突然的…
之后我想了想, 既然我不喜欢递归…那为什么要用递归呢,和上一题用一样的解法不会好了吗

class Solution {
    public int numWays(int n) {
        int flag1 = 1, flag0 = 1;
        int temp = 0;
        if ( n == 0 ){
            return 1;
        } else if (n == 1){
            return 1;
        }
        for (int i = 2; i <= n; i++) {
            temp = (flag1 + flag0) % 1000000007;
            flag1 = flag0;
            flag0 = temp;
        }
        return temp;
    }
}

之后! 我又想了想不行不行不可以逃避使用递归(x
然后去学习了一些别人未超时的解法!
和我不同的是他们会定义一个全局变量数组来辅助进行递归不用像我一样直接像一头公牛一样的直接莽过去
等我二刷的时候我再来用不熟悉的解法!


本文链接: http://www.dtmao.cc/news_show_450129.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?