logo头像

不忘初心,奋力前行

《剑指Offer》题目解析(4)

本文于436天之前发表,文中内容可能已经过时,如有问题,请联系我。

题目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

1

(1)

2

2

(1,1),(2)

3

4

(1,1,1),(1,2),(2,1),(3)

4

8

(1,1,1,1),(1,2,1),(1,1,2),(2,1,1),(2,2),(1,3),(3,1),(4)

……

……

……

n

2*f(n-1)

(1)

通过尝试,可以发现规律,当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

情况数

情况(括号中1为竖着,2为横着)

1

1

(1)

2

2

(1,1),(2,2)

当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(n2),并且空间复杂度也较高。因此可以使用下面的方法。借鉴了插入排序。

代码

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]);
            }
        }
    }
支付宝打赏 微信打赏 QQ钱包打赏

感觉不错?欢迎给我 打个赏~我将不胜感激!