程序员社区

LeetCode-70-爬楼梯??

LeetCode-70-爬楼梯

70. 爬楼梯

难度简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

  1. Climbing Stairs

Easy

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

  • 类似斐波那契数列的递归

F(N)=F(N-1)+F(N-2)

到达第N台阶,可以通过N-1的台阶跨一步,或者N-2的台阶一次性跨两步两种方式完成,所以是斐波那契数列方式

F(N)=F(N-1)+F(N-2)   f(2)=2 f(1)=1
int[][] base = { { 1, 1 }, { 1, 0 } }; 
res = base^(N-2)
F(N)=`2*res[0][0]+ 1*res[1][0]`

时间复杂度可以做到O(longN)

class Solution {
    public static int climbStairs(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int[][] base = { { 1, 1 }, { 1, 0 } };
        int[][] res = matrixPower(base, n - 2);
        return 2 * res[0][0] + res[1][0];
    }
    
    public static int[][] matrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }
        
        // res = 矩阵中的1
        int[][] tmp = m;// 矩阵1次方
        for (; p != 0; p >>= 1) {
            if ((p & 1) != 0) {
                res = muliMatrix(res, tmp);
            }
            tmp = muliMatrix(tmp, tmp);
        }
        return res;
    }

    // 两个矩阵乘完之后的结果返回
    public static int[][] muliMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }
}
LeetCode-70-爬楼梯??插图
image-20210520094551824

斐波那契数列-矩阵求法

矩阵乘法+空间换时间(减少乘法,取模运算)

数列的递推公式为:f(1)=1,f(2)=2,f(n)=f(n-1)+f(n-2)(n>=3)

用矩阵表示为:

LeetCode-70-爬楼梯??插图1
img

进一步,可以得出直接推导公式:

LeetCode-70-爬楼梯??插图2
img

由于矩阵乘法满足结合律,在程序中可以事先给定矩阵的64,32,16,8,4,2,1次方,加快程序的执行时间。(有些题目需要取模运算,也可以事先进行一下)。给定的矩阵次幂,与二进制有关是因为,如下的公式存在解满足Xi={0或1}:

LeetCode-70-爬楼梯??插图3
img

为了保证解满足 Xi={0或1},对上述公式的求解从右向左,即求解顺序为Xn,Xn-1,Xn-2,....,X1,X0。

Pow(x, n)表示就x的n次方的值

LeetCode-70-爬楼梯??插图4
img
public class FibonacciProblem {

    public static int f1(int n) {//暴力递归
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        return f1(n - 1) + f1(n - 2);
    }

    public static int f2(int n) {//线性乘法
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int res = 1;
        int pre = 1;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
            tmp = res;
            res = res + pre;
            pre = tmp;
        }
        return res;
    }

    public static int f3(int n) {//数列矩阵乘法
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        // [ 1 ,1 ]
        // [ 1, 0 ]
        int[][] base = { 
                { 1, 1 }, 
                { 1, 0 } 
                };
        int[][] res = matrixPower(base, n - 2);
        return res[0][0] + res[1][0];
    }

    public static int[][] matrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }
        
        // res = 矩阵中的1
        int[][] tmp = m;// 矩阵1次方
        for (; p != 0; p >>= 1) {
            if ((p & 1) != 0) {
                res = muliMatrix(res, tmp);
            }
            tmp = muliMatrix(tmp, tmp);
        }
        return res;
    }

    // 两个矩阵乘完之后的结果返回
    public static int[][] muliMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }

    public static int s1(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        return s1(n - 1) + s1(n - 2);
    }

    public static int s2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int res = 2;
        int pre = 1;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
            tmp = res;
            res = res + pre;
            pre = tmp;
        }
        return res;
    }

    public static int s3(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int[][] base = { { 1, 1 }, { 1, 0 } };
        int[][] res = matrixPower(base, n - 2);
        return 2 * res[0][0] + res[1][0];
    }
}

扩展问题——奶牛问题

有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。假设第一年就一头老母牛,第二年就2头母牛,第三牛就3头母牛,第四年就4头母牛,第五年就6头。第六年就9头。请编程实现在第n年的时候,共有多少头母牛?

LeetCode-70-爬楼梯??插图5
image-20210520112940341

思路:今年的牛的数目=去年的牛的数目+三年前牛的数目 即:f(n)=f(n-1)+f(n-3)

f(n)=f(n-1)+f(n-3)=1*f(n-1)+0*f(n-2)+1*f(n-3) 最后的递推为1*f(n-3) 表示一个3阶问题

|F(N),F(N-1),F(N-2),| = |F(3),F(2),F(1)| * (|3*3|)^N-3 3*3的矩阵的N-3次方

LeetCode-70-爬楼梯??插图6
image-20210520113954771

计算出a~i

LeetCode-70-爬楼梯??插图7
image-20210520115008809
LeetCode-70-爬楼梯??插图8
image-20210520115710402
public static int c1(int n) {//暴力递归
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        return c1(n - 1) + c1(n - 3);
    }

    public static int c2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        int res = 3;
        int pre = 2;
        int prepre = 1;
        int tmp1 = 0;
        int tmp2 = 0;
        for (int i = 4; i <= n; i++) {
            tmp1 = res;
            tmp2 = pre;
            res = res + prepre;
            pre = tmp1;
            prepre = tmp2;
        }
        return res;
    }

    public static int c3(int n) {//数列矩阵乘法 O(longN)
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        int[][] base = { 
                { 1, 1, 0 }, 
                { 0, 0, 1 }, 
                { 1, 0, 0 } };
        int[][] res = matrixPower(base, n - 3);//乘法可以做到 O(longN)
        return 3 * res[0][0] + 2 * res[1][0] + res[2][0];
    }
继续扩展-又假如每头牛的寿命只有十年,则 f(n)=f(n-1)+f(n-3)-f(n-10) 表示一个10阶问题

爬楼梯-台阶问题

LeetCode-70-爬楼梯

LeetCode-70-爬楼梯??插图9
image-20210520120951454

F(N)=F(N-1)+F(N-2) f(2)=2 f(1)=1

int[][] base = { { 1, 1 }, { 1, 0 } }; res = base^(N-2)

F(N)=2*res[0][0]+ 1*res[1][0]

public static int s1(int n) {//暴力递归 O(2^N)
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        return s1(n - 1) + s1(n - 2);
    }

    public static int s2(int n) {//暴力递归 线性乘法  
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int res = 2;
        int pre = 1;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
            tmp = res;
            res = res + pre;
            pre = tmp;
        }
        return res;
    }

    public static int s3(int n) {//数列矩阵乘法 O(longN)
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int[][] base = { { 1, 1 }, { 1, 0 } };
        int[][] res = matrixPower(base, n - 2);
        return 2 * res[0][0] + res[1][0];
    }

给定一个数N,想象只由0和1两种字符,组成的所有长度为N的字符串,如果某个字符串,任何0字符的左边都有1紧挨着,认为这个字符串达标
返回有多少达标的字符串!

  • 暴力解

N个长度由0|1组成的字符串的个数 2^N次方个 检验是否有效O(N) 所以总的时间复杂度 O(2^N * N)

  • 斐波那契数列-矩阵求法
LeetCode-70-爬楼梯??插图10
image-20210520124307949
LeetCode-70-爬楼梯??插图11
image-20210520124445054

所以F(N) = F(N-1)+F(N-2) 斐波那契数列求解 F(1)=1 F(2) = 2

LeetCode-70-爬楼梯??插图12
image-20210520125623122
赞(0) 打赏
未经允许不得转载:IDEA激活码 » LeetCode-70-爬楼梯??

一个分享Java & Python知识的社区