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

RAGFlow与Dify共存方案:同一台Win11机器如何用Docker隔离部署

RAGFlow与Dify共存方案&#xff1a;同一台Win11机器如何用Docker隔离部署 在AI应用开发领域&#xff0c;RAGFlow和Dify作为两款热门工具&#xff0c;分别擅长知识库构建和AI应用编排。许多开发者面临一个现实挑战&#xff1a;如何在本地开发环境中同时运行这两个系统&#xff1…...

企业级离线OCR深度解析:5大策略实现高性能文字识别

企业级离线OCR深度解析&#xff1a;5大策略实现高性能文字识别 【免费下载链接】Umi-OCR OCR software, free and offline. 开源、免费的离线OCR软件。支持截屏/批量导入图片&#xff0c;PDF文档识别&#xff0c;排除水印/页眉页脚&#xff0c;扫描/生成二维码。内置多国语言库…...

vue3 diff算法中的-双端 Diff + 最长递增子序列 讲解

一句话总结 Vue3 Diff 双端比较&#xff08;快速复用&#xff09; 最长递增子序列&#xff08;最小移动 DOM&#xff09; 目的&#xff1a;在乱序节点中&#xff0c;只移动最少 DOM&#xff0c;实现最高效更新。1. 先搞懂&#xff1a;Vue3 对比 Vue2 差在哪&#xff1f; Vue2…...

构建企业级AI智能体:LangGraph多智能体框架实战指南

构建企业级AI智能体&#xff1a;LangGraph多智能体框架实战指南 【免费下载链接】langgraph Build resilient language agents as graphs. 项目地址: https://gitcode.com/GitHub_Trending/la/langgraph 在当今AI应用开发中&#xff0c;开发者面临着一个核心挑战&#x…...

芯片缺货潮下的应对策略与国产替代方案

1. 芯片缺货潮下的行业现状最近我的一个产品项目中&#xff0c;原本采购价仅5元的ST品牌MCU&#xff08;微控制器&#xff09;价格飙升至70元&#xff0c;涨幅高达14倍。这个案例并非个例&#xff0c;而是当前全球半导体行业供应链危机的缩影。作为从业十余年的硬件工程师&…...

突破百度网盘下载限速:BaiduPCS-Go命令行客户端的3大技术突破

突破百度网盘下载限速&#xff1a;BaiduPCS-Go命令行客户端的3大技术突破 【免费下载链接】BaiduPCS-Go iikira/BaiduPCS-Go原版基础上集成了分享链接/秒传链接转存功能 项目地址: https://gitcode.com/GitHub_Trending/ba/BaiduPCS-Go 你是否厌倦了百度网盘的龟速下载&…...

STM32移植LVGL图形库实战指南

1. LVGL图形库概述与STM32移植价值LittlevGL&#xff08;简称LVGL&#xff09;作为当前最受欢迎的嵌入式开源图形库之一&#xff0c;其设计哲学完美契合了资源受限的嵌入式环境。我在多个STM32项目中采用LVGL后发现&#xff0c;相比传统GUI方案&#xff0c;它具有三个显著优势&…...

Qwen3-14B镜像实操:自定义Tokenizer适配垂直领域专业术语

Qwen3-14B镜像实操&#xff1a;自定义Tokenizer适配垂直领域专业术语 1. 镜像概述与核心优势 Qwen3-14B私有部署镜像是专为RTX 4090D 24GB显存环境优化的完整解决方案&#xff0c;开箱即用无需复杂配置。这个镜像最显著的特点是针对垂直领域专业术语进行了Tokenizer的深度优化…...

大厂高薪抢手!文科生如何抓住AI时代机遇,实现职业逆袭?

大厂纷纷高薪招聘文科生&#xff0c;引发社会关注。文科生凭借沟通、叙事、逻辑等优势&#xff0c;在大模型理解人类价值观、企业品牌宣传等方面发挥作用。高校也调整专业设置&#xff0c;培养跨学科人才。文章建议文科生根据自身专业&#xff0c;向文案策划、品牌宣传、法务、…...

SpringBoot + MyBatis-Plus项目实战:从零搭建一个JavaEE课程设计骨架(附完整源码结构解析)

SpringBoot MyBatis-Plus项目实战&#xff1a;从零搭建一个JavaEE课程设计骨架&#xff08;附完整源码结构解析&#xff09; 当你第一次打开IDE准备开始JavaEE课程设计时&#xff0c;面对空白的项目窗口是否感到无从下手&#xff1f;本文将带你从零开始&#xff0c;用SpringBo…...