面试题：数组全排列+排序

2018/03/26百词斩面试编程题3

前言

递归题做的真的是 很头大 我等小渣渣真的看得一头雾水
所以只有请教各个大神了
然后 以下
来自大佬的‘嘲讽’…

题目

收，看题

思路

第一反应-递归。
智商限制，没能自己做出来。
以下是大神的思路~
写一个方法来做递归函数。
该方法需要两个参数，第一个参数是已经排好序的部分，第二个参数是需要进行排序打印的数组。
如果最后一个参数length>1，说明还有排序的可能，进入for循环，把下一个可能的值循环取出来。
->通过slice取出，取出的数与a拼接城下一个函数的第一个参数a，原数组改变，继续执行该方法。
如果最后个参数length为1，则不需要排序了，直接打印出好的。

代码

var resArr = [];
function temp(a, arr) {
    //console.log('a =',a, '  arr =',arr.join(''))
    let tempArr = arr.slice();
    if(arr.length != 1) {
        for(let i = 0; i < arr.length; i++) {                
            let txTempArr = tempArr.slice();
            temp(a + '' + txTempArr.splice(i, 1)[0], txTempArr);
        }
    } else {
        var res = a + '' +arr[0]   //一个完整的排列
        //console.log('结果=',res)
        resArr.push(res)     
    }
}
temp('',[1,2,3])
console.log(resArr)
/*输出 ["123", "132", "213", "231", "312", "321"]*/

3月27

我一直没有理解到他是怎么进行排序的，所以就每次进入temp函数的就打印出其参数。
结果如下

可以对比着代码看看结果。稍微有点明白了
但是他是怎么进行的循环，代码执行顺序是什么 真的很懵。
然后自己画了张图便于自己理解。其实思路清晰之后看题就不觉得那么难了。

扩展-关于递归

求上述题中有数组长度为n 则多少种排序可能性（阶乘）

function factorial(n) {
    return n <= 1 ? 1 : n * factorial( n-1 );
}
console.log(factorial(3))  //6
console.log(factorial(4))  //24

经典函数-斐波拉契的兔子数列

假设兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。
第一个月我们有一对小兔子，如果所有兔子都不死，那么每个月的兔子对数就是1、1、2、3、5、8、13….
得出：斐波拉契数列：0、1、1、2、3、5、8、13、21……从第三项起，它的每一项都等于前两项的和。
问题： 求任意月兔子的总数

function func( n )
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    return func(n-1) + func(n-2);
}
var a = func(22);
console.log(a);

总结

天道酬勤