leetcode热题100.爬楼梯(从二进制到快速幂)

Problem: 70. 爬楼梯

文章目录

  • 题目
  • 思路
  • Code
  • 复杂度

题目

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

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

示例 1:

输入:n = 2

输出:2

解释:有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶

  2. 2 阶

示例 2:

输入:n = 3

输出:3

解释:有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

思路

在上一讲从递归到动态规划中,我们讲解了递归和动态规划的求解思路,但是我们发现这两种方案的时间复杂度都为 o ( n ) o(n) o(n),我们试图找一种更加优秀的时间复杂度的解法

这里我们就要介绍快速幂的概念了

我们先将n表现为2进制,例如 3 13 3^{13} 313 = 3 1101 3^{1101} 31101 = 3 8 3^8 38 * 3 4 3^4 34 * 3 3 3

因为n有 ⌊ l o g 2 n ⌋ \lfloor log_2n \rfloor log2n+1 个二进制位 当我们知道了 a 1 , a 2 , a 3 . . . . a^1,a^2,a^3.... a1,a2,a3....后我们只需要 o ( l o g n ) o(log n) o(logn)次乘法就可以计算出 a n a^n an了。

于是我们只需要知道一个快速的方法来计算上述 3 的 2 k 2^k 2k 次幂的序列。这个问题很简单,因为序列中(除第一个)任意一个元素就是其前一个元素的平方。例如:
在这里插入图片描述

那么对于我们刚才举得例子而言,我们只要计算得出 3 8 3^8 38 3 4 3^4 34 3 3 3,就可以得到其最后的真实值。
整个算法的时间复杂度是 0 ( l o g n ) 0(logn) 0(logn),比递归和递归都要优秀

回到本题,本题快速乘有一点不同,本题要用到矩阵 ,由上一篇从递归到动态规划中,我们已经知道了状态的递归公式:
f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n-1) + f(n-2) f(n)=f(n1)+f(n2)
我们可以得到这样一个关系:
在这里插入图片描述
只要我们快速的求出矩阵的n次幂,那么我们就可以得出f(n),即最终答案。这里快速求解矩阵的方法,正是刚刚所讲的快速幂解法。

Code

class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1,1},{1,0}};
        int[][] res = pow(q,n);
        return res[0][0];

    }

    public int[][] pow(int[][] a,int n){
        int[][] ret = {{1,0},{0,1}};
        while(n>0){
            if( (n&1)==1 ){
                ret = multiply(ret,a);
            }
            n >>= 1;
            a = multiply(a,a);
        }
        return ret;
    }

    public int[][] multiply(int[][] a,int[][] b){
        int[][] c = new int[2][2];
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }

        return c;
    }


}

复杂度

时间复杂度:

只需要求 l o g ( n ) log(n) log(n)次, O ( l o g n ) O(logn) O(logn)

空间复杂度:

O ( 1 ) O(1) O(1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/540635.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

java智慧校园系统源码saas电子班牌固件安卓7.1+Java Android原生系统源码

java智慧校园系统源码saas电子班牌固件安卓7.1&#xff0b;Java Android原生系统源码 智慧校园是促进信息技术与教育教学深度有效融合、提高学与教的效果为目的&#xff0c;以物联网、云计算、大数据分析等新技术为核心技术&#xff0c;提供一种环境全面感知、智慧型、数据化、…

SaaS知识库哪些比较好用?中小企业也能适用

在快节奏的商业世界中&#xff0c;拥有一个高效、易于使用的知识管理工具是提升工作效率的关键。对于中小企业来说&#xff0c;选择合适的SaaS&#xff08;软件即服务&#xff09;知识库平台尤为重要&#xff0c;因为它不仅能帮助员工快速找到信息&#xff0c;而且还能优化客户…

[react] useState的一些小细节

1.无限循环 因为setState修改是异步的,加上会触发函数重新渲染, 如果代码长这样 一秒再修改,然后重新触发setTImeout, 然后再触发,重复触发循环 如果这样呢 还是会,因为你执行又会重新渲染 2.异步修改数据 为什么修改多次还是跟不上呢? 函数传参解决 因为是异步修改 ,所以…

TCP协议简单总结

TCP&#xff1a;传输控制协议 特点&#xff1a;面向连接、可靠通信 TCP的最终目的&#xff1a;要保证在不可靠的信道上实现可靠的传输 TCP主要有三个步骤实现可靠传输&#xff1a;三次握手建立连接&#xff0c;传输数据进行确认&#xff0c;四次挥手断开连接 三次握手建立可靠…

每日一题---OJ题: 环形链表

片头 嗨! 小伙伴们,大家好! 今天我们来讲讲这道OJ题----环形链表,准备好了吗? 我们开始咯! 题目似乎有点抽象,我们举几个例子哈 上图中,总共有4个结点,分别为 3, 2, 0, -4, 链表中有一个环,尾结点连接到第二个结点。 上图中,总共有2个结点,分别为 1, 2, 链表中有一个环, 尾结…

抖音小店选品必经五个阶段,看你到哪一步了,直接决定店铺爆单率

大家好&#xff0c;我是电商笨笨熊 新手选品必经的阶段就是迷茫期&#xff0c;不知道怎么选品&#xff0c;在哪里选品&#xff0c;选择什么样的品&#xff1b; 而有些玩家也会在进入店铺后疯狂选品&#xff0c;但是上架的商品没有销量&#xff1b; 而这些都是每个玩家都要经…

JAVA也有自己的大模型生态

说到大模型好像已经绑定了Python语言&#xff0c;现在其他语言也有大模型生态了&#xff0c;它就是Spring AI 官网介绍&#xff1a;https://spring.io/projects/spring-ai#overview github&#xff1a;https://github.com/spring-projects/spring-ai 简单介绍 Spring AI 是 A…

SSL证书添加与ICP备案,对于SpringBoot的要求

配置了SSL证书之后&#xff0c;在SpringBoot的resources文件夹里的application.properties会添加以下代码&#xff1a; server.port443 不需要添加server.address。不然会报错。 https类型的请求默认在Postman里面不可请求。 经过SSL证书处理的网页&#xff0c;链接中使默认…

成为摄影拍照高手,摄影技术进阶秘籍

一、资料前言 本套摄影高手资料&#xff0c;大小2.02G&#xff0c;共有57个文件。 二、资料目录 DSLR数码单反摄影圣经.pdf photoshop超细的人像后期磨皮及专业美化.docx “失传”的人像拍摄绝技.doc 白加黑减.怎样应用曝光补偿.pdf 标准镜头秘笈&#xff1a;标准镜如何…

CSS3 常用样式

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 ✍CSS3 常用样式&#x1f48e;1 CSS3 新增选择器&#x1f339;1.1 属性选择器…

002 若依管理系统前端vue3讲解 - svg雪碧图

小何hdc 跟着小何学编程 ☉本文由小何整理首发&#xff0c; 版权归本公众号所有&#xff0c; 如有侵犯&#xff0c;请自行删除&#xff01; svg雪碧图 安装vite-plugin-svg-icons pnpm install vite-plugin-svg-icons -D 配置 src\main.js import { defineConfig } fr…

代码训练LeetCode(14)整数反转

代码训练(14)LeetCode之整数反转 Author: Once Day Date: 2024年4月9日 漫漫长路&#xff0c;才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 190. 颠倒二进制位 - 力扣&#xff08;LeetCode&#xff09;7. 整数反转 - 力扣&#xf…

基于springboot和vue的社团管理系统(含源码+sql+视频导入教程+文档+PPT)

&#x1f449;文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1 、功能描述 基于springboot和vue的社团管理系统1有三种角色 管理员&#xff1a;社团管理、类型管理、成员管理、活动管理、通知管理、费用管理等 团长&#xff1a;审核入团申请、发布活动、发布通知…

【教学类-52-03】20240412动物数独(4宫格)难度1-9 打印版

作品展示&#xff1a;合并打印&#xff08;难度10%-90%&#xff0c;一共9份&#xff09; 背景需求 前期两个代码完成了4宫格基本样式的制作 【教学类-52-01】20240411动物数独&#xff08;4宫格&#xff09;宫格图https://mp.csdn.net/mp_blog/creation/editor/137679361【教学…

投资组合中是否应该包括黄金

最近有朋友问我&#xff0c;你对黄金怎么看&#xff1f;现在可以买黄金吗&#xff1f; 这些问题问的很好啊。首先表明我的观点&#xff1a;黄金是投机不是投资&#xff0c;黄金的长期投资价值极低&#xff0c;在我的投资组合中配置黄金的比例不会超过5%。 可能有些朋友会反对…

LeetCode-416. 分割等和子集【数组 动态规划】

LeetCode-416. 分割等和子集【数组 动态规划】 题目描述&#xff1a;解题思路一&#xff1a;01背包问题&#xff0c;动规五部曲解题思路二&#xff1a;0解题思路三&#xff1a;0 题目描述&#xff1a; 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分…

MySQL知识整理

MySQL知识整理 基础第一讲&#xff1a;基础架构&#xff1a;一条SQL查询语句是如何执行的&#xff1f;架构尽量减少长连接的原因和方案为什么尽量不要依赖查询缓存 索引第四讲&#xff1a;深入浅出索引&#xff08;上&#xff09;第五讲&#xff1a;深入浅出索引&#xff08;下…

图机器学习导论

图&#xff1a;描述关系数据的通用语言&#xff0c;起源于哥尼斯堡七桥问题 传统的机器学习&#xff1a;数据样本之间独立同分布&#xff0c;简单拟合数据边界&#xff0c;在传统的机器学习中&#xff0c;每个数据样本彼此无关。传统的神经网络&#xff0c;只能处理简单的表格、…

鱼眼摄像头畸变校正方法概述

1. 摘要 鱼眼摄像头以其独特的广阔视场和其他特点&#xff0c;在各个领域得到了广泛应用。然而&#xff0c;与针孔相机相比&#xff0c;鱼眼摄像头存在显著的畸变&#xff0c;导致拍摄的图像失畸变严重。鱼眼摄像头畸变是数字图像处理中常见的问题&#xff0c;需要有效的校正技…

产品3D模型在线展示快速实现教程

产品3D模型可以向潜在客户提供360度的观察角度&#xff0c;比平面图形的效果更好。快速实现产品3D模型的在线展示最简单的方法是使用NSDT 3DConvert的模型内嵌特性&#xff0c;无需任何开发工作&#xff0c;5分钟就可以完成&#xff1a; NSDT工具推荐&#xff1a; Three.js AI纹…