当前位置: 首页 > 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;能够满足各种复杂的数据处理需求。 下载…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...