摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #最长上升子序列(一)# 来自专栏

题目主要信息: 给定一个数组，求其中最长的严格上升子序列的长度子序列是指数组去掉或不去掉元素后的数组，不要求在原本数组中全部相邻，但是在原数组中的相对位置不能改变严格上升指子序列严格单调递增具体思路: 要找到最长的递增子序列长度，常用方法是动态规划，用dp[i]dp[i]dp[i]表示到元...

C++ 动态规划

2022-02-18

0 406

题解 | #求路径# 来自专栏

题目的主要信息：给定一个m*n的矩阵，要求从矩阵的左上角走到右下角的不同路径数量每次只能往下或者往右走这道题非常典型，我们可以考虑多种方式。方法一：递归具体做法：首先我们在左上角第一个格子的时候，有两种行走方式：如果向右走，相当于后面在一个(n−1)∗m(n-1)*m(n−1)∗m...

C++ 递归动态规划

2022-02-18

0 561

题解 | #编辑距离(一)# 来自专栏

题目主要信息: 给定两个长度可能不同的字符串，可以对第一个字符串增删改字符求增删改的最少次数，让第一个字符串变成第二个字符串字符串中只出现大小写字母具体思路: 把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转...

C++ 动态规划

2022-02-18

3 650

题解 | #盛水最多的容器# 来自专栏

题目主要信息: 输入一个数组，其中每个元素代表水桶边界高度水桶容积为边界较短的一边高度乘上两边界的距离（数组下标表示距离）求在数组中选取两个边，求最大容积具体思路: 这道题类似接雨水问题，还是利用了水桶的短板原理，较短的一边控制最大水量，因此直接用较短边长乘底部两边距离就可以得到当前情况下...

C++ 双指针贪心

2022-02-18

0 542

题解 | #接雨水问题# 来自专栏

题目主要信息: 给定一个整型数组，数组每个元素表示下图所示的每列灰色柱子高度，数值都是非负数在雨水（图中蓝色部分）不超过边界的情况下，问最多能有多少蓝色的格子数组以外的区域高度视为0 具体思路: 我们都知道水桶的短板问题，控制水桶水量的是最短的一条板子。这道题也是类似，我们可以将整个图看成...

C++ 双指针

2022-02-18

0 436

题解 | #矩阵最长递增路径# 来自专栏

题目主要信息: 给定一个矩阵，矩阵中所有元素都是非负整数需要在矩阵中找到一条最长路径，路径中的元素都是递增的，求其最长长度查找路径时，只能向上下左右四个方向查找，不能超出边界，且每个格子最多走一次具体思路: 既然是查找最长的递增路径长度，那我们首先要找到这个路径的起点，起点不好直接找到，就...

C++ 递归

2022-02-17

0 588

题解 | #字符串的排列# 来自专栏

题目主要信息: 给定一个长度为n的字符串，求其中所有字符的全排列字符串中可能有重复字符，打印顺序任意字符串中只包含大小写字母具体思路: 都是求元素的全排列，字符串与数组没有区别，一个是数字全排列，一个是字符全排列，因此大致思路与有重复数字的全排列类似，只是这道题输出顺序没有要求。但是为了便...

C++ 递归

2022-02-17

0 417

题解 | #岛屿数量# 来自专栏

题目主要信息: 给定一个01矩阵，其中1代表是陆地，0代表海洋，如果两个1相邻，则这两个1属于同一个岛只考虑矩阵中上下左右为相邻，斜方不算相邻求矩阵中表示的岛屿的个数具体思路: 矩阵中多处聚集着1，要想统计1聚集的堆数而不重复统计，那我们可以考虑每次找到一堆相邻的1，就将其全部改成0，而将...

C++ 递归 dfs

2022-02-16

1 455

题解 | #有重复项数字的全排列#

题目主要信息: 给定一组可能有重复数字的数组，输出该数组的全部排列输出结果按照字典序升序排列具体思路: 这道题类似没有重复项数字的全排列，但是因为交换位置可能会出现重复交换的情况，出现的结果需要去重，因此不便于使用交换位置的方法，我们就使用临时变量去组装一个排列的情况：每当我们选取一个数组元...

C++ 递归

2022-02-16

3 675

题解 | #没有重复项数字的全排列# 来自专栏

题目主要信息: 给定一个数组，求这组数字的全排列数组无重复元素以数字在数组中的位置靠前为优先级，按字典序排列输出具体思路: 全排列就是对数组元素交换位置，使每一种排列都可能出现。因为题目要求按照字典序排列输出，那毫无疑问第一个排列就是数组的升序排列，它的字典序最小，后续每个元素与它后面的元...

C++ 递归

2022-02-16

0 1179