作者推荐
视频算法专题
本文涉及知识点
动态规划汇总
LeetCoe:32 最长有效括号
给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = “(()”
输出:2
解释:最长有效括号子串是 “()”
示例 2:
输入:s = “)()())”
输出:4
解释:最长有效括号子串是 “()()”
示例 3:
输入:s = “”
输出:0
参数范围:
0 <= s.length <= 3 * 104
s[i] 为 ‘(’ 或 ‘)’
分析
有效括号有两个等效规则,本文用到了其中一个规则:
- ()是有效括号
- 如果A是有效括号,则(A)也是有效括号。简称:包括。如:()() 变成(()())
- 如果A和B都是有效括号,则AB 也是有效括号。简称拼接。如:(()) 和()拼接成(())()
从小到大枚举有效括号的结尾。如果s[i]不是‘)’,忽略。对于每个结尾,分两步:
- 一,计算最长包括。
- 二 ,计算最长拼接。
最长包括
如果dp[i-1]是’(‘,则最长包括是dp[i-1]为2。
如果’)‘ 且dp[i-1]匹配的’(‘的前一个字符为’( ,则dp[i] = 2 + dp[i-1]。dp[i-1]必须不为0。
最长拼接
dp[i]匹配的’('的前一个字符为pre,则dp[i] += dp[pre]。dp[i]必须不为0。
注意:不能第一轮枚举所有的包括,第二轮枚举所有的拼接。比如:(()())
代码
核心代码
class Solution {
public:
int longestValidParentheses(string s) {
if (s.empty())
{
return 0;
}
m_c = s.length();
vector<int> dp(m_c);
for (int i = 0; i < m_c; i++)
{
if ('(' == s[i])
{
continue;
}
if (i - 1 < 0)
{
continue;
}
//理括号的包括
if ('(' == s[i - 1])
{
dp[i] = 2 ;
}
else
{
const int pre = i -1 - dp[i - 1];
if (dp[i-1] && (pre>=0)&&('('==s[pre]))
{
dp[i] = dp[i - 1]+2;
}
}
//处理拼接
if (dp[i] <= 0)
{
continue;
}
const int pre = i - dp[i];
if (pre >= 0)
{
dp[i] += dp[pre];
}
}
return *std::max_element(dp.begin(), dp.end());
}
int m_c;
};
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
string s;
{
Solution sln;
s = "(()";
auto res = sln.longestValidParentheses(s);
Assert(2, res);
}
{
Solution sln;
s = "";
auto res = sln.longestValidParentheses(s);
Assert(0, res);
}
{
Solution sln;
s = ")()())";
auto res = sln.longestValidParentheses(s);
Assert(4, res);
}
{
Solution sln;
s = "(()())";
auto res = sln.longestValidParentheses(s);
Assert(6, res);
}
}
2022年12月版
class Solution {
public:
int longestValidParentheses(string s) {
if (“” == s)
{
return 0;
}
const int c = s.length();
//dp[i]表示以s[i]结尾的合法串长度,非法0
vector dp©;
for (int i = 1; i < c; i++)
{
const char& ch = s[i];
if (‘(’ == ch)
{
continue;
}
if (‘(’ == s[i - 1])
{
dp[i] = ( i >= 2 ? dp[i - 2] :0 ) + 2;
}
else
{
if (dp[i - 1] > 0)
{
int iBegin = (i - 1) - dp[i - 1] + 1;
iBegin–;
if ((iBegin >= 0) && s[iBegin] == ‘(’)
{
dp[i] = dp[i - 1] + 2;
if (iBegin > 0)
{
dp[i] += dp[iBegin - 1];
}
}
}
}
}
return *std::max_element(dp.begin(),dp.end());
}
};
2023年8月版
class Solution {
public:
int longestValidParentheses(string s) {
m_c = s.length();
if (0 == m_c)
{
return 0;
}
vector vRet(m_c);
stack sta;
for (int i = 0 ; i < m_c ; i++ )
{
const auto& ch = s[i];
if (‘(’ == ch)
{
sta.emplace(i);
}
else
{
if (sta.size())
{
int left = sta.top();//与之匹配的左括号
sta.pop();
vRet[i] = (i - left + 1);
if (left > 0)
{
vRet[i] += vRet[left - 1];
}
}
}
}
return *std::max_element(vRet.begin(), vRet.end());
}
int m_c;
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 **C+
+17**
如无特殊说明,本算法用**C++**实现。文章来源:https://www.toymoban.com/news/detail-791402.html
文章来源地址https://www.toymoban.com/news/detail-791402.html
到了这里,关于【动态规划】C++算法:最长有效括号的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!