张雪峰：女生要嫁就嫁程序员这种“牲口”，你们同意吗？
点击蓝字 关注不迷路
前端拿破轮，码动扭乾坤！
大家好啊，我是拿破轮。
周一第一天，是不是无心上班？没事，看看今天的文章，找回自信！
十年搬砖无人问，一朝“牲口”天下知。
对于张雪峰，大家应该不陌生吧？他总是为学生量身打造切合实际的升学规划建议，并且他总是会尽量给普罗大众一个相对的最优解，让很多人愿意找他“取经”。
前不久，就有一个女孩，说自己是文科生，来自偏远小城，想留在大城市发展，但是又不想太卷太累，问张雪峰自己应该学什么？
张雪峰给的建议是：
既然不想太累，就考一个计算机还不错的大学，然后在这个大学学一个好找工作的专业，比如会计，将来定居努力考个编制，然后找个学计算机或者软件工程，毕业出来做码农的“牲口”男朋友。
这些理工男生负责赚钱，你负责花钱，前提条件是你得对人家好。他们比较老实，平时和女生说话都瑟瑟发抖，你就找这样的，千万别嫌弃理工男不浪漫，因为你不能既要又要还要，人这一辈子不可能啥好处都占尽。
你不想累又想过得体面，那就找个将来能有高收入的老公，然后好好对人家，把家庭打理好，把老公孩子照顾好，至少能符合你提出来的预期。
虽然张雪峰的话糙理不糙，但仍然让程序员坐不住了，纷纷表示，虽然说得对，也不至于被叫成“牲口”吧……
把程序员称为“牲口”有点过分，但是对于张雪峰说的程序员多金、老实、顾家、疼老婆，大家表示确实如此。不少对象是程序员的小姐姐现身说法，称自己遇到的程序员就是这样的！
甚至有小姐姐直接原地开大
传下去，程序员多金、老实、顾家、疼老婆，找对象就找序员！
你觉得程序员老公怎么样呢？欢迎评论区交流！
Science Technology
好了，言归正传，今天拿破轮来和大家一起看一道LeetCode算法题：爬楼梯
1
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
提示：1 <= n <= 45
思路
对于爬n阶楼梯总共有多少种方法，我们考虑最后一步的可能情况。因为每一步只能走1阶或者2阶，所以最后一步只有两种可能：
从n-2阶爬了2阶到第n阶
从n-1阶爬了1阶到第n阶
除此以外再无其他可能。所以爬到第n阶的方法总数应该是爬到第n-2阶的方法总数与爬到第n-1阶的方法总数和.即
climbStairs(n)=climbStairs(n-1)+climbStairs(n-2)
解题过程
通过上述分析，我们不难发现，这是一道典型的斐波那契数列.故最简单,最容易理解的方式就是递归实现.代码实现如下：
Code
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
// 递归实现
// 递归基例
if(n===1) return 1 // 如果是爬到第1阶楼梯，只有1种方法
if(n===2) return 2 // 如果是爬到第2阶楼梯，有两种方法(1+1)和(2)
// 递归链条
return climbStairs(n-1) + climbStairs(n-2)
};复
- 时间复杂度: O(2^n)
这个递归函数的时间复杂度是指数级别的。具体来说，每次调用 climbStairs(n) 都会进一步调用 climbStairs(n-1) 和 climbStairs(n-2)，这形成了一个二叉树形的递归结构。对于每个 n，函数会被调用大约2^(n-1) 次（这是最坏情况下的上界）。因此，该函数的时间复杂度是 O(2^n).
- 空间复杂度: O(n)
空间复杂度主要由递归调用栈决定。在这个例子中，递归深度最大为 n，因此递归调用栈的最大深度也是 n。这意味着函数的空间复杂度为 O(n)，这是因为每次递归调用都需要一定的栈空间来保存局部变量和返回地址等信息。
上述算法在n很大的情况下的时间开销非常大，并且有很多额外开销。例如在计算climbStairs(5)时，climbStairs(3)要被计算两次(climbStairs(5)的递归中一次，climbStairs(4)的递归中一次).所以我们考虑优化算法：滑动窗口。
什么是滑动窗口呢？其实就是一个队列。队列中三个元素分别为climbStairs(n-2),climbStairs(n-1)和climbStairs(n).起初让n=0,即爬到第0阶台阶，也就是起始位置，不用爬，只有1种方法。
此时我们可以设置前两个为空元素，即此时的队列为[0,0,1].接下来我们根据输入参数n来滑动窗口，也就是让队首元素出队，新的元素入队，那新的元素怎么来呢？就是此时队尾最后两位元素之和。(因为climbStairs(n)=climbStairs(n-1)+climbStairs(n-2)).故移动1次，滑动窗口(队列)变为[0,1,1]。以此类推即可。代码实现如下：
Code
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
// 滑动窗口实现
// 初始化队列
let left = 0 // 队首元素
let mid = 0 // 队中元素
let right = 1 // 队尾元素，即n=0是的方法总数
// 根据传入参数将窗口滑动
for (let i = 0; i < n; i++) {
left = mid
mid = right
right = left + mid
}
return right //返回队尾元素
};复杂度.
- 时间复杂度:O(n)
这是因为循环体执行了 n 次，每次迭代都执行常数时间的操作，包括赋值和加法运算。
- 空间复杂度: O(1)
空间复杂度主要由递归调用栈决定。在这个例子中，递归深度最大为 n，因此递归调用栈的最大深度也是 n。这意味着函数的空间复杂度为O(n)，这是因为每次递归调用都需要一定的栈空间来保存局部变量和返回地址等信息。
我是拿破轮，关注我，一起分享更多前端知识！
点
击
关
注
解锁更多精彩内容
注：图片素材来源网络，如有侵权，请联系删除
