第9周

2021-11-20

6分钟阅读时长

第9周第19课 | 高级动态规划

1. 动态规划、状态转移方程串讲

参考链接

70.爬楼梯

class Solution {

    /**
     * 动态规划解法
     * Binets 方法 和 斐波那契公式 时间复杂度为O(log(N))
     * @param Integer $n
     * @return Integer
     */
    function climbStairs($n) {
        if ($n <= 2) return $n;
        $first = 1;
        $second = 2;
        for ($i = 3; $i <= $n; $i++) {
            $tmp = $first + $second;
            $first = $second;
            $second = $tmp;
        }
        return $second;
    }
}

//斐波那契公式
public class Solution {
    public int climbStairs(int n) {
        double sqrt5=Math.sqrt(5);
        double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
        return (int)(fibn/sqrt5);
    }
}

public class Solution {
   public int climbStairs(int n) {
       int[][] q = {
          {1, 1}, 
          {1, 0}
       };
       int[][] res = pow(q, n);
       return res[0][0];
   }
   public int[][] pow(int[][] a, int n) {
       int[][] ret = {
            {1, 0}, {0, 1}
        };
       while (n > 0) {
           if ((n & 1) == 1) {
               ret = multiply(ret, a);
           }
           n >>= 1;
           a = multiply(a, a);
       }
       return ret;
   }
   public int[][] multiply(int[][] a, int[][] b) {
       int[][] c = new int[2][2];
       for (int i = 0; i < 2; i++) {
           for (int j = 0; j < 2; j++) {
               c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
           }
       }
       return c;
   }
}

62.不同路径

class Solution {
    /**
     * 自顶向下dp
     * dp方程dp[i, j] = dp[i-1, j] + dp[i, j-1]
     * @param Integer $m
     * @param Integer $n
     * @return Integer
     */
    function uniquePaths($m, $n) {
        $dp = [];
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($i == 0 || $j == 0) {
                    $dp[$i][$j] = 1;
                } else {
                    $dp[$i][$j] = $dp[$i - 1][$j] + $dp[$i][$j - 1];
                }
            }
        }
        return $dp[$m - 1][$n - 1];
    }
}

63. 不同路径 II

一维dp写法

class Solution {

    /**
     * 自顶向下dp
     * 
     * @param Integer[][] $obstacleGrid
     * @return Integer
     */
    function uniquePathsWithObstacles($obstacleGrid) {
        $m = count($obstacleGrid);
        $n = count($obstacleGrid[0]);
        if ($obstacleGrid[0][0] == 1)  return 0;
        $dp = [[1]];
        //初始化第一行
        for ($i = 1; $i < $n; $i++) {
            $dp[0][$i] = $obstacleGrid[0][$i] ? 0 : $dp[0][$i - 1];
        }
        //初始化第一列
        for ($i = 1; $i < $m; $i++) {
            $dp[$i][0] = $obstacleGrid[$i][0] ? 0 : $dp[$i - 1][0];
        }
        for ($i = 1; $i < $m; $i++) {
            for ($j = 1; $j < $n; $j++) {
                if ($obstacleGrid[$i][$j] == 1) {
                    $dp[$i][$j] = 0;
                } else {
                    $dp[$i][$j] = $dp[$i - 1][$j] + $dp[$i][$j - 1];
                }
            }
        }
        return $dp[$m - 1][$n - 1];
    }
}

198.打家劫舍

class Solution {

    /**
     * 二维dp
     * dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) 不偷
     * dp[i][1] = dp[i - 1][0] + nums[i] 偷
     * @param Integer[] $nums
     * @return Integer
     */
    function rob1($nums) {
        if (!$nums) return 0;
        $dp = [];
        $dp[0][0] = 0;
        $dp[0][1] = $nums[0];
        $n = count($nums);
        for ($i = 1; $i < $n; $i++) {
            $dp[$i][0] = max($dp[$i - 1][0], $dp[$i - 1][1]);
            $dp[$i][1] = $dp[$i - 1][0] + $nums[$i];
        }
        return max($dp[$n - 1]);
    }
    //一维dp[i] = max($dp[$i - 1], $dp[$i - 1] + $nums[$i]) 第 i 天偷 的金额
    function rob2($nums) {
        if (!$nums) return 0;
        $n = count($nums);
        if ($n == 1) return $nums[0];
        $dp = [];
        $dp[0] = $nums[0];
        $dp[1] = max($nums[0], $nums[1]);
        for ($i = 2; $i < $n; $i++) {
            $dp[$i] = max($dp[$i - 1], $dp[$i - 2] + $nums[$i]);
        }
        return $dp[$n  - 1];
    }

    function rob($nums) {
        $preMax = $curMax = 0;
        foreach($nums as $num) {
        	$tmp = $curMax;
            $curMax = max($preMax + $num, $curMax);
            $preMax = $tmp; 
        }
        return $curMax;
    }
}

64.最小路径和

class Solution {

    /**
     * 二维 dp
     * @param Integer[][] $grid
     * @return Integer
     */
    function minPathSum1($grid) {
        $m = count($grid);
        if ($m == 0) return 0;
        $n = count($grid[0]);
        $dp = [];
        $dp[0][0] = $grid[0][0];
        //初始化第一行
        for ($i = 1; $i < $n; $i++) {
            $dp[0][$i] = $dp[0][$i - 1] + $grid[0][$i];
        }
        for ($i = 1; $i < $m; $i++) {
            $dp[$i][0] = $dp[$i - 1][0] + $grid[$i][0];
            for ($j = 1; $j < $n; $j++) {
                $dp[$i][$j] = min($dp[$i - 1][$j], $dp[$i][$j - 1]) + $grid[$i][$j];
            }
        }
        return $dp[$m - 1][$n - 1];
    }

    /**
     * 一维 dp
     * @param Integer[][] $grid
     * @return Integer
     */
    function minPathSum($grid) {
        $m = count($grid);
        if ($m == 0) return 0;
        $n = count($grid[0]);
        $dp = [];
        $dp[0] = $grid[0][0];
        //初始化第一行
        for ($i = 1; $i < $n; $i++) {
            $dp[$i] = $dp[$i - 1] + $grid[0][$i];
        }
        for ($i = 1; $i < $m; $i++) {
            $dp[0] = $dp[0] + $grid[$i][0];
            for ($j = 1; $j < $n; $j++) {
                $dp[$j] = min($dp[$j], $dp[$j - 1]) + $grid[$i][$j];
            }
        }
        return $dp[$n - 1];
    }
}

121.股票买卖

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $dpi0 = 0;
        $dpi1 = -$prices[0];
        for ($i = 0; $i < count($prices); $i++) {
            //卖出
            $dpi0 = max($dpi0, $dpi1 + $prices[$i]);
            //买入
            $dpi1 = max($dpi1, -$prices[$i]);
        }
        return $dpi0;
    }
}

课后作业

在第 9 周学习总结中，写出63. 不同路径 II 这道题目的状态转移方程。

2. 高级动态规划题目详解

参考链接

70.爬楼梯

746.使用最小花费爬楼梯

72.编辑距离

课后作业

300. 最长上升子序列

91. 解码方法

32. 最长有效括号

85. 最大矩形

115. 不同的子序列

818. 赛车

第9周第20课 | 字符串算法

1. 字符串基础知识和引申题目

参考链接

不可变字符串

Atoi 代码示例

字符串基础问题

709. 转换成小写字母

58. 最后一个单词的长度

771. 宝石与石头

387. 字符串中的第一个唯一字符

8. 字符串转换整数 (atoi)

字符串操作问题

14. 最长公共前缀

344. 反转字符串

541. 反转字符串 II

151. 翻转字符串里的单词

557. 反转字符串中的单词 III

917. 仅仅反转字母

异位词问题

242. 有效的字母异位词

49. 字母异位词分组

438. 找到字符串中所有字母异位词

回文串问题

125. 验证回文串

680. 验证回文字符串 Ⅱ

5. 最长回文子串

2. 高级字符串算法

最长子串、子序列问题

1143. 最长公共子序列

72. 编辑距离

5. 最长回文子串

字符串 +DP 问题

10. 正则表达式匹配

题解：https://leetcode-cn.com/problems/regular-expression-matching/solution/ji-yu-guan-fang-ti-jie-gen-xiang-xi-de-jiang-jie-b/

44. 通配符匹配

115. 不同的子序列

3. 字符串匹配算法

参考链接

Boyer-Moore 算法

Sunday 算法

字符串匹配暴力法代码示例

public static int forceSearch(String txt, String pat) {
    int M = txt.length();
    int N = pat.length();

    for (int i = 0; i <= M - N; i++) {
        int j;
        for (j = 0; j < N; j++) {
            if (txt.charAt(i + j) != pat.charAt(j))
                break;
        }
        if (j == N) {
            return i;
        }
        // 更加聪明？ 
        // 1. 预先判断 hash(txt.substring(i, M)) == hash(pat)
        // 2. KMP 
    }
    return -1;
}