不忘初心

人啊,总是容易忘记何为根本.

0%

剑指offer(7)——递归和循环（共4道题目）

发表于 更新于 分类于 Valine：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

参考资料：

剑指offer题目汇总

递归和循环（共4道题目）

模板：

　　题目描述：

　　解题思路：

　　注意问题：

　　补充知识点：

7、斐波那契数列（10.07）*

8、跳台阶（10.08）*

9、变态跳台阶（10.09）

10、矩形覆盖（10.10）

补充：12、剪绳子（11.03）

9、变态跳台阶

　　题目描述：

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

　　解题思路：

  当只有一级台阶时，f(1)=1；当有两级台阶时，f(2)=f(2-1)+f(2-2)；一般情况下，当有n级台阶时，f(n)=f(n-1)+f(n-2)+···+f(n-n)=f(0)+f(1)+···+f(n-1)，同理，f(n-1)=f(0)+f(1)+···+f(n-2).

  因此，根据上述规律可以得到：f(n)=2*f(n-1)。这时一个递推公式，同样为了效率问题，用循环可以实现。

　　注意问题：

　　补充知识点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//java
//递归实现
public class Solution {
    public int JumpFloorII(int target) {
        if(target==1)
            return 1;
        return JumpFloorII(target-1)*2;
    }
}
//循环实现
   public int JumpFloorII(int target) {
        if(target<=0)
            return 0;
        if(target==1)
            return 1;
        int res=1;
        for(int i=2;i<=target;i++)
           res=2*res;
        return res;
    }

10、矩形覆盖

　　题目描述：

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

　　解题思路：斐波那契数列变形；f(1)=1,f(2)=2;f(n)=f(n-1)+f(n-2);先把2X8的覆盖方法记为f(8)，用1X2的小矩形去覆盖时，有两种选择：横着放或者竖着放。当竖着放时，右边还剩下2X7的区域。很明显这种情况下覆盖方法为f(7)。当横着放时，1X2的矩形放在左上角，其下方区域只能也横着放一个矩形，此时右边区域值剩下2X6的区域，这种情况下覆盖方法为f(6)。所以可以得到：f(8)=f(7)+f(6)，不难看出这仍然是斐波那契数列。

　　注意问题：

　　1.要注意target<=0情况的讨论；

　　2.深入理解递归和迭代；

　　补充知识点：递归和迭代；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//迭代
public class Solution {
    public int RectCover(int target) {
        if(target==1)
            return 1;
        if(target==2)
            return 2;
        int f1=1,f2=2,f3=0;//target的测试用例有<=0的情况，所以f3=0；
        int i;
        for(i=3;i<=target;i++)
        {
            f3=f1+f2;
            f1=f2;
            f2=f3;
        }
        return f3;
    }
}
//递归
public class Solution {
    public int RectCover(int target) {
        if(target<=0)////target的测试用例有<=0的情况，所以要判断target的<=0的情况；
            return 0;
        if(target==1)
            return 1;
        if(target==2)
            return 2;
        return RectCover(target-2)+RectCover(target-1);
    }
}

12、剪绳子

　　题目描述：

　　给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

　　解题思路：

动态规划：不同的target会有相同的子问题，比如：target=6/7/8都有target=4这个公共子问题。所以先把子问题的值都求出来存放在一个数组里。（重叠子问题性质、最优子结构性质）注意：当子问题分到2/3时，其实不划分才是最好的选择，所以作为子问题，其存在数组中的值应该是2/3，而不是1/2。但当我们要输出target=2/3时，其实应该输出1/2。当子问题大于3时，划分后的乘积总会比原问题大，所以数组中存的值就是target的最优值。

贪心：尽可能多分3，3不满足时尽量多分2，不要分1；证明：当length>=5的时候，任何数都可以分解为加数2和3的和，且2(length-2)>length,3(length-3)>length，所以可以将length分解为全为2,3的加数再相乘就是结果，又注意到3(length-3)>2(length-2)，所以尽可能将length分解为加数3。特殊的，当length=4的时候，13<22=4，所以length=4的时候不用再分。

　　注意问题：

　　补充知识点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//动态规划
public class Solution {
    public int cutRope(int target) {
        int i;
        int a[]=new int[target+1];
        a[2]=2;
        a[3]=3;
        a[4]=4;
        int max=0;
        for (i=5;i<=target;i++)
        {
            int j;
            for (j=2;j<=i/2;j++)
            {
                if (max<a[j]*a[i-j])
                    max=a[j]*a[i-j];
            }
            a[i]=max;
        }
        a[2]=1;
        a[3]=2;
        a[4]=4;
        return a[target];
    }
}
//贪心
import java.lang.Math;
public class Solution {
    public int cutRope(int target) {
        if (target==2)
            return 1;
        if (target==3)
            return 2;
        if (target==4)
            return 4;
        if (target % 3==0)
            return (int)Math.pow(3,target/3);
        if (target%3==1)
            return (int)Math.pow(3,target/3-1)*4;
        if (target%3==2)
            return (int)Math.pow(3,target/3)*2;
        return 0;
    }
}