华科不平凡

分类

题解(135)

/ 注册

TA的专栏 135篇文章 8人订阅

刷遍天下无敌手

135篇文章 15888人学习

0篇文章 0人学习

全部文章（共135篇）

单调栈结构来自专栏

单调栈，顾名思义，栈中的内容是单调的，我们可以利用这里特性解决一些有趣的问题，如：水池问题: 给定一组高度，如[0,1,0,2,1,0,1,3,2,1,2,1]，返回可以装的水量6 最大面积问题：给定一组高度如[2,1,5,6,2,3]，返回最大矩形面积10 题目中要求所有值左边👈和右边最近...

单调栈

2020-08-27

2 1025

0/1背包问题来自专栏

“求价值最大和”，毋庸置疑，用动态规划。此类题目属于动态规划中的一个特殊类别——“背包问题”。 PS：背包问题可以分为三种—— 0/1背包问题——物品只有选/不选两种状态，求最大价值和子集背包问题——分割等和子集问题完全背包问题——物品可以无限选，求可以组合成目标值的选法设当前个数为i，当...

背包问题动态规划

2020-08-26

2 833

格雷码来自专栏

这道题目可以用普通的循环来做，也可以用动态规划来做，相比起来动态规划的思路更加清晰，代码逻辑更加紧密。当n为1时，输出0,1，n为2时，输出00,01,11,10，当n为3时，输出00,01,11,10,110,111,101,100。规律：11,10是在1,0高位上+1得到；110,111,1...

动态规划格雷码

2020-08-25

0 720

子集ii 来自专栏

深度优先遍历，通过set进行去重： // // Created by jt on 2020/8/25. // class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> ...

set 深度优先搜索

2020-08-25

0 694

判断字符串能否由另外两个字符串相交构成来自专栏

"求是否存在"，毫无疑问，又是一道动态规划题。设当前子序列为S1[0..i],S2[0..j],S3[0..i+j+1]，dp[i+1][j+1]==true表示S3[0..i+j]可以由S1[0..i]和S2[0..j]交叉组成，得到如下状态推导公式：如果S1[i]==S3[i+j+1]&am...

子序列动态规划

2020-08-25

1 1114

单词切割ii 来自专栏

用深度优先搜索，注意优化时间复杂度，否则会超时：优化后 class Solution { public: vector<string> wordBreak(string s, unordered_set<string> &dict) { un...

深度优先搜索子串

2020-08-25

1 631

不同子序列个数来自专栏

“求子序列个数”，毋庸置疑，这是一道动态规划题。首先定义dp[i][j]的含义：S[0..j-1]中包含T[0..i-1]的子序列个数，接下来定义状态公式：状况1: dp[i][j]=dp[i][j-1]（如果T[i-1]!=S[j-1]）状况2：dp[i][j]=dp[i][j-1] + d...

子序列动态规划

2020-08-25

2 1124

回文字符串ii（最少切割次数）来自专栏

典型的动态规划问题：对于每个位置i，以递增的方式找长度为1,3,5,7...的回文子串，然后找长度为2,4,6,8的回文子串；假设回文子串的起始位置为idx_s，结束位置为idx_e，更新dp数组的公式为dp[idx_e] = min(dp[idx_s-1] + 1, dp[idx_e]) 考...

回文动态规划

2020-08-24

2 922

回文字符串的切割来自专栏

引用华科平凡大佬的原话，很精辟：如要输出所有的解，往往深度优先搜索；如要求出解的个数或最优解，往往动态规划本题要求输出字符串的所有回文字串组合，因此用深度优先搜索（代码思路同样借鉴了大佬，判断回文的部分简直妙极了）： // // Created by jt on 2020/8/23. // ...

回文深度优先搜索

2020-08-24

4 767

回文数字来自专栏

非反转的常数级别空间复杂度解法：首先计算出数字的位数然后从数字两边向中间遍历，判断对称部位的数字是否相等 class Solution { public: /** * * @param x int整型 * @return bool布尔型 *...

回文十进制

2020-08-24

11 821