算法题是在面试过程中考察候选人逻辑思维能力、手写代码能力的一种方式,因为有一句古话说的好:“说一千道一万,不如写段代码看一看”。
今天我们就来个单刀直入,直奔主题,从一个真实面试题到底怎么爬楼梯
来聊一聊算法中的动态规划
。
小明家有一楼梯共有10级台阶,每次可以爬1级或2级,问小明爬到第10级台阶,一共有多少种走法?
为什么是“小明”呢?这是个奇怪的问题~
很多同学在第一次遇到这个爬楼梯的问题可能会比较懵
,不知道该如何来解决。我们首先需要做的就是寻找这个问题的关键点:每次只能爬1级或2级
。
小明每次只能爬1级或2级,那么对于爬到第10级台阶来说,最后一次操作为走1级(此时处于第9级台阶上)或走2级(此时处于第8级台阶上)。
假定我们有个表达式f可以来计算到达某阶台阶的走法,那么对于第10阶来说,这个表达式就应该为:f(10) = f(9) + f(8)
。
对于这个表达式,是不是有种瞬间回到那初、高中的年代~
按如上规则,再次考虑,爬到第9级台阶时,最后一次操作为走1级(此时处于第8级台阶上)或走2级(此时处于第7级台阶上),此处的表达式为:f(9) = f(8) + f(7)
。
......
依次处理,当爬到第3级台阶时,计算的表达式就是f(3) = f(2) + f(1)
。
那爬到第2级台阶有几种方式呢:每次走1级或者一次走2级,也就是一共有2种走法,f(2) = 2
。
爬到第1级台阶的方式肯定只有一种:走1级,f(1) = 1
。
按我们的思考逻辑,相关代码如下:
/**
* @method climbStairs
* @description 爬楼梯
* @param {number} n 楼梯台阶数
* @return {number} 一共有多少种走法
*/
function climbStairs (n) {
if (n === 1) { return 1 };
if (n === 2) { return 2 };
let num = 0;
num = climbStairs(n - 1) + climbStairs(n - 2);
return num;
}
// 调用函数,输出结果
let num = climbStairs(10);
console.log(num); // 89
Congratulations~我们已经完成啦,得到了正确的结果。
就在你满脸微笑、志得意满的向面试官讲解思路的时候,面试官十有八九会一副老狐狸得逞的样子,继续问你,假如n的值比较大的,如40之类的,上面定义的climbStairs
的执行性能如何。
我们来看下执行的性能:
测试代码如下:
console.time();
let num = climbStairs(40);
console.log(num);
console.timeEnd()
我的mac配置如下:
MacBook Pro
处理器:2.5 GHz 四核Intel Core i7
内存: 16GB
连续执行三次数据如下:
序号 | 结果 | 执行时间 |
---|---|---|
1 | 165580141 | 811.077ms |
2 | 165580141 | 817.025ms |
3 | 165580141 | 814.803ms |
注:在执行过程中有卡顿,不是瞬间输出,如果执行的是```climbStairs(100)```,你应该会瞬间听到风扇启动的呜呜声
在上面代码climbStairs
的基础上我们来进行优化处理。我们仔细分析代码的执行流程,就会发现有很多重复计算的地方,比如说f(5)
就会在f(6-1)
、f(7-2)
时被重复计算,这就浪费了时间和性能。
那我们就选择使用空间换时间的策略,设置对象numbers
,保存爬到某级台阶的结果,避免重复计算,numbers
对象的结果如下:
let numbers = {
1: 1,
2: 2
}
优化后代码如下:
/**
* @method climbStairs
* @description 爬楼梯
* @param {number} n 楼梯台阶数
* @return {number} 一共有多少种走法
*/
function climbStairs (n) {
// 存储计算的结果,key(台阶) : num(走法)
let numbers = {
1: 1,
2: 2
};
let tmpClimbStairs = function (n) {
// 已存在的数据,直接返回,不再重新计算
if (numbers[n]) {
return numbers[n];
}
// 不存在的数据,进行计算
let num = tmpClimbStairs(n - 1) + tmpClimbStairs(n - 2);
// 计算完成后,存放如numbers中,下次可以直接使用
numbers[n] = num;
// 返回结果
return num;
}
// 计算结果
let num = tmpClimbStairs(n);
// 返回结果
return num;
}
相同环境下,我们再来执行测试,连续执行三次数据如下:
序号 | 结果 | 执行时间 |
---|---|---|
1 | 165580141 | 7.100ms |
2 | 165580141 | 7.478ms |
3 | 165580141 | 6.260ms |
消耗的时间竟然相差百倍之多,It's amazing!说明我们使用空间换时间的策略是正确的。
执行结果几乎是瞬间输出的,执行如丝袜奶茶般顺滑~此时此刻你可以再次执行climbStairs(100)
来体验下绝对的性能飙升!
这道面试题处理成这样已经是非常OK的了,但是如果你已经感到彻底满足,为自己的聪明才智感到骄傲了,你就会听到面试官可爱(恨)的声音传来:”还有别的方法或性能更好的方法来实现吗?“
是不是心中一口老血想喷出来面试官是不是故意的,是不是在针对我
哈哈,不慌不慌,小场面~
递归与递推是两种不同的看待、分析问题的思路。
递归
:自顶向下的处理逻辑,有相应的临界点(终止递归的点);
递推
:自底向上的处理逻辑,到达目标点结束。
我们重新使用递推
的方式再来看这个问题。
爬到第1级台阶,有1种方式。 f(1) = 1
;
爬到第2级台阶,有2种方式:每次1级或1次2级。f(2) = 2
;
爬到第3级台阶的情况呢?
不要忘了我们之前分析的关键点:每次只能1级或2级,
对于第3级台阶来说,可以是从第1级台阶出发也可以是从第2级台阶出发,
所以f(3) = f(2) + f(1)
同理可得爬到第4级台阶的情况,f(4) = f(3) + f(2)
我们得出一个结论:对于第N(N > 2)级台阶,其表达式为f(N) = f(N-1) + f(N-2)
。那么我们在结算的过程中,每次都记录下f(N-1)
和f(N-2)
的值,逐级迁移这个值,就可以得到f(N)
了。
现在climbStairs
代码如下:
/**
* @method climbStairs
* @description 爬楼梯
* @param {number} n 楼梯台阶数
* @return {number} 一共有多少种走法
*/
function climbStair (n) {
// 通过观察,我们可只第1级和第2级都是返回对应的n
if (n <= 2) {
return n;
} else {
// 对于n > 2的情况
let i = 1; // 初始存放第1级台阶的走法,对应的是f(N-2)
let j = 2; // 初始存放第2级台阶的走法,对应的是f(N-1);
// 定义走法num
let num;
// 从第3级开始,执行循环操作
for (let k = 3; k <= n; k++) {
// f(N) = f(N-1) + f(N-2)
num = i + j;
// 同时移动
// 将f(N-1)的值给f(N-2)
i = j;
// 将当前值给f(N-1)
j = num;
}
// 返回结果
return num;
}
}
这一次我们直接在时间复杂度上降低了,变成了
O(N)
,执行起来更加是和那啥一样,流畅、顺滑~
我们来看下测试效果,连续执行三次测试结果如下:
序号 | 结果 | 执行时间 |
---|---|---|
1 | 165580141 | 6.570ms |
2 | 165580141 | 6.647ms |
3 | 165580141 | 6.658ms |
相对于
递归
的实现方式,递推
的实现从时间复杂度上更低,执行也会更高效~
此时此刻,这个爬楼梯的问题终于是回答圆满了,这个时候面试官看你就会像丈母娘看女婿一样,怎么看怎么可爱
。
动态规划的算法问题有很多种不同的形式,爬楼梯是其中的一种。在这里胡哥要给大家留一道面试题啦,看看大家对动态规划是不是有了深刻的理解。
面试真题如下:
你是一个有信仰的强盗,有一排房屋等待你去抢劫,在抢劫中不能相邻的房屋不能抢,只能间隔一个或多个房屋进行抢劫,房屋中钱财都是非负整数,数据格式如下:[3, 4, 5, 2, 1, 1]
,请计算出你能抢到的最大金额是多少。
这个强盗相当有信仰,竟然不都抢走~
欢迎各位小伙伴留言,谈谈你对动态规划的理解,留下这道面试题的答案,一起来探讨交流~
以上就是胡哥今天给大家分享的内容,喜欢的小伙伴记得点赞
、收藏
呦,关注胡哥有话说,学习前端不迷路,欢迎多多留言交流...
胡哥有话说,专注于大前端技术领域,分享前端系统架构,框架实现原理,最新最高效的技术实践!
联系客服