LeetCode 爬楼梯算法题的解法及优化

2020年4月19日11:26:04 发表评论 90 views

爬楼梯算法

LeetCode 爬楼梯算法题的解法及优化

都知道爬楼梯算法最重要的在于递归的思想,那我们就来聊聊递归

递归是什么?

  1. 概念
  • 在程序中函数直接或间接调用自己
  • 直接调用自己
  • 间接调用自己
  • 跳出结构,有了跳出才有结果
  1. 思想
  • 递归的调用,最终还是要转换为自己这个函数
  • 如果有个函数fd,如果他是递归函数,到最后问题还是转换为函数fd的形式
  • 递归的思想就是将一个未知问题转换为一个已解决的问题来实现
function fd(){
    ...fd()...
}
复制代码

了解了递归之后,我们来聊聊爬楼梯算法

n阶楼梯的走法

首先,当只有一阶楼梯的时候,很显然只有一种走法; 有两阶楼梯的时候,也很显然的知道有两种走法。就会有下面这句判断语句

if (n == 1 || n == 2) {
        return n;
    }
复制代码

一阶二阶的思想就出来了,那如果当阶数是三阶四阶甚至n阶的时候呢? 这个时候递归的思想就出来了,如果阶数是n阶的时候,走法如下:

   climbStairs(n - 2) + climbStairs(n - 1);
复制代码

聊着聊着我们的代码就出来了

var climbStairs = function (n) {
    if (n == 1 || n == 2) {
        return n;
    }
    else {
        return climbStairs(n - 2) + climbStairs(n - 1);
    }
}
复制代码

这个时候就可以开开心心去LeetCode提交代码了,然后你就会发现

LeetCode 爬楼梯算法题的解法及优化

???这又是个啥玩意? 我辛辛苦苦打出来的代码,你跟我搞这个?

冷静下来仔细一想,我就发现了问题所在,原来是递归的重复计算导致了内存的溢出,接下来就要优化内存的分配。递归是可以优化成循环的,这里我是用定义多个变量减少内存分配来解决这个问题的。

function climbStairs(n){
    if (n == 1 || n == 2) 
        return n;

let ret = 0,
pre = 2,
prepre = 1;
for(let i = 3; i <= n ;i++){
    ret = pre + prepre;
    prepre = pre;
    pre =ret
}
return ret;
}
复制代码

总结

首先拿到爬楼梯这个问题的时候,我马上就想到了要用递归的方法去做,然后去查询了些关于递归的知识。接着分析问题,楼梯只有一阶二阶的时候是个特殊情况,递归思想写出n阶楼梯时的完整代码,当我去LeetCode提交代码的时候,我又认识到了内存溢出的问题,对代码进行了优化,最后写出了这个代码。

作者:梦想的天空分外蓝
链接:https://juejin.im/post/5e971dc1e51d45470246073b
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: