摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #公共子串计算# 来自专栏

题目的主要信息：查找两个字符串a,b中的最长公共子串的长度字符串只包含小写字母进阶要求：时间复杂度：O(n3)O(n^3)O(n3)，空间复杂度：O(n)O(n)O(n) 方法一：暴力枚举具体做法：遍历s1每个字符作为起点，然后遍历以其为起点的每个长度的长度，即暴力枚举字符串s1的所有...

C++ 字符串动态规划

2021-10-30

0 375

题解 | #字符串通配符# 来自专栏

题目的主要信息：实现如下2个通配符： *：匹配0个或以上的字符？：匹配1个字符注：能被*和?匹配的字符仅由英文字母和数字0到9组成，输入却不止这两种匹配不区分大小写方法一：递归具体做法：可以在匹配部分过后，将通配符和字符串的剩余部分进入递归继续判断是否可以完成匹配。首...

C++ 递归动态规划字符串

2021-10-29

1 482

题解 | #查找两个字符串a,b中的最长公共子串# 来自专栏

题目的主要信息：查找两个字符串a,b中的最长公共子串若有多个，输出在较短串中最先出现的那个进阶要求：时间复杂度：O(n3)O(n^3)O(n3)，空间复杂度：O(n)O(n)O(n) 方法一：暴力枚举具体做法：我们可以先比较两个字符串的长度，然后将s1设置为较短的字符串，s2设置为较长...

C++ 动态规划字符串

2021-10-29

12 927

题解 | #小红的树# 来自专栏

题目的主要信息：没有回路的无向连通图，可以看成树，根结点为1 其中一部分结点染成了红色之后有qqq次询问，每次询问以该结点作为根的子树有多少红色结点具体做法：根据输入的父节点，构建树的邻接表。然后用字符串记录输入的染色信息，再通过dfs构建，对树进行染色，构建dp数组。其中dp[i]d...

C++ 动态规划递归 dfs

2021-10-27

2 656

题解 | #放苹果# 来自专栏

题目的主要信息：把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放共有多少种不同的分法，不区分顺序方法一：递归具体做法：因为不区分顺序，所以只考虑苹果分了几份，每份多少个，很容易知道当苹果为0个的时候或者盘子只有1个的时候，只有1种分法。那这个问题子问题就是苹果更少或者盘子更少...

C++ 递归动态规划

2021-10-27

16 0

题解 | #合并回文子串# 来自专栏

题目的主要信息：两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变需求出所有可能的串C中的最长回文子串的长度具体做法：这是一个区间DP问题。我们用dp[l1][r1][l2][r2]dp[l1][r1][l2][r2]dp[l1][r1][l2][r2]表示字符串A在区...

C++ 动态规划

2021-10-26

0 611

题解 | #称砝码# 来自专栏

题目的主要信息：现有一组砝码，重量互不相等，分别为m1m_1m1,m2m_2m2,m3m_3m3 … mnm_nmn 每种砝码对应的数量为x1x_1x1,x2x_2x2,x3x_3x3 ...xnx_nxn 现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量 ...

C++ 动态规划集合

2021-10-21

46 3532

题解 | #统计每个月兔子的总数# 来自专栏

题目的主要信息：有一对兔子，从出生后第 3 个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第n个月的兔子对数为多少? 我们有如下计算：月份兔子数（对）第1个月 1对兔子第2个月 1对兔子第3个月 2对兔子（第一对生出第二对）...

C++ 递归动态规划

2021-10-21

24 1659

题解 | #密码截取# 来自专栏

题目的主要信息：输入一个长度不超过2500的字符串找到其中最长的回文子串长度方法一：中心扩散法具体做法：我们可以遍历每个字符串每个位置，都以其为回文子串的中心，或是奇数长度子串的中心（从两边开始找），或是偶数长度的子串中心（以它左边和它一起），分别向两边扩散，只要这个过程中两边字符是相...

C++ 动态规划字符串

2021-10-19

39 1641

题解 | #合唱队# 来自专栏

题目的主要信息：给出nnn个同学的身高，在不改变所有人的相对位置的情况下从中剔除几位，使得剩下的kkk位同学的身高排序是形如：T1<T2<T3<...<Ti>Ti+1>...>TkT_1<T_2<T_3<...<T_i>T_...

C++ 动态规划二分法

2021-10-11

3 472