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

leetcode_动态规划/递归 509. 斐波那契数

509. 斐波那契数

  • 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
    • F(0) = 0,F(1) = 1
    • F(n) = F(n - 1) + F(n - 2),其中 n > 1
  • 给定 n ,请计算 F(n) 。
class Solution(object):def fib(self, n):""":type n: int:rtype: int"""if n < 2:return nf = [0] * (n + 1)f[0] = 0f[1] = 1for n in range(2, n+1):f[n] = f[n-1] + f[n-2]return f[n]
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

空间优化

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""if n < 2:return nprev, curr = 0, 1  # 初始化前两个斐波那契数for _ in range(2, n + 1):prev, curr = curr, prev + curr  # 更新前两个值return curr
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

相关文章:

leetcode_动态规划/递归 509. 斐波那契数

509. 斐波那契数 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1F(n) F(n - 1) F(n - 2)&#xff0c;其中 n …...

对泰坦尼克号沉没事件幸存者数据分析和预测

一、分析目的 探究决定泰坦尼克号沉没事件中什么因素决定着船上人的生死&#xff0c;并对实例进行判别和预测。 二、数据介绍 Titanic.csv数据中包含了891个样本&#xff0c;记录了泰坦尼克号遇难时的891个乘客的基本信息&#xff0c;其中包括以下信息&#xff1a; Passenger…...

算法之排序算法

排序算法 ♥常见排序算法知识体系详解♥ | Java 全栈知识体系 算法 - 排序 | CS-Notes 面试笔记 十大经典排序算法总结 | JavaGuide...

DMA发送全部历史记录数据到串口

背景 博主参与的项目中&#xff0c;有个读取全部历史记录的功能&#xff0c;如果下位机在主程序中将全部历史记录单纯地通过串口传输会比较占用cpu资源&#xff0c;影响主程序中别的功能。最后商量得出以下实现方案&#xff1a; 定义两个发送缓冲区DMATxbuf1和DMATxbuf2&…...

蓝桥杯好题推荐-----高精度减法

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” 题目链接 记录详情 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/record/205122671 思路讲解 这个题目的解题思路&#xff0c;其实是和高精度加法是非常像的。怎么说…...

SpringMVC (3)

目录 1. 传递对象 2. 后端参数重命名&#xff08;后端参数映射&#xff09; 3. 传递数组 4. 传递集合 5. 传递JSON数据 5.1 JSON概念 5.2 JSON语法 5.3 JSON字符串和Java对象互转 5.4 JSON优点 5.5 传递JSON对象 6. 获取URL中参数PathVariable 7. 上传文件RequestP…...

vscode使用豆包MARSCode----集成doubao1.5 DeepSeekR1 DeepseekV3模型的ai编程插件

引入扩展 打开VSCode扩展窗口&#xff0c;在搜索窗口搜索MarsCode&#xff0c;找到MarsCode 插件单击「install」&#xff0c;完成安装&#xff0c;登录即可使用MarsCode 编程助手。 主要功能 主要快捷键 / explain 解释项目代码&#xff0c;AI 返回的内容有结构分类&#…...

Ubuntu 下 nginx-1.24.0 源码分析 - ngx_buf_t

ngx_buf_t 定义在 src/core/ngx_buf.h typedef struct ngx_buf_s ngx_buf_t;struct ngx_buf_s {u_char *pos;u_char *last;off_t file_pos;off_t file_last;u_char *start; /* start of buffer */u_char …...

分布式开源协调服务之zookeeper

Zookeeper简介 Zookeeper是什么&#xff1f; Zookeeper官网中对Zookeeper的定义还是比较明确的&#xff1a; ZooKeeper is a centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services…...

ubuntu系统安装playhouse三方库

ubuntu系统python3.10安装playhouse三方库 问题描述 问题描述 虚拟环境中使用pip install playhouse&#xff0c;返回安装成功 用pip list查看&#xff0c;能看到playhouse及版本号 导包时提示没有找到playhouse我那件目录&#xff0c;能发现 检查site-package发现问题&#x…...

【星云 Orbit-F4 开发板】04.一触即发:GPIO 外部中断

【星云 Orbit-F4 开发板】04. 一触即发&#xff1a;外部中断控制 摘要 本文详细介绍了如何使用STM32F407微控制器的HAL库实现外部中断功能。通过配置GPIO引脚作为外部中断源&#xff0c;并在中断回调函数中处理按键事件&#xff0c;实现了按键控制LED状态翻转的功能。本文旨在…...

笔记二:整数和浮点数在内存中存储

目录 一、数据类型介绍 二、类型的基本归类 1.整形家族&#xff1a; 2.浮点数家族&#xff1a; 3.构造类型&#xff1a; 4.指针类型 5.空类型&#xff1a; 三、整形在内存中的存储 3.1 原码&#xff0c;反码、补码 3.2 大小端介绍 四、浮点数在内存中的存储 ​编辑 4.…...

PyQT(PySide)的上下文菜单策略设置setContextMenuPolicy()

在 Qt 中&#xff0c;QWidget 类提供了几种不同的上下文菜单策略&#xff0c;这些策略通过 Qt::ContextMenuPolicy 枚举类型来定义&#xff0c;用于控制控件&#xff08;如按钮、文本框等&#xff09;在用户右键点击时如何显示上下文菜单。 以下是 Qt::ContextMenuPolicy 枚举中…...

BladeX框架接口请求跨域

前端使用代理请求接口&#xff0c;接口可以正常访问。如果换全路径请求就跨域。 除了后端要配置跨域 还需要修改配置文件对OPTIONS请求的限制...

如何在Apple不再支持的MacOS上安装Homebrew

手头有一台2012年产的Macbook Pro&#xff0c;系统版本停留在了10.15.7&#xff08;2020年9月24日发布的&#xff09;。MacOS 11及后续的版本都无法安装到这台老旧的电脑上。想通过pkg安装Homebrew&#xff0c;发现Homebrew releases里最新的pkg安装包不支持MacOS 10.15.7&…...

本地大模型编程实战(26)用langgraph实现基于SQL数据构建的问答系统(5)

本文将将扩展上一篇文章完成的 langgraph 链&#xff0c;继续使用基于 langgraph 链 &#xff0c;对结构化数据库 SQlite 进行查询的方法。该系统建立以后&#xff0c;我们不需要掌握专业的 SQL 技能&#xff0c;可以用自然语言询问有关数据库中数据的问题并返回答案。主要完善…...

数据结构与算法:滑动窗口

前言 滑动窗口一般主要用于解决子数组或子串问题&#xff0c;这类的题目更看重对题目的分析和转化。 一、原理 在整个数组上&#xff0c;用l和r分别控制窗口的左右边界&#xff0c;r就扩大&#xff0c;l就减小。 当窗口的范围和题目中某个指标间存在单调关系时&#xff0c;…...

江协科技/江科大-51单片机入门教程——P[2-1] 点亮一个LED

本节将向大家介绍如何用 51 单片机去控制开发板上的 LED。开发板上的 LED 位置标注有 “LED 模块”。 第二章要写 3 个程序代码&#xff1a;第一个代码实现点亮开发板上的第一个 LED&#xff1b;第二个代码让第一个 LED 以 1 秒为周期闪烁&#xff1b;第三个代码使 8 个 LED 以…...

leetcode hot 100 41. 缺失的第一个正数

代码 测试用例 测试用例 测试结果 41. 缺失的第一个正数 已解答 困难 相关标签 相关企业 提示 给你一个未排序的整数数组 nums &#xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1&#xf…...

UniApp 使用 u-loadmore 完整步骤

文章目录 一、前期准备1. 安装 uView - UI 二、使用 u-loadmore组件1. 创建页面2. 编写页面代码模板部分&#xff08;loadmore-demo.vue&#xff09;样式部分脚本部分 三、要点补充1. u-loadmore 状态说明2. 数据请求优化3. 性能优化4. 兼容性问题 在 UniApp 开发中&#xff0c…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...