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:爬楼梯 题目要求: 解题思路:(类似斐波那契数) 递归解法: 非递归解法: 126:斐波那契数 题目要求: 解题思路: 递归解法: 非递归解…...

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

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

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

Golang Struct 继承的深入讨论和细节
1)结构体可以使用嵌套匿名结构体所有的字段和方法,即:首字母大写或者小写的字段、方法,都可以使用。 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 版本升级后,goland 无法进行调试了 首先请看自己下载的版本是否有误 1.apple系 M系列芯片的 arm64版本 2.apple系 intel系列芯片的x86_64 3.windows系 intel解决如下: 查看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 标准用法 如果对你有帮助,欢迎三连 收藏点赞关注!!! ---- NickYoung 二、…...

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

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

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

Spring MVC的常用注解
目录 RequestMapping 例子: RequestMapping 支持什么类型的请求 使 RequestMapping 只支持特定的类型 RestController 通过 HTTP 请求传递参数给后端 1.传递单个参数 注意使⽤基本类型来接收参数的情况 2.传递多个参数 3.传递对象 4.RequestParam 后端参数…...
vim 使用文档笔记
1. i:进入编辑模式 2. ESC:进入一般命令模式 3. h 或 ←:光标向左移动一个字符 4. j 或 ↓:光标向下移动一个字符 5. k 或 ↑:光标向上移动一个字符 6. l 或 →:光标向右移动一个字符 7. num…...
274. H 指数
文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析1.1 方案一1.2 方案二 2、时间复杂度3、代码详解3.1 方案一3.2 方案二 三、本题小知识 一、题目 1、题目描述 给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论…...

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

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

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

机器学习-学习率:从理论到实战,探索学习率的调整策略
目录 一、引言二、学习率基础定义与解释学习率与梯度下降学习率对模型性能的影响 三、学习率调整策略常量学习率时间衰减自适应学习率AdaGradRMSpropAdam 四、学习率的代码实战环境设置数据和模型常量学习率时间衰减Adam优化器 五、学习率的最佳实践学习率范围测试循环学习率&a…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...