【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

连续执行三次数据如下:

序号结果执行时间
1165580141811.077ms
2165580141817.025ms
3165580141814.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;

}

相同环境下,我们再来执行测试,连续执行三次数据如下:

序号结果执行时间
11655801417.100ms
21655801417.478ms
31655801416.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;

}

}

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

序号结果执行时间
11655801416.570ms
21655801416.647ms
31655801416.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

连续执行三次数据如下:

序号结果执行时间
1165580141811.077ms
2165580141817.025ms
3165580141814.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;

}

相同环境下,我们再来执行测试,连续执行三次数据如下:

序号结果执行时间
11655801417.100ms
21655801417.478ms
31655801416.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;

}

}

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

序号结果执行时间
11655801416.570ms
21655801416.647ms
31655801416.658ms

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

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

面试真题如下:

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

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

后记

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

以上是 【JS】面试官在“逗”你系列:到底应该怎么爬楼梯?! 的全部内容, 来源链接: utcz.com/a/114545.html

回到顶部