H5W3
当前位置:H5W3 > JavaScript > 正文

【JS】面试官在“逗”你系列:到底应该怎么爬楼梯?!

面试官在“逗”你系列:到底应该怎么爬楼梯?!

胡哥有话说发布于 今天 03:31

直奔主题

算法题是在面试过程中考察候选人逻辑思维能力、手写代码能力的一种方式,因为有一句古话说的好:“说一千道一万,不如写段代码看一看”。

【JS】面试官在“逗”你系列:到底应该怎么爬楼梯?!

今天我们就来个单刀直入,直奔主题,从一个真实面试题到底怎么爬楼梯来聊一聊算法中的动态规划

面试真题

小明家有一楼梯共有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

就在你满脸微笑、志得意满的向面试官讲解思路的时候,面试官十有八九会一副老狐狸得逞的样子,继续问你,假如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 的基础上我们来进行优化处理。我们仔细分析代码的执行流程,就会发现有很多重复计算的地方,比如说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

执行结果几乎是瞬间输出的,执行如丝袜奶茶般顺滑~此时此刻你可以再次执行 climbStairs(100) 来体验下绝对的性能飙升!

这道面试题处理成这样已经是非常OK的了,但是如果你已经感到彻底满足,为自己的聪明才智感到骄傲了,你就会听到面试官可爱(恨)的声音传来:”还有别的方法或性能更好的方法来实现吗?“

是不是心中一口老血想喷出来~面试官是不是故意的,是不是在针对我~

哈哈,不慌不慌,小场面~

递归与递推

递归与递推是两种不同的看待、分析问题的思路。

递归:自顶向下的处理逻辑,有相应的临界点(终止递归的点);

递推:自底向上的处理逻辑,到达目标点结束。

递推思想

我们重新使用递推的方式再来看这个问题。

  1. 爬到第1级台阶,有1种方式。 f(1) = 1
  2. 爬到第2级台阶,有2种方式:每次1级或1次2级。f(2) = 2
  3. 爬到第3级台阶的情况呢?

    不要忘了我们之前分析的关键点:每次只能1级或2级,
    对于第3级台阶来说,可以是从第1级台阶出发也可以是从第2级台阶出发,
    所以f(3) = f(2) + f(1)

  4. 同理可得爬到第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;
}
}

我们来看下测试效果,连续执行三次测试结果如下:

序号 结果 执行时间
1 165580141 6.570ms
2 165580141 6.647ms
3 165580141 6.658ms

此时此刻,这个爬楼梯的问题终于是回答圆满了,这个时候面试官看你就会像丈母娘看女婿一样,怎么看怎么可爱

动态规划的算法问题有很多种不同的形式,爬楼梯是其中的一种。在这里胡哥要给大家留一道面试题啦,看看大家对动态规划是不是有了深刻的理解。

面试真题如下:

你是一个有信仰的强盗,有一排房屋等待你去抢劫,在抢劫中不能相邻的房屋不能抢,只能间隔一个或多个房屋进行抢劫,房屋中钱财都是非负整数,数据格式如下:[3, 4, 5, 2, 1, 1],请计算出你能抢到的最大金额是多少。

欢迎各位小伙伴留言,谈谈你对动态规划的理解,留下这道面试题的答案,一起来探讨交流~

后记

以上就是胡哥今天给大家分享的内容,喜欢的小伙伴记得点赞收藏呦,关注胡哥有话说,学习前端不迷路,欢迎多多留言交流…

javascript
阅读 53发布于 今天 03:31
本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议
avatar

胡哥有话说

公号『胡哥有话说』作者。

167 声望
5 粉丝

0 条评论
得票时间

avatar

胡哥有话说

公号『胡哥有话说』作者。

167 声望
5 粉丝

宣传栏

直奔主题

算法题是在面试过程中考察候选人逻辑思维能力、手写代码能力的一种方式,因为有一句古话说的好:“说一千道一万,不如写段代码看一看”。

【JS】面试官在“逗”你系列:到底应该怎么爬楼梯?!

今天我们就来个单刀直入,直奔主题,从一个真实面试题到底怎么爬楼梯来聊一聊算法中的动态规划

面试真题

小明家有一楼梯共有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

就在你满脸微笑、志得意满的向面试官讲解思路的时候,面试官十有八九会一副老狐狸得逞的样子,继续问你,假如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 的基础上我们来进行优化处理。我们仔细分析代码的执行流程,就会发现有很多重复计算的地方,比如说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

执行结果几乎是瞬间输出的,执行如丝袜奶茶般顺滑~此时此刻你可以再次执行 climbStairs(100) 来体验下绝对的性能飙升!

这道面试题处理成这样已经是非常OK的了,但是如果你已经感到彻底满足,为自己的聪明才智感到骄傲了,你就会听到面试官可爱(恨)的声音传来:”还有别的方法或性能更好的方法来实现吗?“

是不是心中一口老血想喷出来~面试官是不是故意的,是不是在针对我~

哈哈,不慌不慌,小场面~

递归与递推

递归与递推是两种不同的看待、分析问题的思路。

递归:自顶向下的处理逻辑,有相应的临界点(终止递归的点);

递推:自底向上的处理逻辑,到达目标点结束。

递推思想

我们重新使用递推的方式再来看这个问题。

  1. 爬到第1级台阶,有1种方式。 f(1) = 1
  2. 爬到第2级台阶,有2种方式:每次1级或1次2级。f(2) = 2
  3. 爬到第3级台阶的情况呢?

    不要忘了我们之前分析的关键点:每次只能1级或2级,
    对于第3级台阶来说,可以是从第1级台阶出发也可以是从第2级台阶出发,
    所以f(3) = f(2) + f(1)

  4. 同理可得爬到第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;
}
}

我们来看下测试效果,连续执行三次测试结果如下:

序号 结果 执行时间
1 165580141 6.570ms
2 165580141 6.647ms
3 165580141 6.658ms

此时此刻,这个爬楼梯的问题终于是回答圆满了,这个时候面试官看你就会像丈母娘看女婿一样,怎么看怎么可爱

动态规划的算法问题有很多种不同的形式,爬楼梯是其中的一种。在这里胡哥要给大家留一道面试题啦,看看大家对动态规划是不是有了深刻的理解。

面试真题如下:

你是一个有信仰的强盗,有一排房屋等待你去抢劫,在抢劫中不能相邻的房屋不能抢,只能间隔一个或多个房屋进行抢劫,房屋中钱财都是非负整数,数据格式如下:[3, 4, 5, 2, 1, 1],请计算出你能抢到的最大金额是多少。

欢迎各位小伙伴留言,谈谈你对动态规划的理解,留下这道面试题的答案,一起来探讨交流~

后记

以上就是胡哥今天给大家分享的内容,喜欢的小伙伴记得点赞收藏呦,关注胡哥有话说,学习前端不迷路,欢迎多多留言交流…

本文地址:H5W3 » 【JS】面试官在“逗”你系列:到底应该怎么爬楼梯?!

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址