超级大米

题解

/ 注册

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

题解 | #正则表达式匹配#

动态规划，把pattern预处理一下，*字符和前面的字符分成一组，就可以开始了，dp[i][j],表示str的前i个字符和pat（处理后的数组）的前n组字符是否能匹配上 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定...

C++ 动态规划

2021-12-29

0 394

题解 | #编辑距离(一)#

动态规划，二维数组 comp[i][j] 项表示当str1的前i个字符匹配str2的前j个字符需要做的变化量。然后分两种情况，str1[i],str2[j]相同和不同，代码里应该很清楚了 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改...

C++ 动态规划

2021-12-29

0 319

题解 | #最长上升子序列(二)#

也算是一种动态规划新建一个数组，单调递增，数组中的数字upVec[i]表示长度为n的最小子序列，数组的长度就是最终子序列的长度。新来一个元素，如果他大于数组中的所有数字，则插入到末尾，否则，把第一个大于他的数字变成他。假设upVec = [1,3,5]，如果来了7，则变成 [1,3,5,7...

C++ 动态规划二分查找

2021-12-14

3 435

题解 | #寻找第K大#

两种实用方法，没啥难点，代码自己看吧 class Solution { public: int findKth(vector<int> a, int n, int K) { multiset<int, greater<int>> multy(a.begin...

C++

2021-12-13

0 331

题解 | #最大矩形#

把每一列的1累加起来，遇到0重新开始累加，记录到一个新的矩阵中，对这个矩阵进行遍历。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix int整型vector<...

C++ 枚举

2021-12-09

0 572

题解 | #最长无重复子数组#

使用双指针检索，map记录数据。 class Solution { public: /** * * @param arr int整型vector the array * @return int整型 */ int maxLength(vector<int>& arr) {...

C++ 双指针

2021-12-08

0 412

题解 | #单词拆分(二)#

用到了动态规划和字典查询，f(n)表示从从0到第n个字符有哪些解，则f(n) = (字母(0到n)如果在字典中，则并入f(0)的解) + (字母(1到n)如果在字典中，则并入f(1)的解).... (字母(n-1到n)如果在字典中，则并入f(n-1)的解),最终输出f(n) class Soluti...

C++ 动态规划哈希表

2021-12-07

0 457

题解 | #N皇后问题#

由题意可知，每行有且只有一个皇后，那么问题就变成先对第一行放一个皇后，之后再第二行中找一个位置放置皇后，一直放到最后一行，如果最后一行有位置放，那么直接answer++，否则返回到上一级，继续试下一个点。 int Nqueen(int n) { int answer = 0; //...

C++

2021-12-07

0 434

题解 | #打家劫舍(三)#

针对每个节点，有两种情况，选，或者不选，而该点的最大值为可以分为两种情况，选择该点时和不选择该点时，如果不选择该点，只需要获得左右子节点的最大值并相加，如果需要选择点，则需要获左右子节点都不直接选择的最大值（所以每次递归需要把子节点不选择时的最大值也返回上来）。最后比较两种情况的大小返回真正的最大值...

C++ 递归

2021-12-06

1 482