C++怎么实现最长有效括号

今天小编给大家分享一下C++怎么实现最长有效括号的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。Given a string containing just the characters”(“and”)”, find the length of the longest valid (well-formed) parentheses substring.Example 1:Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”Example 2:Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”这道求最长有效括号比之前那道Valid Parentheses难度要大一些，这里还是借助栈来求解，需要定义个 start 变量来记录合法括号串的起始位置，遍历字符串，如果遇到左括号，则将当前下标压入栈，如果遇到右括号，如果当前栈为空，则将下一个坐标位置记录到 start，如果栈不为空，则将栈顶元素取出，此时若栈为空，则更新结果和 i – start + 1 中的较大值，否则更新结果和 i – st.top() 中的较大值，参见代码如下：解法一：还有一种利用动态规划 Dynamic Programming 的解法。这里使用一个一维 dp 数组，其中 dp[i] 表示以 s[i-1] 结尾的最长有效括号长度（注意这里没有对应 s[i]，是为了避免取 dp[i-1] 时越界从而让 dp 数组的长度加了1），s[i-1] 此时必须是有效括号的一部分，那么只要 dp[i] 为正数的话，说明 s[i-1] 一定是右括号，因为有效括号必须是闭合的。当括号有重合时，比如 “(())”，会出现多个右括号相连，此时更新最外边的右括号的 dp[i] 时是需要前一个右括号的值 dp[i-1]，因为假如 dp[i-1] 为正数，说明此位置往前 dp[i-1] 个字符组成的子串都是合法的子串，需要再看前面一个位置，假如是左括号，说明在 dp[i-1] 的基础上又增加了一个合法的括号，所以长度加上2。但此时还可能出现的情况是，前面的左括号前面还有合法括号，比如 “()(())”，此时更新最后面的右括号的时候，知道第二个右括号的 dp 值是2，那么最后一个右括号的 dp 值不仅是第二个括号的 dp 值再加2，还可以连到第一个右括号的 dp 值，整个最长的有效括号长度是6。所以在更新当前右括号的 dp 值时，首先要计算出第一个右括号的位置，通过 i-3-dp[i-1] 来获得，由于这里定义的 dp[i] 对应的是字符 s[i-1]，所以需要再加1，变成 j = i-2-dp[i-1]，这样若当前字符 s[i-1] 是左括号，或者j小于0（说明没有对应的左括号），或者 s[j] 是右括号，此时将 dp[i] 重置为0，否则就用 dp[i-1] + 2 + dp[j] 来更新 dp[i]。这里由于进行了 padding，可能对应关系会比较晕，大家可以自行带个例子一步一步执行，应该是不难理解的，参见代码如下：解法二：此题还有一种不用额外空间的解法，使用了两个变量 left 和 right，分别用来记录到当前位置时左括号和右括号的出现次数，当遇到左括号时，left 自香港云主机增1，右括号时 right 自增1。对于最长有效的括号的子串，一定是左括号等于右括号的情况，此时就可以更新结果 res 了，一旦右括号数量超过左括号数量了，说明当前位置不能组成合法括号子串，left 和 right 重置为0。但是对于这种情况 “(()” 时，在遍历结束时左右子括号数都不相等，此时没法更新结果 res，但其实正确答案是2，怎么处理这种情况呢？答案是再反向遍历一遍，采取类似的机制，稍有不同的是此时若 left 大于 right 了，则重置0，这样就可以 cover 所有的情况了，参见代码如下：解法三：以上就是“C++怎么实现最长有效括号”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注开发云行业资讯频道。

相关推荐: 怎么查看电脑已经开机运行了多长时间

这篇文章主要为大家展示香港云主机了“怎么查看电脑已经开机运行了多长时间”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“怎么查看电脑已经开机运行了多长时间”这篇文章吧。方法一：1.使用鼠标右键点击桌面左下角的开始菜单…