xiaomi

个人博客

小米的个人博客,欢迎交流


今天两道剑指Offer:变态跳台阶/矩形覆盖


Offer0009

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


思路: 找规律!!!

  • 规律一 : 方案数 = 2^(n-1)

    —快速幂计算—

        public int JumpFloorII(int target) {
            if (target <= 1) return 1;
            int res = fastpow(2, target-1);
            return res;
        }
      
        public int fastpow(int a, int b) {
            int res = 1;
            if (b <= 0) return res;
            while (b > 0) {
                if (b % 2 == 1) {
                    res *= a;
                }
                a *= a;
                b >>= 1;
            }
            return res;
        }
    


  • 规律二 :
    | 1 (n=0)
    f(n) = | 1 (n=1)
    | 2*f(n-1) (n>=2)


Offer0010

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


思路:

1、target<=0,1
2、target==1,1
3、target==2,2
4、target==n ->
木块有两种变换的形态->2×1 和 (1×2)×2
—–当使用2×1时
1 0 0 0 有f(target-1)种方案
1 0 0 0
—–当使用(1×2)×2时
11 0 0 有f(target-2)种方案
11 0 0
—–> f(target) = f(target-1) + f(target-2)
——–斐波那契数列规律!!


代码:

斐波那契数列其他的实现方法:快戳我

 public int RectCover(int target) {
        if (target <= 0) return 0;
        if (target == 1) return 1;
        if (target == 2) return 2;
        int[] fib = new int[target + 1];
        fib[0] = 0;
        fib[1] = 1;
        fib[2] = 2;
        for (int i = 3; i <= target; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        return fib[target];
    }