剑指offer三五题-2

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

题解

跳到n级台阶的跳法等于跳到n-1级台阶和n-2级台阶的跳法之和。

递归解法

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 2){
            return target;
        }
        return JumpFloor(target-1) + JumpFloor(target-2);
    }
}

动态规划解法

public class Solution {
    public int JumpFloor(int target) {
        int ans[] = new int[target+1];
        ans[0] = ans[1] = 1;

        for(int i=2; i<=target; i++){
            ans[i] = ans[i-1]+ans[i-2];
        }
        return ans[target];
    }
}

优化存储,动态规划解法

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 2){
            return target;
        }
        int sum = 0;
        int n_minusone = 2;
        int n_minustwo = 1;
        for(int i=3; i<=target; i++){
            sum = n_minusone + n_minustwo;
            n_minustwo = n_minusone;
            n_minusone = sum;
        }
        return sum;
    }
}

题目描述

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

题解

令该青蛙跳上一个n阶的台阶的跳法为$f(n)$,则有

$$f(n) = f(n-1)+f(n-2)+…+f(2)+f(1)$$

$$f(n-1) = f(n-2)+…+f(2)+f(1)$$

两式相减得,

$$f(n) =2* f(n-1)$$

要么用动态规划

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

要么用等比数列通项公式

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

题目描述

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

比如n=3时,2*3的矩形块有3种覆盖方法。

题解

当$n>=3$时,覆盖方法等于最后一块矩形竖着和最后一块矩形横着(最后一块矩形横着等价于最后两块矩形横着),故覆盖2 * n的大矩形的方法数等于覆盖2 * (n-1)的大矩形的方法数加上覆盖2 * (n-2)的大矩形的方法数。

动态规划:

public class Solution {
    public int RectCover(int target) {
        if(target<=2){
            return target;
        }

        int pre2 = 1;
        int pre1 = 2;
        int cur = 0;
        for(int i=3; i<=target; i++){
            cur = pre2 + pre1;
            pre2 = pre1;
            pre1 = cur;
        }
        return cur;
    }
}

题目描述

输入一个整数,输出该数32位二进制表示中1的个数。其中负数用补码表示。

题解

将一个数与其减一的结果相与,就会消除其最右端的一个1。如1100与1011,得到1000。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n!=0){
            count++;
            n = n&(n-1);
        }
        return count;
    }
}

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

题解

public class Solution {
    public double Power(double base, int exponent) {
        if(exponent<0){
            base = 1/base;
            exponent = -exponent;
        }
        double total = 1.0d;
        if(exponent>0){
            for (; exponent >=1 ; exponent--) {
                total *=base;
            }

        }
        return total;
  }
}

   转载规则


《剑指offer三五题-2》 帅张 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录