牛客283182957号

分类

题解(51)

/ 注册

全部文章（共52篇）

题解 | #最小覆盖子串#

1.问题描述：s的子串覆盖t的所有元素，不要求顺序。只看s子串中玩不完全包含t的所有元素。 2.滑动窗口简述：详述（76. 最小覆盖子串 Minimum Window Substring 【LeetCode 力扣官方题解】_哔哩哔哩_bilibili） &nb...

2022-07-31

0 367

题解 | #最长的括号子串#

step 1：可以使用栈来记录左括号下标。 step 2：遍历字符串，左括号入栈，每次遇到右括号则弹出左括号的下标。此时会出现两种情况：0，不合法情况，先出现右括号，1左括号比较多，2右括号比较多 step 3：然后长度则更新为当前下标与栈顶下标的...

2022-07-27

0 321

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

LeetCode力扣刷题 | 剑指Offer 19. 正则表达式匹配_哔哩哔哩_bilibili。还是有点不太理解。但是可以肯定的是分类讨论的思想，用模式串p取匹配源字符串s。只有p中会有。*之类的。问题的关键在于p当前匹配的字符是否为*，设dp[i]...

2022-07-26

0 320

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

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结...

2022-07-25

0 320

题解 | #最长回文子串#

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。贪心...

2022-07-14

0 337

题解 | #兑换零钱(一)#

动态规划19：例题：零钱兑换问题的分析_哔哩哔哩_bilibili 要点1，f（x）意思为，凑够x元所需要最少的硬币个数，这是一种映射。就是dp【i】的含义. 要点2，f（11）=min（f（11-5），f（11-2），f（11-1））+1.其中f（11）是由f（10），f（9），f（6...

2022-07-13

0 416

题解 | #把数字翻译成字符串#

问题，。。。。前n个数的译码种数就是前n-1个数的译码种数添上第n个数的译码种数之和 dp[i] 用辅助数组dp表示前i个数的译码方法有多少种。例如 nums = "2312", 此时dp[0]=1,dp[1]=1,dp[2]=2（2，3和23），dp[3]=2 （2，3，1和23，1...

2022-07-12

0 283

题解 | #矩阵的最小路径和#

题目要求得到从「左上角」到「右下角」的整个二维数组的最小路径，因此其子问题为：对于二维数组中的每个元素位置，求取从起点到该位置的最短路径；对于「右下角」的元素位置，从起点到该位置的最短路径即为最终答案。或者要求到最右下元素（m，n）路径最小，那么到mn只能由m-1，n或m，n-1到达...

2022-07-12

0 321

题解 | #最长公共子串#

此题在状态方程的寻找和描述上是比子序列简单的。9.69 最长公共子串（动态规划）——信息学竞赛培训课程_哔哩哔哩_bilibili 通过两层遍历可以求解问题。在第二个序列（内层循环中）逐个作为开头和第一个序列的每个字符开头比较，不断更新维护最大值。在求解的时候，可以使用动态规划思想，（...

2022-07-11

0 355

题解 | #最长公共子序列(二)#

0.公共子序列和公共子串的区别 1.解题思路。包教包会～最长公共子序列_哔哩哔哩_bilibili 结合图理解dp【i】【j】值的具体意义。。是指dp【0】【1】，dp【0】【2】-------dp【0】【j】（字符串1的A与字符串B的前1个即B的公共子序列，字符串1的A与字符串2的前2...

2022-07-05

0 368