《剑指Offer》题目解析（4）

题目1 斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

代码

递归方法：

int Fibonacci(int n) {
    if(n==0)
        return 0;
    if(n==1||n==2)
        return 1;
    return Fibonacci(n-1)+Fibonacci(n-2);

}

非递归方法：

int Fibonacci(int n) {
        int first = 0;
        int second = 1;

        int result = n;
        for(int i = 2; i<=n; i++){
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }

题目2 青蛙跳台阶

题目描述

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

题目解析

对于这种问题我们可以这样分析。在第一次跳台阶的时候，它可以选择跳1个台阶，也可以选择跳两个台阶。对于它要跳n个台阶来说（设为f(n)），假如第一次跳了1个台阶，那么第二次跳就是f(n-1)的问题；假如第一次跳了2个台阶，那么第二次就是f(n-2)的问题。对于第二次跳也是如此，就是分别是f(n-2)和f(n-3)（对于第一次跳了1阶的情况下）、f(n-3)和f(n-4)（对于第一次跳了2阶的情况下），依次类推下去，成为一个递归。特别的，当n=1的时候，只有一种跳法（只跳一阶），当n=2的时候，有两种跳法（跳1阶跳两次，跳2阶跳一次）。实际上这就是一个斐波那契数列。

代码

int jumpFloor(int number) {
        if(number==1)
            return 1;
        else if(number==2)
            return 2;
        else
            return jumpFloor(number-1)+jumpFloor(number-2);  
    }

题目3 变态跳台阶

题目描述

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

题目解析

当一个青蛙跳上n级台阶有以下的情况：

通过尝试，可以发现规律，当n>1的时候，f(n)=2*f(n-1)。

代码

 int jumpFloorII(int number) {
     if(number<1)
         return -1;
     else if(number==1)
         return 1;
     else
         return 2*jumpFloorII(n-1);
 }

题目4 矩形覆盖

题目描述

我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

题目解析

对于这种问题，我们还是需要进行分析。

当n=3的时候，我们发现，若固定了第三块砖的放置方式，那么前两块砖有两种放置方式（f(2)）；若固定了第二块和第三块的放置方式，则前一块砖有一种放置方式（f(1)）。以此类推，可以得出f(n)=f(n-1)+f(n-2)，当n>2的时候。

代码

int rectCover(int number) {
    if(number<=0)
        return 0;
    else if(number==1)
        return 1;
    else if(number==2)
        return 2;
    else
        return rectCover(number-1)+rectCover(number-2);
}

题目5 二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

题目解析

思路很简单，利用与的特性：1&1=1，0&1=0就可以进行判断。

代码

 int  NumberOf1(int n) {
     int count=0;
     for(int i=0;i<32;i++)
     //32位是由int决定
     {
         if((n>>i)&1)
             count++;
     }
     return count;
 }

题目6 调整数组，使奇数位于偶数前面

题目描述

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

题目解析

其实这个可以借助于类似于冒泡法的思想，不过这样的复杂度有O(n²)，并且空间复杂度也较高。因此可以使用下面的方法。借鉴了插入排序。

代码

void reOrderArray(vector<int> &array) {
        for(int i = 0;i < array.size();i++){
            for(int j = array.size()-1; j>i;j--){
                if(array[j]%2==1&&array[j-1]%2==0)
                    swap(array[j],array[j-1]);
            }
        }
    }