重生之我要当分子

分类

题解(3)

/ 注册

全部文章（共295篇）

题解 | 信封嵌套

解题思路这是一个二维的最长递增子序列()问题，可以通过以下步骤解决：首先对信封按照宽度升序排序，当宽度相同时按照长度降序排序这样排序后，我们只需要在长度上找最长递增子序列使用二分查找优化的算法：维护一个数组，表示长度为的递增子序列的最小结尾值对于每个数，二分查找它在中...

2024-12-23

0 38

题解 | 环形数组的连续子数组最大和

解题思路这是最大子数组和的变种，需要考虑环形的情况。可以通过以下思路解决：环形数组的最大子数组和有两种可能：不跨越边界的普通最大子数组和（使用算法）跨越边界的最大子数组和（等于总和减去最小子数组和）对于跨越边界的情况：总和减去中间的最小子数组和相当于首尾相连的部分特...

2024-12-23

0 85

题解 | 连续子数组的最大乘积

解题思路这是一个动态规划问题，但需要同时维护最大值和最小值，因为：当遇到负数时，最小值乘以负数可能变成最大值当遇到正数时，最大值乘以正数仍然是最大值当遇到0时，需要重新开始计算具体步骤：维护两个数组：和表示以结尾的子数组的最大乘积表示以结尾的子数组的最小乘积...

2024-12-23

0 59

题解 | 打家劫舍(二)

解题思路这是打家劫舍问题的变种，房屋首尾相连形成环形。可以通过以下步骤解决：由于首尾相连，我们可以将问题拆分为两种情况：偷第一家，不能偷最后一家（考虑的房屋）不偷第一家，可以偷最后一家（考虑的房屋）对于每种情况，使用动态规划求解：表示到第个房屋时能偷到的最大金额 ...

2024-12-23

0 24

题解 | 删除相邻数字的最大分数

解题思路这是一个动态规划问题，可以通过以下步骤解决：首先统计每个数字出现的次数对于每个数字，如果我们选择了它：会得到的分数会删除所有的和不能选择和因此可以用数组记录到当前数字为止能获得的最大分数表示考虑到数字时能获得的最大分数代码 c++...

2024-12-22

0 41

题解 | 龙与地下城游戏问题

解题思路这是一个动态规划问题，但需要从终点往起点推导：创建一个数组，表示到达位置时需要的最小血量从右下角开始，逆向推导到左上角对于每个位置：如果是终点，则否则，最终就是所需的最小初始血量代码 c++ java python #includ...

2024-12-22

0 43

题解 | 计算字符串的编辑距离

解题思路编辑距离是一个经典的动态规划问题，我们可以通过以下步骤解决：创建一个的二维数组，其中和分别是两个字符串的长度表示字符串1的前个字符转换到字符串2的前个字符所需的最小操作数对于每个位置，我们有三种可能的操作：替换：删除：插入：代码 c+...

2024-12-22

0 67

题解 | 最大子矩阵

解题思路这是一个二维最大子数组和的问题，可以通过以下步骤解决：对于每一对可能的行（），我们计算这些行之间每一列的元素和将二维问题转化为一维问题：把到行的每一列的和看作一个一维数组对这个一维数组求最大子数组和（使用算法）遍历所有可能的行对，找到最大的和代码 c++ ...

2024-12-22

1 48

题解 | 买卖股票的最好时机(四)

解题思路这是股票买卖的通用版本，需要处理k次交易。我们可以使用动态规划来解决：创建二维dp数组：表示第天进行次交易的最大收益其中范围是，范围是对于每一天和交易次数，我们有两种选择：不进行交易：沿用前一天的收益进行交易：在之前某一天买入，第i天卖出优化空间复杂度：使用...

2024-12-22

0 60

题解 | 买卖股票的最好时机(三)

解题思路这道题是股票买卖的进阶版本，最多允许两次交易。我们可以使用动态规划来解决：对于每一天，我们有以下几种状态：第一次买入（）第一次卖出（）第二次买入（）第二次卖出（）对于每个状态，我们都记录到当前天为止的最大收益状态转移方程：代码 c++ ja...

2024-12-22

0 52