当前位置: 首页 > 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;周六周日快乐玩耍&…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

工厂方法模式和抽象工厂方法模式的battle

1.案例直接上手 在这个案例里面&#xff0c;我们会实现这个普通的工厂方法&#xff0c;并且对比这个普通工厂方法和我们直接创建对象的差别在哪里&#xff0c;为什么需要一个工厂&#xff1a; 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类&#xff1a; 两个发…...