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

剑指offer10-I.斐波那契数列

 学计算机的对这道题肯定不陌生,我记得是学C语言的时候学递归的时候有这道题,于是我就世界用递归写了如下代码:

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

到n=44就算不出了,超时了。就看了一下题解,题解用的是动态规划的方法:

class Solution {public int fib(int n) {if(n<2){return n;}int p=0,q=1;int r =0;for(int i =2;i<=n;i++){r = (p+q) % 1000000007;p = q;q = r;       }return r;}
}

n小于2的话返回自己,然后定义p为n的前两个数,q为n的前一个数,然后r是第n个数的值,所以r就等于p+q,然后把q给p,r给q,最后返回r就可以了。

题解还给出了一种矩阵幂的方法:

 最后只需要求M的n次方就行。

class Solution {static final int MOD = 1000000007;public int fib(int n) {if (n < 2) {return n;}int[][] q = {{1, 1}, {1, 0}};int[][] res = pow(q, n - 1);return res[0][0];}public int[][] pow(int[][] a, int n) {int[][] ret = {{1, 0}, {0, 1}};while (n > 0) {if ((n & 1) == 1) {ret = multiply(ret, a);}n >>= 1;a = multiply(a, a);}return ret;}public int[][] multiply(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;}
}

定义了一个矩阵乘矩阵的multiply方法,求矩阵的n次方的pow方法,通过这两个方法可以求出M的n次方。

相关文章:

剑指offer10-I.斐波那契数列

学计算机的对这道题肯定不陌生&#xff0c;我记得是学C语言的时候学递归的时候有这道题&#xff0c;于是我就世界用递归写了如下代码&#xff1a; class Solution {public int fib(int n) {if(n1) return 1;if(n0) return 0;return (fib(n-1) fib(n-2)) % 1000000007;} } 到…...

13年测试经验,性能测试-压力测试指标分析总结,看这篇就够了...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 一般推荐&#xf…...

大数据课程D3——hadoop的Source

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Source的AVRO Source; ⚪ 掌握Source的Exec Source; ⚪ 掌握Source的Spooling Directory Source; ⚪ 掌握Source的Netcat Source; ⚪ 掌握Source的Sequence Generator Source;…...

F5 LTM 知识点和实验 4-持久化

第四章:持久化 持久化: 大多数应用都是有状态的,比如,使用一个购物网站,最重要的是用户在放入一个商品之后,刷新网页要能继续看到购物车里的东西,这就需要请求报文发到同一个后端服务器上,持久化就能完成这个功能。 持久化支持一下几种场景: 源地址目标地址SSLSIPH…...

SpringBoot之WebMvcConfigurer详解

目录 一、基本介绍 二、WebMvcConfigurer接口展示 三、常用方法列举 3.1 addInterceptors&#xff1a;添加拦截器 3.2 addResourceHandlers&#xff1a;添加静态资源 3.3 addCorsMappings&#xff1a;添加跨域 编写的初衷是为了自己巩固复习&#xff0c;如果能帮到你将是…...

WPF实战学习笔记22-添加自定义询问窗口

添加自定义询问窗口 详细代码&#xff1a;https://github.com/DongLiqiang/Mytodo/commit/221de6b2344d5c861f1d3b2fbb2480e3e3b35c26 添加自定义询问窗口显示方法 修改文件Mytodo.Extensions.DialogExtension 添加内容&#xff0c;类中添加内容 /// <summary> /// …...

Spring Boot项目的创建

hi 大家好,又见面了,今天继续讲解Spring Boot 文章目录 &#x1f436;1.什么是Spring Boot?&#x1f436;2.Spring Boot的优势&#x1f436;3.Spring Boot项目创建&#x1f33c;3.1使用ieda创建&#x1f95d;3.1.1下载插件Spring Boot Helper&#x1f95d;3.1.2创建项目 &…...

Python加载数据的5种方法

大家好&#xff0c;今天回顾五种引入数据的Python技术&#xff0c;并附有代码实例参考。 我们将使用Numpy、Pandas和Pickle包&#xff0c;所以要导入它们&#xff1a; import numpy as np import pandas as pd import pickle Manual功能 这是最困难的&#xff0c;因为你必须…...

QPoint、QLine、QSize、QRect

QPoint、QLine、QSize、QRect QPointQLineQSizeQRect QPoint // 构造函数 // 构造一个坐标原点, 即(0, 0) QPoint::QPoint(); // 参数为 x轴坐标, y轴坐标 QPoint::QPoint(int xpos, int ypos);// 设置x轴坐标 void QPoint::setX(int x); // 设置y轴坐标 void QPoint::setY(in…...

vue+leaflet笔记之地图量测

vueleaflet笔记之地图量测 文章目录 vueleaflet笔记之地图量测开发环境代码简介插件简介与安装使用简介图形量测动态量测 详细源码(Vue3) 本文介绍了Web端使用Leaflet开发库进行距离量测的一种方法 (底图来源:天地图)&#xff0c;结合leaflet-measure-path插件能够快速的实现地…...

“深入理解SpringBoot:从入门到精通的几个关键要点“

标题&#xff1a;深入理解Spring Boot&#xff1a;从入门到精通 摘要&#xff1a;本文将深入探讨Spring Boot的关键要点&#xff0c;帮助读者从入门到精通。我们将从Spring Boot的基本概念开始&#xff0c;介绍自动配置、起步依赖、注解驱动开发等特性&#xff0c;并通过示例代…...

数值线性代数: 共轭梯度法

本文总结线性方程组求解的相关算法&#xff0c;特别是共轭梯度法的原理及流程。 零、预修 0.1 LU分解 设&#xff0c;若对于&#xff0c;均有&#xff0c;则存在下三角矩阵和上三角矩阵&#xff0c;使得。 设&#xff0c;若对于&#xff0c;均有&#xff0c;则存在唯一的下三…...

【JVM】详解对象的创建过程

文章目录 1、创建对像的几种方式1、new关键字2、反射3、clone4、反序列化 2、创建过程步骤 1、检查类是否已经被加载步骤 2、 为对象分配内存空间1、指针碰撞针对指针碰撞线程不安全&#xff0c;有两种方案&#xff1a; 2、空闲列表选择哪种分配方式 步骤3、将内存空间初始化为…...

华纳云:ubuntu下如何搭建nfs服务

在Ubuntu下搭建NFS(Network File System)服务&#xff0c;可以实现网络文件共享。以下是在Ubuntu上搭建NFS服务的步骤&#xff1a; 安装NFS服务器和客户端软件&#xff1a; 打开终端&#xff0c;并使用以下命令安装NFS服务器和客户端软件&#xff1a; sudo apt-get update s…...

HCIA实验二

实验要求&#xff1a; 1.R2为ISP&#xff0c;只能配置IP 2.R1-R2之间为HDLC封装 3.R2-R3之间为PPP封装&#xff0c;pap认证&#xff0c;R2为主认证方 4.R2-R4之间为PPP封装&#xff0c;chap认证&#xff0c;R2为主认证方 5.R1、R2、R3构建MGRE&#xff0c;仅R1的IP地址固定…...

stm32 舵机 cubemx

文章目录 前言一、cubemx配置二、代码1.serve.c2.serve.h3.主函数 总结 前言 stm32对舵机进行控制&#xff0c;很简单直接一个pwm就可以实现 pwm的周期是50HZ占空比分别对应 一个0.5ms的高电平对应于0度 一个1.5ms的高电平对应于90度 一个2.5ms的高电平对应于180度 因此&#…...

无涯教程-jQuery - Spinner组件函数

Widget Spinner 函数可与JqueryUI中的窗口小部件一起使用。Spinner提供了一种从一组中选择一个值的快速方法。 Spinner - 语法 $( "#menu" ).selectmenu(); Spinner - 示例 以下是显示Spinner用法的简单示例- <!doctype html> <html lang"en"…...

Python 有趣的模块之pynupt——通过pynput控制鼠标和键盘

Python 有趣的模块之pynupt ——通过pynput控制鼠标和键盘 文章目录 Python 有趣的模块之pynupt ——通过pynput控制鼠标和键盘1️⃣简介2️⃣鼠标控制与移动3️⃣键盘控制与输入4️⃣结语&#x1f4e2; 1️⃣简介 &#x1f680;&#x1f680;&#x1f680;学会控制鼠标和键盘是…...

docker基于centos7镜像安装python3.7.9

下载centos7镜像 docker pull centos&#xff1a;centos7 启动容器centos-python-3.7 docker run -itd --name centos-python-3.7 -p 60021:22 --privileged centos:centos7 /usr/sbin/init 进入容器 docker exec -it centos-python-3.7 /bin/bash centos7环境下安装python3.7.…...

JavaScript中的switch语句

switch语句和if语句一样&#xff0c;同样是运用于条件循环中&#xff1b; 下面例子我们用switch实现 例如如果今天是周一就学习HTML&#xff0c;周二学习CSS和JavaScript&#xff0c;周三学习vue&#xff0c;周四&#xff0c;周五学习node.js&#xff0c;周六周日快乐玩耍&…...

UCI心脏病数据集实战:用XGBoost构建预测模型的全流程指南(附特征重要性分析)

UCI心脏病数据集实战&#xff1a;用XGBoost构建预测模型的全流程指南&#xff08;附特征重要性分析&#xff09; 医疗数据科学正在重塑现代医学诊断方式。当我在克利夫兰诊所实习期间&#xff0c;亲眼见证了机器学习模型如何辅助医生识别高风险心脏病患者。本文将带您完整复现这…...

嵌入式STM32开发者的Gitee协作指南:如何用.gitignore管好你的Hex和工程文件

嵌入式STM32开发者的Gitee协作指南&#xff1a;如何用.gitignore管好你的Hex和工程文件 在嵌入式开发领域&#xff0c;STM32系列微控制器的项目开发往往伴随着大量中间文件的生成——从Keil MDK编译产生的.hex、.axf&#xff0c;到STM32CubeIDE自动创建的Debug文件夹&#xff0…...

Krita AI Diffusion图像引导适配器功能异常的深度解决方案

Krita AI Diffusion图像引导适配器功能异常的深度解决方案 【免费下载链接】krita-ai-diffusion Streamlined interface for generating images with AI in Krita. Inpaint and outpaint with optional text prompt, no tweaking required. 项目地址: https://gitcode.com/gh…...

从Simulink到实物:单闭环直流调速仿真如何指导真实的Arduino/STM32控制?

从Simulink到Arduino&#xff1a;如何将直流电机控制算法从仿真落地到真实硬件 当你第一次在Simulink中看到那个完美的电机转速响应曲线时&#xff0c;那种成就感是无可替代的。但很快&#xff0c;一个更迫切的问题出现了&#xff1a;这些漂亮的仿真结果&#xff0c;如何变成手…...

5步搞定Qwen3-Embedding-4B向量服务:SGlang部署亲测有效

5步搞定Qwen3-Embedding-4B向量服务&#xff1a;SGlang部署亲测有效 1. Qwen3-Embedding-4B模型简介 1.1 模型核心能力 Qwen3-Embedding-4B是通义实验室推出的新一代文本嵌入模型&#xff0c;专为高效语义编码设计。作为Qwen3系列的一员&#xff0c;它在保持中等参数规模&am…...

PyTorch 2.8镜像效果实测:Wan2.2-I2V图生视频在4090D上的流畅度表现

PyTorch 2.8镜像效果实测&#xff1a;Wan2.2-I2V图生视频在4090D上的流畅度表现 1. 测试环境与配置 1.1 硬件配置 本次测试使用的是基于RTX 4090D显卡的深度学习工作站&#xff0c;具体配置如下&#xff1a; 显卡&#xff1a;NVIDIA RTX 4090D 24GB显存CPU&#xff1a;10核…...

推荐算法闲谈:如何在不同业务场景下理解和拆解核心指标

巧解决的是能不能学好&#xff0c;而指标分析解决的是这次改动是否真正创造了业务价值&#xff0c;以及为什么。一个非常常见、但又极易被忽视的事实是&#xff1a;推荐系统并不存在一套放之四海而皆准的核心业务指标。不同产品形态、不同交互方式、不同公司发展阶段&#xff0…...

ftools架构深度解析:Stata大数据处理的技术革命

ftools架构深度解析&#xff1a;Stata大数据处理的技术革命 【免费下载链接】ftools Fast Stata commands for large datasets 项目地址: https://gitcode.com/gh_mirrors/ft/ftools 在数据科学和经济学研究的实践中&#xff0c;Stata用户经常面临一个共同的挑战&#x…...

工程伦理案例分析:从经典失败项目看责任分配与风险预防

工程伦理案例分析&#xff1a;从经典失败项目看责任分配与风险预防 当一座桥梁在通车典礼上轰然倒塌&#xff0c;当一栋新建大楼在台风中支离破碎&#xff0c;这些触目惊心的工程事故背后&#xff0c;往往隐藏着复杂的伦理困境。工程伦理不是简单的对错判断题&#xff0c;而是需…...

别再死磕英文手册了!手把手带你用Lisflood-FP跑通第一个洪水模拟案例(附T001_buscot实战)

从零到一&#xff1a;Lisflood-FP洪水模拟实战指南&#xff08;T001_buscot案例详解&#xff09; 刚接触水文模型的研究者常被英文手册劝退——密密麻麻的公式、晦涩的术语、复杂的参数配置让人望而生畏。其实&#xff0c;掌握Lisflood-FP的关键不在于死磕理论&#xff0c;而在…...