摸鱼学大师

题解

未归档(8)

/ 注册

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

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

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

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

2021-07-30

0 571

题解 | #最大四边形面积# 来自专栏

思路：题目的主要信息：从一个一维数组中任选4个数，组成四边形，求能组成的四边形的最大面积返回结果与正确答案的误差应小于0.00001 性质1：能够组成四边形的四条边必然满足，三边之和大于第四边性质2：四条边已知（a,b,c,d)的四边形，最大面积（形状不确定，因为四边形有不稳定性，只能求最...

四边形四边形面积组合数排序最大面积公式

2021-07-30

0 805

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

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

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

2021-07-29

0 539

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

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

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

2021-07-29

1 580

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

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

数组数学模拟哈希前缀和

2021-07-29

0 533

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

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

数组数学分段函数

2021-07-29

2 837

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

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

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

2021-07-28

0 549

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

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

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

2021-07-28

0 610

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

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

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

2021-07-28

0 602

题解 | #将字符串转化为整数# 来自专栏

思路：题目的主要信息：写一个atoi函数，将字符串转变成int型数字，输入没有任何限制，需要注意以下几点：前导0与前导空格要全部去掉第一个符号是正负号的情况输入了非数字要直接跳出输入达到了int型表示边界空串返回0 方法一：遍历法具体做法：用一个index全程记录字符串下标。按照上面...

字符串状态机

2021-07-28

0 498