当前位置: 首页 > 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…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...

VSCode 使用CMake 构建 Qt 5 窗口程序

首先,目录结构如下图: 运行效果: cmake -B build cmake --build build 运行: windeployqt.exe F:\testQt5\build\Debug\app.exe main.cpp #include "mainwindow.h"#include <QAppli...