【动态规划】C++算法:最长有效括号

这篇具有很好参考价值的文章主要介绍了【动态规划】C++算法:最长有效括号。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

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;
};

【动态规划】C++算法:最长有效括号,# 算法题,算法,动态规划,c++,leetcode,最长,有效括号,拼接

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。

【动态规划】C++算法:最长有效括号,# 算法题,算法,动态规划,c++,leetcode,最长,有效括号,拼接文章来源地址https://www.toymoban.com/news/detail-791402.html

到了这里,关于【动态规划】C++算法:最长有效括号的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法题】动态规划中级阶段之最长回文子串、括号生成、跳跃游戏

    动态规划(Dynamic Programming,简称 DP)是一种解决多阶段决策过程最优化问题的方法。它是一种将复杂问题分解成重叠子问题的策略,通过维护每个子问题的最优解来推导出问题的最优解。 动态规划的主要思想是利用已求解的子问题的最优解来推导出更大问题的最优解,从而

    2024年02月12日
    浏览(43)
  • 【算法Hot100系列】最长有效括号

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月02日
    浏览(43)
  • LeetCode | C++ 动态规划——300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

    300题目链接 dp 数组定义 dp[i] 表示 i 之前包括 i 的以 nums[i]结尾 的最长递增子序列的长度 需要包含nums[i]结尾,不然在做递增比较的时候,就没有意义了。 递推公式 位置 i 的最长递增子序列 等于 j 从 0 到 i - 1各个位置的最长递增子序列 + 1 的 最大值 if (nums[i] nums[j]) dp[i] = ma

    2024年02月16日
    浏览(46)
  • 【算法|动态规划No.7】leetcode300. 最长递增子序列

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(42)
  • 【算法|动态规划No30】leetcode5. 最长回文子串

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(39)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(48)
  • 有效的括号字符串(力扣)动态规划、贪心 JAVA

    给你一个只包含三种字符的字符串,支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串,如果是有效字符串返回true 。 有效字符串符合如下规则: 任何左括号 ‘(’ 必须有相应的右括号 ‘)’。 任何右括号 ‘)’ 必须有相应的左括号 ‘(’

    2024年02月14日
    浏览(38)
  • 剑指offer(C++)-JZ48:最长不含重复字符的子字符串(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 数据范围:  s.length≤40000 s.length≤40000 示例: 输入: 返回值: 说明

    2024年02月06日
    浏览(55)
  • 1027. 最长等差数列【leetcode】/动态规划

    给你一个整数数组 nums,返回 nums 中最长等差子序列的长度。 回想一下,nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] ,且 0 = i1 i2 … ik = nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 = i seq.length - 1) 的值都相同,那么序列 seq 是等差的。 示例 1 : 输入 :nums = [3,6,9,12] 输出 :

    2024年02月21日
    浏览(41)
  • 【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号

    🌱 栈 是一种特殊的线性表, 只能在一端进行操作 🌱 往栈中 添加 元素的操作,一般叫做 push ( 入栈 ) 🌱 从栈中 移除 元素的操作,一般叫做 pop ,出栈(只能移除栈顶元素),也叫做: 弹出栈顶元素 🌱 后进先出 的原则, L ast I n F irst O ut, LIFO 注意:这里的 栈 与内

    2024年02月13日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包