• 剑指offer--Day3


    递归的使用,找到规律后今天的题就很好做了。

    Day3:剑指 Offer 10- I. 斐波那契数列

    力扣链接:剑指 Offer 10- I. 斐波那契数列

    题目:写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:
    F(0) = 0, F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
    斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
    答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

    斐波那契(Fibonacci)数列:1 1 2 3 5 8 13 21 34…

    题解:从上边逻辑看呢,n>1的时候f(n)=f(n-1)+f(n-2) 依此类推,可以得到斐波那契(Fibonacci)数列的规律,每个数都等于前两个数相加。循环遍历,由于index=2时,val=1,所以第二个数需要0+1,因此初始值需要设为0与1,在根据循环不断赋值,得到结果。

    class Solution {
        public int fib(int n) {
            if(n<=1){
                return n;
            }
            int a=0;
            int b=1;
            int c=0;
            
           for(int i=2;i<=n;i++){
                c=(a+b)%1000000007;
                a=b;
                b=c;
            }
            return c;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    Day3:剑指 Offer 10- II. 青蛙跳台阶问题

    力扣链接:剑指 Offer 10- II. 青蛙跳台阶问题

    题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
    答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

    题解:青蛙一次可以跳一阶或者两阶,那这样的话青蛙跳上第n阶就需要,f(n)=f(n-1)+f(n-2) ,然后在分析,n=1的时候有1种方式,n=2的时候有2种方式,这样能确定初始值1与1,n<2时n=1,n>2进行循环,确认值,其实跟上边那题的逻辑一样

    class Solution {
        public int numWays(int n) {
            if(n<2){
                return 1;
            }
            int a =1;
            int b=1;
            int c=0;
            for(int i=2;i<=n;i++){
                c=(a+b)%1000000007;
                a=b;
                b=c;
            }
            return c;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    END>>>
    努力不为别人,而是让自己成为自己都羡慕的人!!!

  • 相关阅读:
    redis安装、redis 普通用户启动
    数据结构基础9:排序全家桶
    源码框架-​1.Spring底层核心原理解析
    php正则表达式汇总
    SpringBoot 22 Swagger配置扫描接口和开关、过滤url、根据环境决定使用
    《从菜鸟到大师之路 正则表达式 篇》
    SpringMVC学习---第二课
    写好技术书籍
    JS基本小知识:函数
    千万播放竟有通用公式?B站被小看的爆款机会!
  • 原文地址:https://blog.csdn.net/qq_45656077/article/details/126125146