摸鱼学大师

题解

未归档(8)

/ 注册

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

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

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

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

2021-08-02

0 538

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

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

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

2021-07-31

0 568

题解 | #字符串距离计算# 来自专栏

思路：题目的主要信息：两个长度相等的字符串距离定义为相同位置不同字符的数目现有两个字符串S1与S2，从S1中任选一个字符X1，将其全部替换成另一个字符串X2后再与S2比较距离，求这个距离可能的最小值两个字符串长度一定相等，全是小写字母，无特殊情况方法一：暴力法具体做法：既然全是小写字母...

字符串距离字符串矩阵数组

2021-07-31

0 523

题解 | #那些插队的人# 来自专栏

思路：题目的主要信息：长度为n为队伍，人员编号1-n cutIn数组中是要插队的编号，依次进行插队，即加入到最前面求最后有多少人不在原来的位置方法一：哈希表具体做法：对于最后的队列，没有插过队的人肯定都排在后面，最大插队元素是其分界线，最大插队元素之前的位置都可能有改变，之后的就不会有变...

插队数组数学模拟哈希表

2021-07-30

0 439

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

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

动态规划 bfs 数组

2021-07-30

0 503

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

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

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

2021-07-30

0 571

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

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

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

2021-07-29

1 567

题解 | #数组求和统计# 来自专栏

思路：题目的主要信息：两个长度相同的数组a与b，长度都为n 统计数对出现的次数，其中：相当于是相同的下标，a数组中的区间求和等于b数组中两端相加。方法一：暴力法具体做法：一个慢指针遍历a数组中的每个元素，另一个快指针遍历a数组中后面的所有元素，并累加快慢指针之间的和，并每次...

数组数学模拟哈希前缀和

2021-07-29

0 533

题解 | #牛牛的消消乐# 来自专栏

思路：题目的主要信息：对一个数组，每次选1个元素进行操作，两次操作后使数组和最小操作为：任选一个元素x，将数组中所有大于等于x的数减去x 方法一：暴力法具体做法：首先对数组进行排序，使之成为递增顺序。求一个数组的和sum，然后就是找到sum要减去的最大值。这个最大值就是进行两次操作的时候...

数组数学分段函数

2021-07-29

2 837

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

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

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

2021-07-28

0 602