侧边栏壁纸

LeetCode-70 Climb Stairs

2022年06月02日 430阅读 0评论 0点赞

1.png

爬楼梯的题目,这题目难度是easy,但是我感觉作为我第一次刷leetcode遇到的算法题还是有点难度的。思路不难想但是要写出来这个代码好像需要点时间。
简单概括这个题目的意思就是一个人可以选择一次上1节台阶,也可以选择一次上2节台阶,问如果一共有n节台阶,他有几种上楼的走法。比如说一共有3节台阶,他就有三种走法,要么1+1+1, 要么1+2,要么2+1. 可以从后往前推,思考一下如何达到最后一节台阶,假设我们要抬脚走上最后一节台阶,我们要么走一步要么走两步,假设count(n)代表走上第n个台阶里包含的走法数量,那么count(n) = count(n-1) + count(n-2),想不通的话可以多想想,这是一个普通的脑筋急转弯,其实这是让我们去写一个斐波那契数列。
针对这个问题,有三种写法,
第一种就是直接使用recursion,不过每次都需要从头开始不断的算,很浪费时间,leetcode里面的题目似乎还有时间上的限制,我第一次用这个他给我报了run time error
2.png

第二种的办法的话好一点,就是一开始建立一个袋子,里面放我们需要的数字,然后我们再去写我们的函数
3.png

第三种办法和第二种差不多,只不过我把建立袋子这个行为加进了我们的函数里面而已,虽然我也不明白为啥run time要比第二种慢,不过我感觉也无所谓了,反正能过就行~
4.png


总结一下就是第一种办法也行但是速度太慢,现在这么内卷,用第一种办法绝对上不了台面了。
5.png

0
打赏

—— 评论区 ——

请登录后发表评论
立即登录
LOGIN