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

算法leetcode|70. 爬楼梯(rust重拳出击)


文章目录

  • 70. 爬楼梯:
    • 样例 1:
    • 样例 2:
    • 提示:
  • 分析:
  • 题解:
    • rust:
    • go:
    • c++:
    • python:
    • java:


70. 爬楼梯:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

样例 1:

输入:n = 2输出:2解释:有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶

样例 2:

输入:n = 3输出:3解释:有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶

提示:

  • 1 <= n <= 45

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • 可以爬一阶或者两阶台阶,那也就是说,除了初始位置,和第一阶台阶,到达其他阶台阶 n 的方式,就只能从 n - 1 阶台阶,或者 n - 2 阶台阶来。
  • 这是典型的动态规划,到初始位置和第一阶台阶的方式只有一种,之后到达每一阶台阶的发方法总数都可以动态计算得来,即 f(x) = f(x − 1) + f(x − 2)
  • 动态规划方法我觉得很好了,但是由于有规律,用数学的方式计算,当然更快了,另外将前几项列出来,再结合定义,就会发现,到达每一阶台阶的方法总数恰好就是 斐波那契数列
  • 动态规划只能从 1n 按顺序推算,在 n 较大时,效率仍不令人满意,矩阵快速幂,可以有像二分查找一样的效率,数学的知识都还给老师了,有兴趣的可以去研究一下,能看明白,但是过段时间又会忘记,无奈啊,矩阵快速幂矩阵乘法快速幂 的结合,可以先分别了解,再结合理解。
  • 所以建议一定要把动态规划优先掌握,其次是快速幂,至于通项公式,数学的方法,很难举一反三,要具体问题具体分析,说到底还是需要掌握数学知识本身,与君共勉。
  • 最后,爬楼梯当然要5阶5阶的上才霸气。

题解:

rust:

impl Solution {pub fn climb_stairs(n: i32) -> i32 {let sqrt5 = 5f64.sqrt();let fibn = ((1f64 + sqrt5) / 2f64).powi(n + 1) - ((1f64 - sqrt5) / 2f64).powi(n + 1);return (fibn / sqrt5).round() as i32;}
}

go:

func climbStairs(n int) int {sqrt5 := math.Sqrt(5)pow1 := math.Pow((1+sqrt5)/2, float64(n+1))pow2 := math.Pow((1-sqrt5)/2, float64(n+1))return int(math.Round((pow1 - pow2) / sqrt5))
}

c++:

class Solution {
public:int climbStairs(int n) {const double sqrt5 = sqrt(5);const double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);return (int) round(fibn / sqrt5);}
};

python:

class Solution:def climbStairs(self, n: int) -> int:sqrt5 = math.sqrt(5)fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1)return round(fibn / sqrt5)

java:

class Solution {public int climbStairs(int n) {final double sqrt5 = Math.sqrt(5);final double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);return (int) Math.round(fibn / sqrt5);}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~


相关文章:

算法leetcode|70. 爬楼梯(rust重拳出击)

文章目录 70. 爬楼梯&#xff1a;样例 1&#xff1a;样例 2&#xff1a;提示&#xff1a; 分析&#xff1a;题解&#xff1a;rust&#xff1a;go&#xff1a;c&#xff1a;python&#xff1a;java&#xff1a; 70. 爬楼梯&#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼…...

基于epoll的TCP服务器端(C++)

网络编程——C实现socket通信(TCP)高并发之epoll模式_tcp通信c 多客户端epoll_n大橘为重n的博客-CSDN博客 网络编程——C实现socket通信(TCP)高并发之select模式_n大橘为重n的博客-CSDN博客 server.cpp #include <stdio.h> #include <sys/types.h> #include <…...

实时安全分析监控加强网络安全

网络犯罪分子只需几分钟&#xff0c;有时甚至几秒钟即可泄露敏感数据。但是&#xff0c;IT 团队可能无法在数周内发现这些违规行为。通常&#xff0c;这些违规行为是由外部方或客户发现的&#xff0c;到那时为时已晚。随着网络漏洞的激增&#xff0c;对安全分析的需求空前高涨。…...

基于ipad协议的gewe框架进行微信群组管理(二)

友情链接 geweapi.com 点击访问即可。 获取群组详情 小提示&#xff1a; 该接口可以一次查询20个群组查询出来的信息是不带公告的 请求URL&#xff1a; http://域名地址/api/group/detail 请求方式&#xff1a; POST 请求头&#xff1a; Content-Type&#xff1a;applica…...

大数据-玩转数据-Flink网页埋点PV统计

一、说明 衡量网站流量一个最简单的指标&#xff0c;就是网站的页面浏览量&#xff08;Page View&#xff0c;PV&#xff09;。用户每次打开一个页面便记录1次PV&#xff0c;多次打开同一页面则浏览量累计。 一般来说&#xff0c;PV与来访者的数量成正比&#xff0c;但是PV并不…...

什么是伪类选择器?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 伪类选择器⭐ 一些常见的伪类选择器示例&#xff1a;:hover:active:focus:nth-child(n):first-child 和 :last-child ⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何…...

PLY模型格式详解【3D】

本文介绍PLY 多边形文件格式&#xff0c;这是一种用于存储被描述为多边形集合的图形对象。 PLY文件格式的目标是提供一种简单且易于实现但通用的格式足以适用于各种模型。 PLY有两种子格式&#xff1a;易于入门的 ASCII 表示形式和用于紧凑存储和快速保存和加载的二进制格式。 …...

Java的反射机制、Lambda表达式和枚举

Java的反射机制、Lambda表达式和枚举 文章目录 Java的反射机制、Lambda表达式和枚举1.反射机制反射的概念、用途、优缺点反射相关的类及使用&#xff08;重要&#xff01;&#xff01;&#xff09;相关类Class类&#xff1a;代表类实体&#xff0c;表示类和接口Field类&#xf…...

数据结构:堆的实现

1.堆的概念 如果有一个关键码的集合 K { k1 &#xff0c;k2 &#xff0c;k3 &#xff0c;…&#xff0c;kn }&#xff0c;把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中&#xff0c;并且 k(i) < k(i*21) 和 k(i) < k(i*22)&#xff0c; i 0 &#xff…...

zabbix-6.4 监控 MySQL

目录 1、rpm安装zabbix_agentd服务 2、编写zabbix_agentd.conf文件 3、编写模板文件 4、创建mysql用户并赋权限 5、创建.my.cnf文件 6、将规则添加到SELinux策略中 注意&#xff1a; 若模板无法读取.my.cnf 信息&#xff0c;从而导致监控报错&#xff0c;可以尝试修改模…...

深入探索:解读创意的力量——idea的下载、初步使用

目录 ​编辑 1.IDEA的简介 2.IDEA的下载 2.1下载路径https://www.jetbrains.com/zh-cn/idea/download/?sectionwindows​编辑​ 2.2下载的步骤 3 idea的初步使用 3.1新建一个简单的Java项目 3.1.1首先需要创建一个新的工程 3.1.2创建一个新的项目&#xff08;模块&am…...

Redis详解

Redis 简介 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的高性能键值对存储数据库&#xff0c;最初由 Salvatore Sanfilippo 开发&#xff0c;它在内存中存储数据&#xff0c;并提供了持久化功能&#xff0c;可以将数据保存到磁盘中&#xff0c;是一种N…...

【Linux】高级IO

目录 IO的基本概念 钓鱼五人组 五种IO模型 高级IO重要概念 同步通信 VS 异步通信 阻塞 VS 非阻塞 其他高级IO 阻塞IO 非阻塞IO IO的基本概念 什么是IO&#xff1f; I/O&#xff08;input/output&#xff09;也就是输入和输出&#xff0c;在著名的冯诺依曼体系结构当中…...

动态HTTP代理与竞争情报收集的关联

Hey&#xff0c;各位爬友们&#xff01;作为一名专业的爬虫HTTP代理提供者&#xff0c;今天我要和大家聊一聊动态HTTP代理与竞争情报收集之间的关联。在这篇文章中&#xff0c;我将向大家解释怎么使用动态HTTP代理完成在竞争中的情报收集&#xff0c;并分享一些实用的技巧。 首…...

kafka基本概念及操作

kafka介绍 Kafka是最初由Linkedin公司开发&#xff0c;是一个分布式、支持分区的&#xff08;partition&#xff09;、多副本的 &#xff08;replica&#xff09;&#xff0c;基于zookeeper协调的分布式消息系统&#xff0c;它的最大的特性就是可以实时的处理大量数据以满足各…...

分享个试卷去笔迹什么软件,几个步骤轻松擦除

试卷擦去笔迹是一项非常关键的技能&#xff0c;它可以帮助你更好地管理你的笔记和文件。不管是小伙伴们想重新测试试卷或者是将试卷输出为电子版&#xff0c;都可以实现的。在这篇文章中&#xff0c;我将分享一些方法和软件&#xff0c;帮助你更好地进行试卷擦除。有需要的小伙…...

ClickHouse(十八):Clickhouse Integration系列表引擎

进入正文前&#xff0c;感谢宝子们订阅专题、点赞、评论、收藏&#xff01;关注IT贫道&#xff0c;获取高质量博客内容&#xff01; &#x1f3e1;个人主页&#xff1a;含各种IT体系技术&#xff0c;IT贫道_Apache Doris,大数据OLAP体系技术栈,Kerberos安全认证-CSDN博客 &…...

日常BUG——代码提交到了本地但是没有push,删除了本地分支如何恢复

&#x1f61c;作 者&#xff1a;是江迪呀✒️本文关键词&#xff1a;日常BUG、BUG、问题分析☀️每日 一言 &#xff1a;存在错误说明你在进步&#xff01; 一、问题描述 代码在本地提交了&#xff0c;但是没有push到远程&#xff0c;然后删除了本地的分支。想要恢…...

Markdown语法

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 Markdown语法目录 前言1.标题2.文本样式3.列表四.图片5.链接6.目录7.代码片7.表格8.注脚9.注释10.自定义列表11.LaTeX数学公式12.插入甘特图13.插入UML图14.插入Merimaid流程…...

vue3表格,编辑案例

index.vue <script setup> import { onMounted, ref } from "vue"; import Edit from "./components/Edit.vue"; import axios from "axios";// TODO: 列表渲染 const list ref([]); const getList async () > {const res await ax…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...