当前位置：首页 > news >正文

剑指offer专项 97-100笔记

news 来源：原创 2024/5/22 2:32:28

剑指 Offer II 097. 子序列的数目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。
在这里插入图片描述

动态规划

s父串要生成子串t
如果父串长度小于子串长度，那么不可能生成
在这里插入图片描述
如果子串为空，那么父串只需要删除自身就能生成，且只有删除自身这一种方式

如果新添加一个元素，这个元素可以是横向添加的一个，也可以是列向添加的一个，但不管横向还是列向添加，都表示父类添加了这个元素
如果这个新添加的元素，行列相同，那么有两种选择
1、父串舍弃这个元素，如下图的横向箭头，也就是我选择不要这个元素
2、父串和子串都舍弃这个元素，如下图的斜箭头，父类和子类都不要这个元素
在这里插入图片描述
如果这个新添加的元素不同

python版本
在这里插入图片描述
以下图为例，每一行的两个元素生成下一个元素，而最终结果只是求最右下角的值，那么二维数组可以只用一行的一维数组表示，每次一维数组保存上一行的数据，然后逐渐修改下一行的数据

剑指 Offer II 098. 路径的数目

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
在这里插入图片描述
输入：m = 3, n = 7
输出：28

动态规划，类似爬楼梯

在这里插入图片描述

节省空间，使用滚动的二维数组

在这里插入图片描述
如上图所示，仅用2*m就可以，如果再节省一点，让m为n和m中小的那个

 if (m < n) return uniquePaths(n, m);

再节省空间，使用一维数组

在这里插入图片描述

剑指 Offer II 099. 最小路径之和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：一个机器人每次只能向下或者向右移动一步。
在这里插入图片描述

动态规划

对于当前步，有从上面来的和从左边来的，两个选最小的加上当前的花费
和爬楼梯花费最小体力一样
在这里插入图片描述

代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
       
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));

        dp[0][0] = grid[0][0];
        for (int j = 1; j < grid[0].size(); ++j) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }

        for (int i = 1; i < grid.size(); ++i) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
            for (int j = 1; j < grid[0].size(); ++j) {
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
            }
        }
        return dp[grid.size() - 1][grid[0].size() - 1];
    }
};

抽象成一维数组的代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        vector<int> dp(grid[0].size());

        dp[0] = grid[0][0];
        for (int j = 1; j < grid[0].size(); ++j) {
            dp[j] = grid[0][j] + dp[j - 1];
        }

        for (int i = 1; i < grid.size(); ++i) {
            dp[0] = grid[i][0] + dp[0];
            for (int j = 1; j < grid[0].size(); ++j) {
                dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
            }
        }
        return dp[grid[0].size() - 1];
    }
};

剑指 Offer II 100. 三角形中最小路径之和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。