力扣刷题(2020/6/9)

  • 时间:
  • 来源:互联网
  • 文章标签:

青蛙跳台阶问题

题目描述:

  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1000000007,如计算初始结果为:1000000008,请返回 1。
  • 0 <= n <= 100在这里插入图片描述
    通过手动计算前几个数据,可以发现本题符合“斐波那契数列”。有一点需要注意,本题目对算法的性能要求比较高,因而要采取“非递归算法”进行求解。
class Solution {
    public int numWays(int n) {
        int a,b,c;
        if(n<=1){
            return 1;
        }
        else{
            a=1;
            b=1;
            for(int i=2;i<=n;i++){
                c=a;
                a=a+b;
                b=c;
                a=a%1000000007;    //此处需注意,由于“数据过大”和题目要求,必须采取相应策略,防止数据异常。
            }
            return a;
        }
    }
}

PS: “a=a%1000000007;”此处需注意,由于“数据过大”和题目要求,必须采取相应策略,防止数据异常。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-words-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

本文链接http://www.taodudu.cc/news/show-82826.html