剑指Offer-递归和循环

2017/3/11 posted in  算法-数据结构  

求斐波那契额

这个题目非常简单,2分钟就可以解决。直接上代码!

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

但是,这个解法有很多的问题。当n的值比较大的时候,就会出现栈调用溢出。所以,我们一般在条件允许的情况下,使用循环来替代递归的实现。

public class Solution {
    public int Fibonacci(int n) {
        if(n <= 1){
            return n;
        }
        int number1 = 0;
        int number2 = 1;
        int ans = 0;
        for(int i = 2;i<=n;i++){
            ans = number1 + number2;
            number1 = number2;
            number2 = ans;
        } 
        return ans;
    }
}

跳台阶

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

思路

首先我们考虑最简单的情况。如果只有1级台阶,那显然只有一种跳法。如果有2级台阶,那就有两种跳的方法了:一种是分2次跳,每次跳1级;另外一种就是一次跳2级。
接着我们再来讨论一般情况,我们把n级台阶时的跳法看成是n的函数,记为f(n)。当n>2时,第一次跳的时候就有两种不同的选择:一是一次跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);另一种跳法是一次跳2级,这是跳法数目就是后面剩下n-2级台阶的跳法数目,即f(n-2)。因此n级台阶的跳法数目f(n) = f(n-1) + f(n - 2);

代码

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 2){
            return target;
        }
        int number1 = 1;
        int number2 = 2;
        int ans = 0;
        for(int i = 3;i<=target;i++){
            ans = number1 + number2;
            number1 = number2;
            number2 = ans;
        }
        return ans;
    }
}

变态跳台阶

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

思路

借鉴上面的思路,我们把n级台阶时的跳法看成是n的函数,记为f(n)。此时f(n) = f(n-1) + f(n-2) + ...+ f(1) + 1;经过数学推导可得:f(n) = 2n-1;

代码

public class Solution {
    public int JumpFloorII(int target) {
        return 1 << target-1;
    }
}

矩形覆盖

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

思路

既然放在这个章节,自然是递推解决。当我们使用一个1*2的矩形去覆盖大矩形(2*n)的左侧时,我们有两个选择,横着放或者竖着放。当竖着放时,右边剩下的区域长度就为n-1;当横着放时,左边剩下的区域长度就为n-2。所以可以发现f(n) = f(n-1) + f(n-2)

代码

public class Solution {
    public int RectCover(int target) {
        if(target <=2){
            return target;
        }
        int number1 = 1;
        int number2 = 2;
        int ans = 0;
        for(int i = 3;i <= target;i++){
            ans = number1 + number2;
            number1 = number2;
            number2 = ans;
        }
        return ans;
    }
}