刷题1 跳台阶&暴力跳台阶&调整数组顺序

1、跳台阶

题目描述（递归）

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

题目链接

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=13&tqId=11161&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=1

分析

找规律
n=1:1种方法；
n=2:2种方法；
n=3:3种方法；
n=4:5种方法；
n=5:8种方法；
n=6:13种方法；
所以，本质上是斐波那契数列：f(n)=f(n-1)+f(n-2)。

function jumpFloor(number)
{
    if (number <=2){
        return number;
    }else{
        var s0=1;
        var s1=2;
        for (var i=3;i<=number;i++){
            s2=s1+s0
            s0=s1;
            s1=s2
        }
        return s2
    }

}

2、暴力跳台阶

题目描述（贪心）

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目链接

https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&&tqId=11162&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

分析

链接：https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387?f=discussion

关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:

f(1) = 1

f(2) = f(2-1) + f(2-2)         //f(2-2) 表示2阶一次跳2阶的次数。

f(3) = f(3-1) + f(3-2) + f(3-3) 

...

f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)

可以得出：
f(n)- f(n-1) = f(n-1) 
f(n) = 2*f(n-1)

法一：

function jumpFloorII(number)
{
    var s=1
    for(var i=1;i<number;i++){
        s=2*s       
    }
    return s
}

法二：

function jumpFloorII(number)
{
    return Math.pow(2, number - 1);
}

3、调整数组顺序奇数位于偶数前面

题目描述（数组）

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

题目链接

https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&&tqId=11166&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

分析

链接：https://www.nowcoder.com/questionTerminal/beb5aa231adc45b2a5dcc5b62c93f593?answerType=1&f=discussion

1）开辟新数组保存法

创建两个数组，一个用来存奇数，一个用来存偶数，最后合并。

function reOrderArray(array)
{
    var a = [];
    var b = [];
    for(var i=0;i<array.length;i++){
        if (array[i]%2==1){
            a.push(array[i])
        }else{
            b.push(array[i])
        }
    }
    return a.concat(b)
}

2）不开辟新数组

1.用两个下标i,j进行遍历;
2.当i走到偶数时停下，并让j从i的后一个元素开始遍历；(若i走到队尾则循环结束)
3.若j所指的是偶数则继续前进，j遇到奇数则停下(如果j都没遇到奇数则在队尾停下，结束。)。
4.此时j所指的是奇数，i所指的是偶数(i到j-1都是偶数)。
5.则可以用临时变量temp保存j对应的值，然后从j-1开始到i，挨个后移一位。
6.将temp保存的值插入到i的位置。

3）优化：

冒泡排序也可以保证相对位置不变，所以用冒泡排序写起来会更方便。