摸鱼学大师

题解

未归档(8)

/ 注册

全部文章 / 题解（共84篇）

题解 | #牛妹的面试# 来自专栏

思路：题目的主要信息：凸子序列：对于子序列中的,使得所有单调递增或单调递减序列也算凸序列单独一个数是长度为1的凸序列序列数大于0，不用考虑特殊情况求一个序列中的最长凸子序列长度其实这就是两个最长递增子序列问题的叠加，从左往右是找一个最长递增子序列，从右往左也是找一个最长递增子序列...

动态规划数组凸子序列最长递增子序列二分法

2021-08-02

0 538

题解 | #牛妹的礼物# 来自专栏

思路：题目的主要信息：矩阵不为空，且矩阵中的内容非负数总体上要从矩阵的左上角到右下角，每次可以选择向下、向右、向右下三个方向路过矩阵每个格子中的数累加，求最短路径和事实上，这道题就是一个求矩阵最短路径和的问题，只不过它是有三个方向可以选择。方法一：递归（超时）具体做法：容易想到的是，...

动态规划空间记忆递归数组矩阵矩阵最小路径和

2021-07-31

0 568

题解 | #牛能和牛可乐的礼物# 来自专栏

思路：题目的主要信息：给定一串数组，将数组分为两部分要使两部分各自的和相差最小两部分的值越接近于总和的一半，相差越小。方法一：动态规划（01背包）具体做法：依据上面提到的性质，我们可以将这个问题看成一个01背包问题：背包容量为总和的一半，因此我们要装两部分，然后依次遍历数组，利用动态规...

动态规划空间记忆递归 01背包

2021-07-31

0 593

题解 | #单帧操作# 来自专栏

思路：题目的主要信息：给一串数组，每次找到一个位置进行一次操作：将该位置前后一个数及本身改为三者中的最大值一共进行n次操作，每次操作需要找到改变后使数组和最大那个位置来改变方法一：暴力解法（超时）具体做法：利用二进制掩码的特性，枚举所有位置选择或是不选择的组合（相当于n次操作，选择的位置...

动态规划 bfs 数组

2021-07-30

0 503

题解 | #一样的水# 来自专栏

思路：题目的主要信息：数组a是初始时水桶里的水数组p是每次询问后，要求水桶中水相同的水桶数量一共是q次查询，每次需要找到使水桶中拥有相同水量的水桶数量达到p中要求的最少花费，即每次加水量最少方法一：动态规划+前缀和具体做法：我们用（下标1开始）表示前i个数的和。对于某一次查询，我们要求...

数组动态规划查找迭代前缀和

2021-07-30

0 571

题解 | #牛妹的蛋糕# 来自专栏

思路：题目的主要信息：每天吃掉蛋糕总数的1/3，再额外吃1个吃到第n天还剩下1个蛋糕，问最开始总共有多少蛋糕这是一个数学问题，可以用递归、动态规划、迭代处理。方法一：递归具体做法：第n天还剩下1一个蛋糕，那么总蛋糕数就是n-1的子问题+1的3/2，可以写出如下递归： class Sol...

递归迭代动态规划数学模拟

2021-07-29

0 525

题解 | #最大子三角形# 来自专栏

思路：题目的主要信息：从一个六边形的01矩阵中找到全1的三角形，且要找边长最大的一个其中六边形矩阵的数据以vector数组的形式给出因为给出的数据是一维的，现在首要的难题的是将一维数组表示的六边形矩阵装入二维矩阵。仔细观察边长为的六边形矩阵，一共是行，最长是列。因此我们建立一个这样的矩阵保存...

最大子三角形六边形数组动态规划迭代

2021-07-29

1 567

题解 | #牛牛的数列# 来自专栏

思路：题目的主要信息：求给定数组的一个子序列，该子序列修改一个元素后可以变成完全递增序列，可以不用修改要求返回子序列的最长长度基本思路就是遍历数组中的所有元素，检查如果该元素后一个元素大于前一个元素，我们可以找到以它前一个元素结尾的最长递增序列加上以它后一个元素开始的最长递增序列，二者相...

动态规划数列递归最长递增子序列

2021-07-28

0 549

题解 | #最长回文子序列# 来自专栏

思路：题目的主要信息：找到给定串中的最长回文子序列的长度子序列不同于字串，不要求字符全部相邻回文序列是指这个序列无论从左读还是从右读都是一样的方法一：递归（超时）性质：一个字符串的最长回文子序列等于该字符串与其逆序的最长公共子序列。具体做法：我们可以利用上述性质，构造字符串s的逆序字符...

动态规划子序列字符串递归回文序列

2021-07-28

0 610

题解 | #信封嵌套问题# 来自专栏

思路：题目的主要信息： vector中是每个信封的长度和宽度，当一个信封长度和宽度都大于另一个信封时，便可以嵌套题目要求最大嵌套数量，且长宽不能颠倒方法一：动态规划具体做法：我们可以用动态规划来解决。首先对数组进行排序，将较长的信封放在前面，使之成为一个信封长度递减的序列。维护一个辅助数组...

数组排序信封嵌套二分法动态规划

2021-07-28

0 602