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

LeetCode题:70爬楼梯,126斐波那契数

目录

70:爬楼梯

题目要求:

解题思路:(类似斐波那契数)

递归解法:

非递归解法:

126:斐波那契数

题目要求:

解题思路:

递归解法:

非递归解法:

都看到这了,点个赞再走呗,谢谢谢谢谢!!!


70:爬楼梯

题目要求:

解题思路:(类似斐波那契数)

递归解法:

由题可知,每次可以爬1个或者2个台阶,假如有n个台阶,会有多少种走法?那么我们就想,第一次爬一个台阶,那方法数就是爬这一次台阶加上剩下n-1个台阶的走法,爬两个台阶,那方法数就是爬完这两个台阶再加上剩下n-2个台阶的走法,很容易就想到递归的解法了,而使用递归我们要找到终止条件,也要写出递归公式

但是这么递归的时间复杂度很高,LeetCode上通过不了,会有很多重复计算的斐波那契数,我们可以用HashMap来解题,每次往下找之前都记录一下map里面有没有n这个斐波那契数,有就不用继续往下找了,直接返回这个斐波那契数,没有就继续往下找,有了HashMap的引用,我们时间复杂度就变成了O(N),在LeetCode上也就能通过了。

递归公式如下:

代码如下:

class Solution {HashMap<Integer, Integer> hashmap = new HashMap<>();public int climbStairs(int n) {if(n == 1) {return 1;}if(n == 2) {return 2;}//每次递归都判断map有没有n个台阶爬楼梯方法数,没有算出当前n阶台阶的方法数,放进map里,放进map里后就不用继续往下递归了,直接返回这个方法数,因为hashmap已经存了n阶台阶的方法数了;有就不用继续递归了,直接返回n台阶的方法数if(hashmap.get(n) != null) {return hashmap.get(n);} else {int result = climbStairs(n - 1) + climbStairs(n - 2);hashmap.put(n, result);return result;}}
}

非递归解法:

从此图我们可以看出,要求n的斐波那契数,必须求前一个和前两个的斐波那契数,也就是上图的公式,非递归的解法,我们就用循环来解决,从下至上来求n的斐波那契数,我们定义一个pre和prePre变量来记录前一个和前两个的斐波那契数,result来记录n的斐波那契数每循环一次都要更改pre和prePre的下标,时间复杂度为O(N).

代码如下:

 public int climbStairs(int n) {//非递归思想if(n == 1) {return 1;}if(n == 2) {return 2;}int result = 0;int pre = 2;int prePre = 1;for(int flg = 3; flg <= n; flg++) {result = pre + prePre;//pre和prePre都要往前推prePre = pre;pre = result;}return result;}

126:斐波那契数

题目要求:

解题思路:

        这题和爬楼梯思路一样,解法也一样,递归和非递归也一样,不过他的递归公式和结束条件和爬楼梯不一样,公式如下图:

递归思路:因为递归会重复计算很多次,所以我们可以用一个HashMap来记录n的斐波那契数每递归一次都判断map里面有没有n的斐波那契数,有就不用继续往下递归了,直接返回这个斐波那契数没有就往下递归,把1后面的斐波那契数列都记录在map中,这样时间复杂度就是O(N)了,LeetCode也能通过。

非递归思路:用循环,从下至上,求得每个斐波那契数我们定义result放n的斐波那契数,pre放n的前一个斐波那契数,prePre放n的前两个斐波那契数每循环一次都要更新一次pre和prePre的下标,往上走。

递归解法:

代码如下:

 Map<Integer, Integer> map = new HashMap<>();public int fib(int n) {if(n == 0 || n == 1) {return n;}if(map.containsKey(n)) {return map.get(n);}//n的斐波那契数不在map里int result = (fib(n - 1) + fib(n - 2)) % 1000000007;//int result = (fib(n - 1) + fib(n - 2));map.put(n, result);return result;}

非递归解法:

 public int fib(int n) {//非递归if(n == 0 || n == 1) {return n;}int result = 0;int pre = 1;int prePre = 0;for(int i = 2; i <= n; i++) {result = (pre + prePre) % 1000000007;prePre = pre;pre = result;}return result;}

都看到这了,点个赞再走呗,谢谢谢谢谢!!!

相关文章:

LeetCode题:70爬楼梯,126斐波那契数

目录 70&#xff1a;爬楼梯 题目要求&#xff1a; 解题思路&#xff1a;&#xff08;类似斐波那契数&#xff09; 递归解法&#xff1a; 非递归解法&#xff1a; 126&#xff1a;斐波那契数 题目要求&#xff1a; 解题思路&#xff1a; 递归解法&#xff1a; 非递归解…...

VTK OrientationMarker 方向 三维坐标系 相机坐标轴 自定义坐标轴

本文 以 Python 语言开发 我们在做三维软件开发时&#xff0c;经常会用到相机坐标轴&#xff0c;来指示当前空间位置&#xff1b; 坐标轴效果&#xff1a; 相机方向坐标轴 Cube 正方体坐标轴 自定义坐标轴&#xff1a; Code&#xff1a; Axes def main():colors vtkNamedC…...

工控安全与网络安全有什么不同?

在当代&#xff0c;全球制造业正在经历一场前所未有的技术变革。工业4.0不仅代表着自动化和数据交换的进步&#xff0c;它还揭示了工业自动化、智能制造与系统集成的融合。这种集成为企业带来了效率和质量的双重提升&#xff0c;但同时也暴露出新的安全隐患。工控系统成为了这一…...

性能测试工具:Jmeter介绍

JMeter是一个开源的Java应用程序&#xff0c;由Apache软件基金会开发和维护&#xff0c;可用于性能测试、压力测试、接口测试等。 1. 原理 JMeter的基本原理是模拟多用户并发访问应用程序&#xff0c;通过发送HTTP请求或其他协议请求&#xff0c;并测量响应时间、吞吐量、并发…...

Golang Struct 继承的深入讨论和细节

1&#xff09;结构体可以使用嵌套匿名结构体所有的字段和方法&#xff0c;即&#xff1a;首字母大写或者小写的字段、方法&#xff0c;都可以使用。 type A struct {Name stringage int }func (a *A) SayName() {fmt.Println("A say name", a.Name) }func (a *A) s…...

Android11分区介绍

1.分区汇总 3566及3568分区对应如下: rockdev/Image-rk3566_rgo/ ├── boot.img ├── dtbo.img ├── MiniLoaderAll.bin ├── misc.img ├── parameter.txt ├── recovery.img ├── super.img ├── uboot.img └── vbmeta.img 2.分区说明 分区 说明 boo…...

goland无法调试问题解决

goland 无法调试问题解决 golang 版本升级后&#xff0c;goland 无法进行调试了 首先请看自己下载的版本是否有误 1.apple系 M系列芯片的 arm64版本 2.apple系 intel系列芯片的x86_64 3.windows系 intel解决如下&#xff1a; 查看gopath ericsanchezErics-Mac-mini gww-api…...

关于近期IP-Guard新版本客户端重复发送邮件的问题处理说明

关于近期新版本客户端重复发送邮件的问题处理说明 一、问题描述 近期部分客户反馈,升级到新版本的客户端(4.81.341.0、4.82.621.0及以上),使用SMTP协议发送邮件时,会出现重复发送邮件的情况,主要表现为以下两种现象: Outlook发送包含大量收件人的邮件时,收件人邮箱可能…...

linux java 启动脚本

#!/bin/sh## java env #export JAVA_HOME/data/jdk1.8.0_121 #export JRE_HOME$JAVA_HOME/jre## service name #当前目录 SERVICE_DIR$(cd dirname $0; pwd) echo "$SERVICE_DIR" #jar包路径 JAR_DIRls -ltr $SERVICE_DIR/*.jar| tail -1 echo "JAR_DIR $JAR_DI…...

Node.js 的 CommonJS ECMAScript 标准用法

目录 一、前言二、CommonJS 标准使用方法 三、ECMAScript 标准使用方法 四、常用命令总结 一、前言 本文主要是介绍 Node.js 的 CommonJS & ECMAScript 标准用法 如果对你有帮助&#xff0c;欢迎三连 收藏点赞关注&#xff01;&#xff01;&#xff01; ---- NickYoung 二、…...

Mysql数据库 4.SQL语言 DQL数据查询语言 查询

DQL数据查询语言 从数据表中提取满足特定条件的记录 1.单表查询 2.多表查询 查询基础语法 select 关键字后指定要查询到的记录的哪些列 语法&#xff1a;select 列名&#xff08;字段名&#xff09;/某几列/全部列 from 表名 [具体条件]&#xff1b; select colnumName…...

俄罗斯黑客利用Roundcube零日漏洞窃取政府电子邮件

导语&#xff1a;最近&#xff0c;一起涉及Roundcube Webmail的零日漏洞被俄罗斯黑客组织Winter Vivern利用&#xff0c;攻击了欧洲政府机构和智库。这一漏洞已经存在至少一个月&#xff0c;直到10月16日&#xff0c;Roundcube开发团队才发布了安全补丁来修复这个Stored Cross-…...

【Javascript】ajax(阿甲克斯)

目录 什么是ajax? 同步与异步 原理 注意 写一个ajax请求 创建ajax对象 设置请求方式和地址 发送请求 设置响应HTTP请求状态变化的函数 什么是ajax? 是基于javascript的一种用于创建快速动态网页的技术&#xff0c;是一种在无需重新加载整个网页的情况下&#xff0c…...

Spring MVC的常用注解

目录 RequestMapping 例子&#xff1a; RequestMapping 支持什么类型的请求 使 RequestMapping 只支持特定的类型 RestController 通过 HTTP 请求传递参数给后端 1.传递单个参数 注意使⽤基本类型来接收参数的情况 2.传递多个参数 3.传递对象 4.RequestParam 后端参数…...

vim 使用文档笔记

1. i&#xff1a;进入编辑模式 2. ESC&#xff1a;进入一般命令模式 3. h 或 ←&#xff1a;光标向左移动一个字符 4. j 或 ↓&#xff1a;光标向下移动一个字符 5. k 或 ↑&#xff1a;光标向上移动一个字符 6. l 或 →&#xff1a;光标向右移动一个字符 7. num&#xf…...

274. H 指数

文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析1.1 方案一1.2 方案二 2、时间复杂度3、代码详解3.1 方案一3.2 方案二 三、本题小知识 一、题目 1、题目描述 给你一个整数数组 citations &#xff0c;其中 citations[i] 表示研究者的第 i 篇论…...

0基础学习PyFlink——用户自定义函数之UDTAF

大纲 UDTAFTableAggregateFunction的实现累加器定义创建累加 返回类型计算 完整代码 在前面几篇文章中&#xff0c;我们分别介绍了UDF、UDTF和UDAF这三种用户自定义函数。本节我们将介绍最后一种函数&#xff1a;UDTAF——用户自定义表值聚合函数。 UDTAF UDTAF函数即具备了…...

SQLi靶场

SQLi靶场 less1- less2 &#xff08;详细讲解&#xff09; less 1 Error Based-String (字符类型注入) 思路分析 判断是否存在SQL注入 已知参数名为id&#xff0c;输入数值和‘ 单引号‘’ 双引号来判断&#xff0c;它是数值类型还是字符类型 首先输入 1 &#xff0c; 发现…...

重庆开放大学学子们的好帮手

作为一名电大学员&#xff0c;我有幸目睹了一个令人惊叹的学习工具的诞生——电大搜题微信公众号。这个创新应用为重庆开放大学&#xff08;广播电视大学&#xff09;的学子们提供了便捷、高效的学习资源&#xff0c;成为他们的得力助手。 重庆开放大学是一所为全日制在职人员提…...

机器学习-学习率:从理论到实战,探索学习率的调整策略

目录 一、引言二、学习率基础定义与解释学习率与梯度下降学习率对模型性能的影响 三、学习率调整策略常量学习率时间衰减自适应学习率AdaGradRMSpropAdam 四、学习率的代码实战环境设置数据和模型常量学习率时间衰减Adam优化器 五、学习率的最佳实践学习率范围测试循环学习率&a…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

UE5 音效系统

一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类&#xff0c;将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix&#xff0c;将上述三个类翻入其中&#xff0c;通过它管理每个音乐…...

AWS vs 阿里云:功能、服务与性能对比指南

在云计算领域&#xff0c;Amazon Web Services (AWS) 和阿里云 (Alibaba Cloud) 是全球领先的提供商&#xff0c;各自在功能范围、服务生态系统、性能表现和适用场景上具有独特优势。基于提供的引用[1]-[5]&#xff0c;我将从功能、服务和性能三个方面进行结构化对比分析&#…...

Linux 中替换文件中的某个字符串

如果你想在 Linux 中替换文件中的某个字符串&#xff0c;可以使用以下命令&#xff1a; 1. 基本替换&#xff08;sed 命令&#xff09; sed -i s/原字符串/新字符串/g 文件名示例&#xff1a;将 file.txt 中所有的 old_text 替换成 new_text sed -i s/old_text/new_text/g fi…...

【RabbitMQ】- Channel和Delivery Tag机制

在 RabbitMQ 的消费者代码中&#xff0c;Channel 和 tag 参数的存在是为了实现消息确认机制&#xff08;Acknowledgment&#xff09;和精细化的消息控制。 Channel 参数 作用 Channel 是 AMQP 协议的核心操作接口&#xff0c;通过它可以直接与 RabbitMQ 交互&#xff1a; 手…...