前端:经典的递归面试题

更新日期: 2018-12-19阅读: 2.4k标签: 面试

细胞分裂

细胞分裂 有一个细胞 每一个小时分裂一次,一次分裂一个子细胞,第三个小时后会死亡。那么n个小时候有多少细胞? 这个问题的核心就是三个小时为一个周期

// 每三个小时为一个周期 , 第四个小时就 go die 了。
// 方法一
// 第一个小时,只有a态细胞;第二个小时,a态细胞分裂,原来的a态细胞变成了b态细胞,分裂出来的细胞变成了新的a态细胞;第三个小时,a态细胞继续分裂变成b态细胞和新的a态细胞,b态细胞分裂变成c态细胞和a态细胞;第四个小时,a、b、c态细胞都会分裂,并且按照之前的规律转变。得出下面的结论
// a 初始态 一个小时 前一个小时的 a+b+c
// b 幼年态 两个小时 前一个小时的 a
// c 成熟态 三个小时 前一个小时的 b
function allCell(n){
    // a态细胞
    let aCell = function(n){
        if(n==1){
            return 1;
        }else{
            return aCell(n-1)+bCell(n-1)+cCell(n-1);
        }
    }
    // b态细胞
    let bCell = function(n){
        if(n==1){
            return 0;
        }else{
            return aCell(n-1);
        }
    }
    // c态细胞
    let cCell = function(n){
        if(n==1||n==2){
            return 0;
        }else{
            return bCell(n-1);
        }
    }
    return aCell(n)+bCell(n)+cCell(n)
}
console.log(allCell(10))
// 方法二
// 这个方法就是分成了 活着的 和 死亡的
function cell(hour){
    // 活着的细胞
    function livecell(hour){
        if(hour<4){
            // 前三个小时没有死亡的细胞 成2的n-1次方增长
            return Math.pow(2,hour-1)
        }else{
            // 从第四个小时开始有死亡的细胞 
            // 活着的细胞 = 前一个小时活着的细胞 - 这个小时死去的细胞
            return livecell(hour-1)*2 - diecell(hour)
        }
    }
    // 死亡的细胞
    function diecell(hour){
        if(hour<4){
            // 前三个小时没有死亡的细胞
            return 0
        }else{
            // 因为三个小时一个周期
            // 也就是每三个小时,(n-3)时的细胞就会死完
            // 那么 这个小时(n)死去的细胞 + 上个小时(n-1)死去的细胞 + 前两个小时(n-2)死去的细胞 = 前三个小时(n-3)活着的细胞
            return livecell(hour-3) - diecell(hour-1) - diecell(hour-2)
        }
    }
    return livecell(hour)
}
console.log(cell(10))


斐波那契数列

又称兔子数列,是以兔子繁殖为例,得出这样一个数列:1,1,2,3,5,8... 指从第三个值开始,每个值都是前两个值的和。
// 递归
    let a = 0;
    function tu(num){
        a++
        if(num==1||num==2){
            return 1
        }
        let nums = tu(num-1)+tu(num-2)
        return nums
    }
    console.log(tu(8),a)
// 闭包解决
    // 也就是存在数组中,再次循环时,如果数组中已经存在,就返回数组中的值,大大减少了递归调用函数的次数
    var count2=0;
    var fiba = (function(){
        var arr = [0,1,1];   //第0位只是占位,从第一位开始算起
        return function(n){
            count2++;   
            var res=arr[n]; 
            if(res){// 如果arr中存在,返回这个值
                console.log(res,'----')
                return res;
            }else{
                console.log(arr[n],'+++++')
                arr[n]=fiba(n-1)+fiba(n-2);
                return arr[n];
            }   
        }
    })();
    console.log(fiba(8),count2)
// 普通
    // 普通循环解决这个问题是性能最好的。
    let a = 1;
    let b = 1
    let c;
    function tu(num){
        for(let i=0;i<num-2;i++){
            c = a+b;
            a = b;
            b = c
        }
        return c;
    }
    console.log(tu(8))


64格子

有 64 个格子,第一个格子放一粒麦子,第二个放2粒,第三个放4粒...每个格子都是前边的两倍。一共有多少粒?
let sum = 0
let start = 1;
let end = 0;
function tow(){
    if(end>=64){
        return false
    }
    sum+=start
    start*=2
    end++
    tow()
}
tow()
console.log(sum)


使用递归实现数组快速排序方法

这个问题的核心思想是 取中间值,然大的放一边,小的放一边,然后再对两边执行一样的操作,也就是递归了。
var mysort = function(arr){
    // 结束条件
    if(arr.length<=1){
        return arr
    }
    // 找基准值 数组中间值
    // 求下标
    var center = Math.floor(arr.length/2)
    var jZ = arr.splice(center,1)[0]
    // 创建两个空数组
    var left = [] , right = [];
    // 循环数组,并进行比较
    for(var i=0;i<arr.length;i++){
        if(arr[i]<jZ){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    return mysort(left).concat([jZ],mysort(right))
}
console.log(mysort([1,6,4,3,7,8,9]))


九九乘法表

// 递归
function num(nums){
    if(nums==1){
        console.log("1x1=1")
    }else{
        num(nums-1)
        for(var i=1,str='';i<=nums;i++){
            str += `${i}x${nums}=`+i*nums+' '
        }
        console.log(str)
    }
}
num(9)
// 循环
for(var i=1;i<10;i++){
    let str = ''
    for(var j=1;j<10;j++){
        if(i>=j){
            str += `${j}x${i}=`+i*j+' '
        }
    }
    console.log(str)
}

链接: https://fly63.com/article/detial/2457

Web前端年后跳槽面试复习指南

很多童鞋可能年后有自己的一些计划,比如换份工作环境,比如对职业目标有了新的打算。当然面试这一关不得不过,大概又不可能系统性的复习,这里罗列一些 重点 面试的知识点和文章,

前端面试之webpack面试常见问题

什么是webpack和grunt和gulp有什么不同?什么是bundle,什么是chunk,什么是module?什么是Loader?什么是Plugin?如何可以自动生成webpack配置?webpack-dev-server和http服务器如nginx有什么区别?

每个 JavaScript 工程师都应当知道的 10 个面试题

多问问应聘者高层次的知识点,如果能讲清楚这些概念,就说明即使应聘者没怎么接触过 JavaScript,也能够在短短几个星期之内就把语言细节和语法之类的东西弄清楚。

37个JavaScript基本面试问题和解答

面试比棘手的技术问题要多,这篇文章整理了37个JavaScript基本面试问题和解答,这些仅仅是作为指导。希望对前端开发的你有所帮助!

React常见面试题

React常见面试题:React中调用setState之后发生了什么事情?React中Element与Component的区别?优先选择使用ClassComponent而不是FunctionalComponent?React中的refs属性的作用是什么?React中keys的作用是什么?

有趣的Js面试题_如何让 (a == 1 && a == 2 && a == 3) 返回 true

题目大意为:JS 环境下,如何让 a == 1 && a == 2 && a == 3 这个表达式返回 true ?这道题目乍看之下似乎不太可能,因为在正常情况下,一个变量的值如果没有手动修改,在一个表达式中是不会变化的。

js练习笔记:10道JavaScript题目

10道JavaScript题目:累加函数addNum、实现一个Person类、实现一个arrMerge 函数、实现一个toCamelStyle函数、setTimeout实现重复调用、实现一个bind函数、实现一个Utils模块、输出一个对象自身的属性

vue菜鸟从业记:没准备好的面试,那叫尬聊

面试开场白总缺少不了自我介绍,一方面是面试官想听听你对自己的介绍,顺便有时间看看简历上的描述,是否与口述一致。另一方面就是看看你简历上做过什么项目,用到了哪些技术栈,一会儿好提问你。

毕业一年左右的前端妹子面试总结

把面试当做学习,这个过程你会收益很大。前端知识很杂,可能实际工作中用到的技术,像框架都是跟着公司的要求走的,像我最近也在看React啦,Vue和React都对比着再学习

vue面试时需要准备的知识点

vue上手可以说是比较轻松而且简单,如果你用过angular,react,你也会很喜欢vue。vue的核心思想依旧是:构建用户界面的渐进式框架,关注视图的变化。这也是为什么新建的文件是结构是template script style

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!