剑指 Offer 10- II. 青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题

1.结果

执行结果:通过显示详情>

执行用时:0 ms ，在所有Java提交中击败了100.00%的用户

内存消耗:38.4 MB ，在所有Java提交中击败了38.79%的用户

通过测试用例:51/51

2.时间花费

跨了一整天，主要集中在，数学方法上的“（m+n）个球放（m+n）个位置上有多少种组合”和约分操作（没成功）上

3.思路

• 思路一：纯数学方法

  m + 2n = N, 因此有m个1和n个2；
  m个白球和n个红球有多少种排列组合方式

  也转换为（m+n）个球放（m+n）个位置上有多少种组合
  完那m个白球，剩下的n个红球也就确定了

  总而言之，此时有$C_{(}^{n}m+n)$种排列方式
  模的问题：(a∗b)%c=((a%c)∗(b%c))%c，但除法不适用，未解决这部分

• 思路二：动态规划

  每次只会跳一阶或者二阶，因此，可以看成前面组合再加上在倒数第一阶跳一阶台阶和在倒数第二阶跳二阶的情况。

  设F(n)为蛤蟆跳n阶台阶的跳法，故

  F(n) = F(n-1) + “跳一阶”

  ​ + F(n-2) + “跳二阶”

  即：F(n) = F(n-1) + F(n-2)

  F(n-1) + “跳一阶”：F(n-1)是确定的，再跳一阶，跳的排列数不会变。后面同理。

4.code

4.1 code1

    /**
     * 剑指 Offer 10- II. 青蛙跳台阶问题
     * 

     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n级的台阶总共有多少种跳法。
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     */
    public int numWays(int n) {
        /**
         * 两种思路
         * 思路一：纯数学方法
         * m + 2n = N, 因此有m个1和n个2；
         * 转换为m个白球和n个红球有多少种排列组合方式
         * 也转换为（m+n）个球放（m+n）个位置上有多少种组合
         * 只要放完那m个白球，剩下的n个红球也就确定了
         * 总而言之，此时有$C^n_(m+n)$种排列方式
         * 答案取模的问题：(a∗b)%c=((a%c)∗(b%c))%c，除法不适用
         *
         */
        int re = 0;
        for (int i = 0; i < n; i++) {
            int oneNum = n - i * 2;
            re = (re + computeC(oneNum, i)) % 1000000007;
        }
        return re;

      
    }


    /**
     * 搞不定约分的操作
     */
    public int computeC(int oneNum, int twoNum) {
        int top = Math.min(oneNum, twoNum);
        int re = 1;
        int[] divideNum = new int[top];
        int count = 1; //记录有多少个被约分了
        for (int i = 0; i < top; i++) {
            divideNum[i] = i + 1;
        }

        for (int i = oneNum + twoNum; i > (oneNum + twoNum - top); i--) {
            // re = re * i % 1000000007;
            int t1 = re * i;
            if (t1 < 0) {
                //说明超过了100000007，所以先约分
                for (int j = 0; j < top && count < top; j++) {
                    double t2 = re * 1.0 / divideNum[j];
                    if (t2 != (int) t2) {
                        continue;
                    }
                    re = (int) t2;
                    System.out.println(oneNum + "\t" + twoNum + "\t" + re + "\t" + divideNum[j]);
                    divideNum[j] = 1;
                    count++;
                }
            } else {
                //没超过100000007
                re = t1;
            }


        }
        // System.out.println(oneNum + "\t" + twoNum + "\t" + re);
        while (count <= top) {
            for (int i = 0; i < top; i++) {
                double t3 = re * 1.0 / i;
                if (t3 != (int) t3) {
                    continue;
                }
                re = (int) t3;
                count++;
            }
        }

        System.out.println(oneNum + "\t" + twoNum + "\t" + re);
        return re;
    }
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

4.2 code2

public int numWays(int n) {

        /**
         * 思路二：动态规划
         * 每次都看成是前n-1阶台阶和第n阶台阶两部分来做
         */
        if (n == 0) return 1;
        else if (n == 1) return 1;
        else if (n == 2) return 2;
        else {
            int a = 1, b = 2;
            int c = 0;
            for (int i = 3; i <= n; i++) {
                c = (a + b) % 1000000007;
                a = b;
                b = c;
            }
            return c;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21