首页 > 其他分享 >剑指Offer面试题10:斐波那契数列

剑指Offer面试题10:斐波那契数列

时间:2023-09-23 16:34:34浏览次数:40  
标签:10 面试题 数列 递归 Offer 斐波 fib step 问题

一、题目

剑指Offer面试题10:斐波那契数列_递归

示例:

输入:4
返回值:3
说明:
根据斐波那契数列的定义可知,fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3,所以答案为3。

二、题解

2.1解法一:迭代相加

知识点:动态规划

动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

思路:

斐波那契数列初始化第1项与第2项都是1,则根据公式第0项为0,可以按照斐波那契公式累加到第剑指Offer面试题10:斐波那契数列_ci_02项。

具体做法:

  • step 1:低于2项的数列,直接返回n。
  • step 2:初始化第0项,与第1项分别为0,1.
  • step 3:从第2项开始,逐渐按照公式累加,并更新相加数始终为下一项的前两项。

Java实现代码:

public class Solution {
    public int Fibonacci(int n) {
        //从0开始,第0项是0,第一项是1
        if(n <= 1)    
             return n;
         int res = 0;
         int a = 0;
         int b = 1;
         //因n=2时也为1,初始化的时候把a=0,b=1
         for (int i = 2; i <= n; i++){
         //第三项开始是前两项的和,然后保留最新的两项,更新数据相加
             res = (a + b);
             a = b;
             b = res;
         }
        return res;
    }
}

解法二:递归法

知识点:递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程,最重要的就是查看能不能讲原本的问题分解为更小的子问题,这是使用递归的关键。

思路:

我们也可以根据公式倒推:

  • 终止条件: 当递归到数列第1项或是第0项的时候,可以直接返回数字。
  • 返回值: 返回这一级子问题的数列值。
  • 本级任务: 获取本级数列值:即前两项相加。

具体做法:

  • step 1:低于2项的数列,直接返回n。
  • step 2:对于当前n,递归调用函数计算两个子问题相加。

Java实现代码:

public class Solution {
    public int Fibonacci(int n) {
        //从0开始,第0项是0,第一项是1
        if (n <= 1)    
             return n;
        else{
            //根据公式递归调用函数
            return Fibonacci(n - 1) + Fibonacci(n - 2); 
        }
    }
}

标签:10,面试题,数列,递归,Offer,斐波,fib,step,问题
From: https://blog.51cto.com/u_16244372/7579035

相关文章

  • 熬过月余终见offer,一份Android面经
    前言最近我一直在牛客刷帖子看到好多对于现在IT环境的负面消息,自己也是找了一个多月Offer一个都没有,又看到这些感觉面试的勇气又少了…这种状态我根本就不知道任何转变,真的是投简历都不想投!就在这样的状态下,朋友说他那边内推有消息了,说待会HR会和我联系。怎么说了,并没有太多惊喜,因......
  • 微软最热门的10款前端开源项目!
    本文来盘点微软开源的十大前端项目,这些项目在Github上获得了超过45万Star!VisualStudioCodeVisualStudioCode是一款由微软开发的开源的代码编辑器。它支持多种编程语言,如C、C++、C#、Python、JavaScript和TypeScript等,并提供丰富的插件生态系统来扩展功能。VSCode......
  • 关于部分买家的主板BIOS升级操作说明,针对畅网的N5105 N6005 J6412 J6413的BIOS升级操
    说明:因为BIOS更新了,修复一些小问题,如果你有需要更新请按我的傻瓜式步骤操作。本次升级涉畅网的NAS51056005的主板和小主机V1V2V3V4V5版本的BIOS更新,本次更新bios同步更新cpu微码。更新后部分界面有些许变化。操作步骤:NAS主板部分先看下原先的bios版本,2022/08/31下面......
  • 2023-09-23:用go语言,假设每一次获得随机数的时候,这个数字大于100的概率是P。 尝试N次,其
    2023-09-23:用go语言,假设每一次获得随机数的时候,这个数字大于100的概率是P。尝试N次,其中大于100的次数在A次~B次之间的概率是多少?0<P<1,P是double类型,1<=A<=B<=N<=100。来自左程云。答案2023-09-23:首先,我们可以使用动态规划来解决这个问题。我们可以定义一个二......
  • Java:JSR 310日期时间体系LocalDateTime、OffsetDateTime、ZonedDateTime
    JSR310日期时间体系:LocalDateTime:本地日期时间OffsetDateTime:带偏移量的日期时间ZonedDateTime:带时区的日期时间(目录)日期时间包importjava.time.LocalDateTime;importjava.time.OffsetDateTime;importjava.time.ZonedDateTime;importjava.time.format.DateTimeF......
  • 2023-09-23:用go语言,假设每一次获得随机数的时候,这个数字大于100的概率是P。 尝试N次,其
    2023-09-23:用go语言,假设每一次获得随机数的时候,这个数字大于100的概率是P。尝试N次,其中大于100的次数在A次~B次之间的概率是多少?0<P<1,P是double类型,1<=A<=B<=N<=100。来自左程云。答案2023-09-23:首先,我们可以使用动态规划来解决这个问题。我们可以定义一个二维数组d......
  • 10-ES客户端索引相关操作
    新建业务包├─config #配置文件├─controller #控制器├─entity #实体映射│└─response #响应实体└─service #相关业务在response包下,新建两个类,分别是ResultCode(interface),ResponseResult.java:ResultCode.java:/***@authorBNTang......
  • 随想录Day4|24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07.
    随想录Day4|24.两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题02.07.链表相交、142.环形链表Ⅱ 24.两两交换链表中的节点文章讲解视频讲解给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,......
  • 【2023潇湘夜雨】WIN11_Pro_22H2.23545.1000软件选装纯净版9.23
    【系统简介】=============================================================1.本次更新母盘来自WIN11_Pro_23H2.23545.1000。2.增加部分优化方案,手工精简部分较多。3.OS版本号为23545.1000。精简系统只是为部分用户安装,个别要求高的去MSDN下。4.集成《DrvCeo-2.13.0.8》网卡版、......
  • vue3的面试题
    1.什么是Vue3?Vue3有哪些新增特性?答:Vue3是Vue.js框架的最新版本,它增加了很多新特性,包括CompositionAPI、Teleport、Suspense和Fragment等。2.Vue3CompositionAPI是什么?它的作用是什么?答:Vue3CompositionAPI是Vue3中的一个新特性,它的作用是将组件中的逻辑分解成可复用的可......