摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #取球放球# 来自专栏

思路：题目的主要信息：一共n个箱子，每个箱子有一定容量和一定初始球个数进行k次操作，每次操作对某一个箱子中的球进行加1或者减1 求k次操作之后要使任意相邻箱子球数差的平方的最大值达到最小。方法一：贪心具体做法：利用贪心思想，利用一个辅助数组每次操作前记录相邻两个数组之差，并找到差的最大值...

二分法动态规划贪心数组

2021-08-02

0 539

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

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

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

2021-08-02

0 538

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

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

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

2021-07-28

0 602

题解 | #二维数组中的查找# 来自专栏

题目的主要信息：矩阵的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复找到矩阵中有没有给定元素即可方法一：暴力法具体做法：从上到下每行，每行中从左至右遍历二维数组，依次查找。 class Solution { public: bool Find(in...

二维数组二分法查找

2021-07-27

0 489

题解 | #最长重复子串# 来自专栏

思路：题目的主要信息：重复字符串是由两个相同的字符串首尾拼接而成，不存在覆盖返回的是字串长度，为重复部分的2倍，必为偶数若不存在任何重复字符子串，则返回0 方法一：暴力解法（超时）具体做法：n记录最长的重复字串的重复长度，从字符串长度一半开始，然后依次比较后面的n个字符及再后面的n个字符...

二分法重复子串字符串

2021-07-25

1 1832

题解 | #最长递增子序列# 来自专栏

思路：先找最长递增子序列长度再根据长度逆向得到序列（逆向的原因是字典序更小，若是小值跑到后面去的情况，同样长度大值跑后面只会增加子序列长度）要找到最长的递增子序列长度，常用方法是动态规划，dp[i]表示到元素i结尾时，最长的子序列的长度，初始化全部为1。方法一：暴力动态规划（超时）具...

动态规划二分法子序列数组

2021-07-17

1 1185

题解 | #寻找第K大# 来自专栏

思路：题目中给到的信息：利用快速排序的思想有重复数字，不用去重，也不用管稳定性与否方法一：重载sort 因为sort使用的是快速排序，因此这种方法勉强算是利用了快排思想。这次要寻找第K大，sort函数默认递增，因此需要将其重载为递减，然后遍历到第k个。 class Solution {...

快速排序递归二分法

2021-07-16

14 1487