当前位置: 首页 > news >正文

【LeetCode】剑指 Offer 10- I. 斐波那契数列 p74 -- Java Version

题目链接

1. 题目介绍()

写一个函数,输入 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。

【测试用例】:
示例 1:

输入:n = 2
输出:1

示例 2:

输入:n = 5
输出:5

【条件约束】:

提示:

  • 0 <= n <= 100

2. 题解

2.1 递归实现 — O(2n)

时间复杂度O(2n),空间复杂度O(1)

class Solution {// 第一种方法:递归实现public int fib(int n) {// 1. n为0时,返回0if (n == 0) return 0;// 2. n为1时,返回1else if (n == 1) return 1;// 3. 从第三个数开始,之后的每个数都为前两项数的和else return fib(n-1) + fib(n-2);}
}

在这里插入图片描述
改进: 使用数组保存每一次的运算结果;改进之后时间复杂度: 从2的n次方降为了O(n²),空间复杂度:O(n)。

class Solution {int[] ints;public int fib(int n) {ints = new int[n];if(n <= 1) return n;return (f(n - 1) + f(n - 2)) % 1000000007;}private int f(int n) {if(n == 0 || n == 1) return n;if (ints[n] != 0){return ints[n];}ints[n] = (f(n - 1) + f(n - 2)) % 1000000007;return (f(n - 1) + f(n - 2)) % 1000000007;}
}

在这里插入图片描述

2.2 滚动数组循环实现

时间复杂度O(n),空间复杂度O(1)
在这里插入图片描述
数组不断滚动向后,逐次累加

class Solution {// 第二种方法:循环实现public int fib(int n) {final int MOD = 1000000007;// 1. 定义辅助数组res,用以记录当前值的前两项值long[] res = {0,1};// 2. 如果n小于2,直接返回if (n < 2){return (int)res[n];} // 3. 定义sum,用于记录从第三项开始,所得到的前两项加和long sum  = 0;for (int i = 2; i <= n; i++){    // 4. sum为前两项加和,然后依次交换元素,逐次相加sum = (res[0] + res[1]) % MOD;res[0] = res[1];res[1] = sum;}return (int)sum;}
}

在这里插入图片描述

2.3 矩阵快速幂 – O(logn)

时间复杂度O(logn),空间复杂度O(1)
在这里插入图片描述
这就涉及到了斐波那契数列的数学公式。

快速幂算法原理: 如需求数据 a 的幂次,此处 a 可以为数也可以为矩阵,常规做法需要对a进行不断的乘积即 a * a * a * …

以求 3^10 的结果为例:
[优化步骤1:]
易知:
3^10=3*3*3*3*3*3*3*3*3*3
=9^5 = 9^4*9
=81^2*9
=6561*9

基于以上原理,我们在计算一个数的多次幂时,可以先判断其幂次的奇偶性,然后:

  • 如果幂次为偶直接 base(底数) 作平方,power(幂次) 除以2

  • 如果幂次为奇则底数平方,幂次整除于2然后再多乘一次底数

[优化步骤2:]

对于以上涉及到 [判断奇偶性] 和 [除以2] 这样的操作。使用系统的位运算比普通运算的效率是高的,因此可以进一步优化:

  • 把 power % 2 == 1 变为 (power & 1) == 1

  • 把 power = power / 2 变为 power = power >> 1

class Solution {static final int MOD = 1000000007;public int fib(int n) {//矩阵快速幂if (n < 2) {return n;}//定义乘积底数int[][] base = {{1, 1}, {1, 0}};//定义幂次int power = n - 1;int[][] ans = calc(base, power);//按照公式,返回的是两行一列矩阵的第一个数return ans[0][0];}//定义函数,求底数为 base 幂次为 power 的结果public int[][] calc(int[][] base, int power) {//定义变量,存储计算结果,此次定义为单位阵int[][] res = {{1, 0}, {0, 1}};//可以一直对幂次进行整除while (power > 0) {//1.若为奇数,需多乘一次 base//2.若power除到1,乘积后得到res//此处使用位运算在于效率高if ((power & 1) == 1) {res = mul(res, base);}//不管幂次是奇还是偶,整除的结果是一样的如 5/2 和 4/2//此处使用位运算在于效率高power = power >> 1;base = mul(base, base);}return res;}//定义函数,求二维矩阵:两矩阵 a, b 的乘积public int[][] mul(int[][] a, int[][] b) {int[][] c = new int[2][2];for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {//矩阵乘积对应关系,自己举例演算一遍便可找到规律c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);}}return c;}
}

在这里插入图片描述

3. 参考资料

[1] 一题解带你走进递归和动态规划算法的大门 – 递归改进代码来源
[2] 斐波那契数列(力扣官方题解)-- (Comment 腌菜读作梦想) – 矩阵快速幂解法来源

相关文章:

【LeetCode】剑指 Offer 10- I. 斐波那契数列 p74 -- Java Version

题目链接&#xff1a; 1. 题目介绍&#xff08;&#xff09; 写一个函数&#xff0c;输入 n &#xff0c;求斐波那契&#xff08;Fibonacci&#xff09;数列的第 n 项&#xff08;即 F(N)&#xff09;。斐波那契数列的定义如下&#xff1a; F(0) 0, F(1) 1F(N) F(N - 1) F…...

论文笔记:DropMessage: Unifying Random Dropping for Graph Neural Networks

&#xff08;AAAI 23 优秀论文&#xff09; 1 intro GNN的一个普遍思路是&#xff0c;每一层卷积层中&#xff0c;从邻居处聚合信息 尽管GNN有显著的进步&#xff0c;但是在大规模图中训练GNN会遇到各种问题&#xff1a; 过拟合 过拟合之后&#xff0c;GNN的泛化能力就被限制…...

木鱼cms系统审计小结

MuYuCMS基于Thinkphp开发的一套轻量级开源内容管理系统,专注为公司企业、个人站长提供快速建站提供解决方案。 ​​ ‍ 环境搭建 我们利用 phpstudy 来搭建环境&#xff0c;选择 Apache2.4.39 MySQL5.7.26 php5.6.9 &#xff0c;同时利用 PhpStorm 来实现对项目的调试 ​…...

软件测试面试-一线大厂必问的测试思维面试题

五、测试思维5.1 打电话功能怎么去测&#xff1f;我们会从几个方面去测试&#xff1a;界面、功能、兼容性、易用性、安全、性能、异常。1&#xff09;界面我们会测试下是否跟界面原型图一致&#xff0c;考虑浏览器不同显示比例&#xff0c;屏幕分辨率。2&#xff09;功能&#…...

企业级分布式应用服务 EDAS

什么是企业级分布式应用服务EDAS企业级分布式应用服务EDAS&#xff08;Enterprise Distributed Application Service&#xff09;是一个应用托管和微服务管理的云原生PaaS平台&#xff0c;提供应用开发、部署、监控、运维等全栈式解决方案&#xff0c;同时支持Spring Cloud和Ap…...

弄懂 Websocket 你得知道的这 3 点

1. WebSocket原理 WebSocket同HTTP一样也是应用层的协议&#xff0c;但是它是一种双向通信协议&#xff0c;是建立在TCP之上的。 WebSocket是一种在单个TCP连接上进行全双工通信的协议。WebSocket API也被W3C定为标准。 WebSocket使得客户端和服务器之间的数据交换变得更加简…...

Appium构架及工作原理

一、appium结构简单来说appium充当一个中间服务器的功能&#xff0c;接收来自我们代码的请求&#xff0c;然后发送到手机上进行执行。二、初步认识appium工作过程1.appium是c/s模式的2.appium是基于webdriver协议添加对移动设备自动化api扩展而成的&#xff0c;所以具有和webdr…...

软件架构中“弹性”的多种含义

在软件架构领域的中文文档、书籍中&#xff0c;经常可以看到“弹性”这个专业术语&#xff0c;但在不同的语境下含义可能会不同。 在英语中&#xff0c;elastic 和 resilient 两个单词都可以翻译为“弹性的”&#xff0c;但是它们在软件架构中代表的含义却完全不同&#xff0c…...

JAVA练习57- 罗马数字转整数、位1的个数

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 一、题目1-罗马数字转整数 1.题目描述 2.思路与代码 2.1 思路 2.2 代码 二、题目2-位1的个数 1.题目描述 2.思路与代码 2.1 思路 2.2 代码 总结 前言 …...

C#把图片放到picturebox上的指定位置,PointToClient与PointToScreen解读

1、C#中如何把图片放到picturebox上的指定位置 构造一个跟picturebox1一样大小的Bitmap&#xff0c; 设置给picturebox1&#xff0c; 然后在上面画图 Bitmap image new Bitmap(picturebox1.Size.Width, picturebox1.Size.Height); Graphics device Graphics.FromImage(imag…...

【论文笔记】Manhattan-SDF==ZJU==CVPR‘2022 Oral

Neural 3D Scene Reconstruction with the Manhattan-world Assumption 本文工作&#xff1a;基于曼哈顿世界假设&#xff0c;重建室内场景三维模型。 1.1 曼哈顿世界假设 参考阅读文献&#xff1a;Structure-SLAM: Low-Drift Monocular SLAM in Indoor EnvironmentsIEEE IR…...

环翠区中小学生编程挑战赛题解中学组T4:免费超市

题目描述 OITV电视台最近开设了名为“免费超市”的真人电视节目,在节目中,抽奖选拔的民间志愿者们将随机匹配进行两两对抗赛。每场比赛上,节目组设置 n n n件商品排成一排供选手挑选,两名选手将交替出手选中并拿走商品,每件商品有着不同的价值 a i a_i a...

关于Oracle树形查询(connect by)的学习笔记

1.查找员工 FORD的上级 Note&#xff1a;在查找时&#xff0c;应当注意树形是倒过来的。&#xff08;自下而上&#xff09;&#xff0c;故此父亲节点是MGR &#xff0c;而儿子节点是EMPNO –PRIOR MGREMPNO也是可以的。 以下两种方式均可以实现查找FORD的上级。 SQL> SQ…...

观看课程领奖品!Imagination中国区技术总监全面解读 IMG DXT GPU

此前&#xff0c;我们发布了一系列关于 IMG DXT GPU 的介绍&#xff0c;为了让更多读者了解其背后的技术及应用方向&#xff0c;我们特别邀请 Imagination 中国区技术总监艾克录制全新在线课程&#xff0c;为大家全面解读IMG DXT GPU。 点击这里&#xff0c;马上注册观看&…...

To_Heart—题解——[SCOI2012]奇怪的游戏

题意 link. 给定一个 nmn\times mnm 的棋盘&#xff0c;每次操作可以选择两个相邻的格子&#xff0c;让这两个各自上的数都 1。问最少多少次操作使得所有格子的数相等。如果永远不行则输出-1。 题解 因为相邻两个格子进行操作&#xff0c;而且是方格&#xff0c;所以很容易…...

Spring Boot Hello World 基于 IDEA 案例详解

一、Spring Boot 是什么 世界上最好的文档来源自官方的《Spring Boot Reference Guide》&#xff0c;是这样介绍的&#xff1a; Spring Boot makes it easy to create stand-alone, production-grade Spring based Applications that you can “just run”...Most Spring Boot…...

基于机器学习的异常检测与分析技术

传统的运维方式在监控、问题发现、告警以及故障处理等各个环节均存在明显不足&#xff0c;需要大量依赖人的经验&#xff0c;在数据采集、异常诊断分析、故障处理的效率等方面有待提高。 本关键技术面对传统运维故障处理效率低、问题定位不准确、人力成本高三大痛点&#xff0…...

pytest进阶之html测试报告

pytest进阶之html测试报告 目录&#xff1a;导读 前言 pytest-html生成报告 安装 生成报告 效果 错误用例截图 添加描述 小结 allure2生成报告 安装allure 安装pytest-allure-adaptor插件 生成xml格式报告 添加环境变量 运行allure生成报告 效果 总结 前言 …...

劳特巴赫仿真测试工具Trace32的基本使用(cmm文件)

劳特巴赫 Trace32 调试使用教程 使用PRACTICE 脚本(.cmm) 在TRACE32 中使用PRACTICE 脚本(*.cmm)将帮助你: 在调试器启动时立即执行命令根据您的项目需求自定义TRACE32PowerView用户界面加载应用程序或符号使调试操作具有可重复性, 并可用于验证目的和回归测试 自动启动脚本…...

盘点四种自动化测试模型实例及优缺点

一&#xff0c;线性测试 1.概念&#xff1a; 通过录制或编写对应应用程序的操作步骤产生的线性脚本。单纯的来模拟用户完整的操作场景。 &#xff08;操作&#xff0c;重复操作&#xff0c;数据&#xff09;都混合在一起。 2.优点&#xff1a; 每个脚本相对独立&#xff0…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

小智AI+MCP

什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析&#xff1a;AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github&#xff1a;https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...