936 2018-11-12 2020-06-25

前言：牛客网剑指Offer编程题7~12题。

一、斐波那契数列

1、题目描述

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

2、我的代码

static class Seven {

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

3、别人的代码

public int Fibonacci1(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int a = 0, b = 1;
    int c = 0;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

如果递归深度较大，则循环比递归好。

4、python二刷

def Fibonacci(self, n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    i = 3
    a, b, c = 1, 1, 2
    while i < n:
        a = b
        b = c
        c = a + b
        i += 1
    return c

二、跳台阶

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

public int JumpFloor(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1, b = 2;
        int c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
}

这题是上一题的一个变种，关键是理解要跳到n，那么只需考虑到跳到n - 1和n - 2，剩下的都是确定的。

三、变态跳台阶

1、题目描述

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

2、我的代码

public int JumpFloorII(int target) {
        public int JumpFloorII(int target) {
            if (target <= 0) {
                return 0;
            }
            int c = 1;
            for (int i = 1; i < target; i++) {
                c *= 2;
            }
            return c;
        }
}

我是观察出来的，没证明出来。但其实有个公式。推导过程如下

因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级。如果跳1级，剩下n-1级，则剩下跳法是f(n-1)；如果 跳2级，剩下n-2级，则剩下跳法是f(n-2)。

所以f(n) = f(n - 1) + f(n - 2) + ... + f(1)。

因为f(n - 1) = f(n - 2) + f(n - 3) + ... + f(1)。

所以f(n) = 2 * f(n - 1)。

四、矩形覆盖

1、题目描述

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

2、我的代码

这题关键是理解，把它看成是那个跳台阶的问题就好了。

static class Ten {
    public int RectCover(int target) {
        if (target <= 0) {
            return 0;
        }
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= target; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

五、二进制中1的个数

1、题目描述

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

2、我的代码

// 屌丝版本
static class Eleven {
    public int NumberOf1(int n) {
        int count = 0;
        String str = Integer.toBinaryString(n);
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                count++;
            }
        }
        return count;
    }

    private static void test() {
        int c = new Eleven().NumberOf1(100);
        Assert.assertEquals(3, c);
    }
}

3、别人的代码

// 大神解法，我等渣渣看看就好
public int NumberOf1(int n) {
    int count = 0;
    while(n!= 0){
        count++;
        n = n & (n - 1);
     }
    return count;
}

// 下面是一个比较容易理解的办法，但不能处理n为负数的情况
public int NumberOf11(int n) {
    int count = 0;
    while (n != 0) {
        if ((n & 1) == 1) {
            count++;
        }
        n = n >> 1;
    }
    return count;
}

4、python二刷

# 个人觉得这个解法比较实在，但貌似效率不是很好
def NumberOf1(self, n):
    count = 0
    while n != 0:
        if n % 2 != 0:
            count += 1
        n = n >> 1
    return count

六、数值的整数次方

1、题目描述

考点代码的完整性，给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

2、我的代码

static class Twelve {
    public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        double result = 1;
        int times = exponent > 0 ? exponent : - exponent;
        for (int i = 1; i <= times; i++) {
            result *= base;
        }
        if (exponent > 0) {
            return result;
        } else {
            return 1 / result;
        }
    }
}

一天6道题，完工。

总访问次数: 272次, 一般般帅 创建于 2018-11-12, 最后更新于 2020-06-25