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

leetcode hot100【LeetCode 70. 爬楼梯】java实现

LeetCode 70. 爬楼梯

题目描述

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

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

注意: 给定 n 是一个正整数。

示例 1:

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

示例 2:

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

Java 实现代码

方法:迭代
class Solution {public int climbStairs(int n) {if (n <= 2) {return n;}int first = 1, second = 2;for (int i = 3; i <= n; i++) {int third = first + second;first = second;second = third;}return second;}
}

解题思路

这个问题是斐波那契数列的一个变种。我们可以观察到,要到达第 n 个台阶,有两种情况:

  1. 从第 n-1 个台阶走上来,方法数为 climbStairs(n-1)
  2. 从第 n-2 个台阶走上来,方法数为 climbStairs(n-2)

因此,到达第 n 个台阶的总方法数为 climbStairs(n-1) + climbStairs(n-2)。这就是斐波那契数列的定义。

复杂度分析

  • 时间复杂度:O(n),因为我们需要从 1 到 n 遍历一次。
  • 空间复杂度:O(1),我们只需要常数级别的空间来存储几个变量。

通过使用动态规划的思想,我们可以避免重复计算,从而提高效率。上面的代码实现了这一思想,通过迭代而不是递归来计算爬楼梯的方法数。

注:题目来源leetcode网站

相关文章:

leetcode hot100【LeetCode 70. 爬楼梯】java实现

LeetCode 70. 爬楼梯 题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 注意&#xff1a; 给定 n 是一个正整数。 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;2 解释&…...

Java异常2

异常抛出的两种形式&#xff1a; 系统隐式抛出&#xff1b;int n10/0;—隐式抛出一个异常&#xff1b;手动抛出异常&#xff1a;throw new Exception(); import java.util.InputMismatchException; import java.util.Scanner;public class Main {public static void main(Str…...

2024熵密杯初始题2

问题简要&#xff1a; 已知 counter 0x7501E6EA token 0xF4CE927C79B616E8E8F7223828794EEDF9B16591AE572172572D51E135E0D21A 伪造出另一个可以通过验证的counter和token。 给出token生成及验证代码如下&#xff1a; import binascii from gmssl import sm3# 读取HMAC ke…...

echarts属性之title

title 标题组件&#xff0c;包含主标题和副标题。 在 ECharts 2.x 中单个 ECharts 实例最多只能拥有一个标题组件。但是在 ECharts 3 中可以存在任意多个标题组件&#xff0c;这在需要标题进行排版&#xff0c;或者单个实例中的多个图表都需要标题时会比较有用。 例如下面不…...

VUE errolog, vue 错误集

I) installation As to command “npm install” on cmd or powershell, we must execute it under the program folder...

驱动开发系列13 - Linux tasklet用法介绍

一:概述 Tasklet 是 Linux 内核中的一种轻量级任务调度机制,通常用于在中断上下文中执行短小的任务。它们在软中断处理过程中被调用,允许将较长的处理工作延后到一个较低优先级的上下文中,以减少中断处理的延迟。Tasklet 的使用可以帮助开发者更好地管理系统资源,提高性能…...

redis实现分布式锁,go实现完整code

Redis分布式锁 Redis 分布式锁是一种使用 Redis 数据库实现分布式锁的方式&#xff0c;可以保证在分布式环境中同一时间只有一个实例可以访问共享资源。 实现机制 以下是实现其加锁步骤&#xff1a; 获取锁 在 Redis 中&#xff0c;一个相同的key代表一把锁。是否拥有这把锁&…...

解析日期、编码

解析日期 这里指的是将字符串或者object类型的日期&#xff0c;转换成panda或python的日期类型。 主要的是dtype的变化&#xff1a;object / str —> datetime64[ns] # modules well use import pandas as pd import numpy as np import seaborn as sns import datetime# …...

【Qt】QApplication::restoreOverrideCursor():恢复鼠标光标到原始状态的用法解析

restoreOverrideCursor() 是 Qt 中 QApplication 类提供的一个静态函数&#xff0c;用来恢复鼠标光标到应用程序之前设置的状态。 在 Qt 中&#xff0c;你可以使用 QApplication::setOverrideCursor() 来临时更改鼠标光标的外观。例如&#xff0c;当执行一些耗时操作时&#x…...

重生之“我打数据结构,真的假的?”--2.单链表(无习题)

C语言中的单链表总结 单链表是一种基础的数据结构&#xff0c;广泛应用于C语言编程中。它由节点组成&#xff0c;每个节点包含数据和指向下一个节点的指针。单链表的优点在于动态内存分配和高效的插入与删除操作。本文将详细探讨单链表的定义、基本操作、应用场景以及相关示例…...

【有啥问啥】视频插帧算法技术原理详解

视频插帧算法技术原理详解 引言 视频插帧&#xff08;Video Interpolation&#xff09;技术&#xff0c;作为计算机视觉领域的一项重要应用&#xff0c;旨在通过算法手段在已有的视频帧之间插入额外的帧&#xff0c;从而提升视频的帧率&#xff0c;使其看起来更加流畅。这一技…...

Leetcode148,109以及二者的合并 -> Tencent面试算法题 - 无序双向链表转BST

根源简述 这道题是腾讯在2024/8/30考的一道面试题&#xff0c;整体来说&#xff0c;难度不大&#xff0c;就是代码量稍稍有点儿大&#xff0c;让我们一起来看一下吧 题目描述 整数无序双向链表能否转BST&#xff08;二叉搜索树&#xff09;&#xff0c;如果能&#xff0c;怎么转…...

【蓝桥杯选拔赛真题77】python计算小球 第十五届青少年组蓝桥杯python选拔赛真题 算法思维真题解析

目录 python计算小球 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 七、 推荐资料 1、蓝桥杯比赛 2、考级资料 3、其它资料 python计算小球 第十五届蓝桥杯青少年组python比赛选拔赛真题 一、题目要…...

获取Hive表备注

DESCRIBE EXTENDED 表名;先获取Detailed Table Information这行的data_type字段数据&#xff0c;进行正则匹配&#xff0c;拿到表备注&#xff0c;如下&#xff1a; String str ReUtil.get("parameters:\\{(?!.*?\\().*transient_lastDdlTime.*?comment(.*?)\\}&quo…...

10.30学习

一、科学计数法 C语言中的科学计数法主要用于表示非常大或非常小的浮点数&#xff0c;它遵循以下格式&#xff1a; 1. E或e表示指数&#xff1a; 科学计数法中的E或e用来表示“指数”&#xff08;Exponent&#xff09;。例如&#xff0c; 1.23e4 或 1.23E4 表示 1.23 * 10^4…...

什么是栈溢出

一、什么是栈溢出 栈溢出&#xff08;Stack Overflow&#xff09;就是指在程序运行过程中&#xff0c;往栈里存放的数据超过了栈所能容纳的最大容量&#xff0c;从而导致程序出现异常行为的情况。这就好比一个箱子本来只能装一定数量的物品&#xff0c;硬要往里面塞更多的东西&…...

在linux中arm-linux-gcc和/usr/bin/gcc有啥区别

在Linux中&#xff0c;arm-linux-gcc和/usr/bin/gcc都是编译器&#xff0c;但它们之间存在显著的区别&#xff0c;主要体现在编译目标、使用场景以及编译生成的二进制文件的可执行性上。而软链接则是Linux文件系统中的一种特殊文件类型&#xff0c;用于创建一个文件的别名。 a…...

常用环境部署(二十二)——MySQL的数据库迁移到另一个机器上

1、导出原数据库的数据 mysqldump -u [用户名] -p[密码] [数据库名] > database_dump.sql 命令示例&#xff1a; mysqldump -u root -p123456 wd > /opt/wd.sql 2、在新机器上创建数据库 mysql -u [用户名] -p -e "CREATE DATABASE [新数据库名]" 命令示…...

两台主机只能单方向ping通

可能性比较大的原因时ping不通的那台主机安装了个人防火墙。 在共享上网的机器中&#xff0c;出于安全考虑&#xff0c;大部分主机都安装个人防火墙软件。几乎所有个人防火墙软件默认不允许其他机器ping本机。一般的做法是将来自外部的ICMP请求报文滤掉&#xff0c;对本机出去的…...

redis windows 5.0 下载

Redis 简介 Redis 是一个高性能的 key-value 数据库&#xff0c;广泛应用于缓存、消息队列、实时分析等场景。它支持多种数据结构&#xff0c;如字符串、哈希、列表、集合、有序集合等&#xff0c;并且提供了丰富的操作命令&#xff0c;能够满足各种复杂的数据处理需求。 下载…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...