绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
leetcode32. 最长有效括号
2020-07-06 00:37:07

1. 题目描述

给定一个只包含 '('')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-valid-parentheses


2. 解题思路

/*
解题思路:
/*
动态规划解题四个组成部分
1. 确定状态
- 研究最优策略的最后一步
- 化为子问题
dp[i]: 表示s[i]的最长有效字符串
2. 转移方程
- 根据子问题定论直接得到
2.1、当s[i]=='(',不构成最长有效串,跳过。
2.2、当s[i]==')' 并且s[i-1]=='(',即“.....()”
dp[i] = dp[i-2]+2;
2.3、当s[i]==')' 并且s[i-1]==')', 即“.....))”
dp[i] = dp[i-1]+dp[i-dp[i-1]-2]+2

3. 初始条件和边界情况
- 细心,考虑周全
2.2中,i-2可能越界
2.3中,i-dp[i-1]-1、i-dp[i-1]-2可能越界
4. 计算顺序
- 利用之前的计算结果
*/
*/


3. 测试结果

解法一、动态规划


4. 动态规划

/*
title: leetcode32. 最长有效括号
author: xidoublestar
method: 动态规划
type: C++
date: 2020-6-9
*/

class Solution {
public:
int longestValidParentheses(string s) {
int size = s.length();
if (size < 2)
return ;
int maxLen = ;
vector<int> dp(size, );
for (int i = 1; i < size; i++)
{
if (s[i] == '(')
continue;
if (s[i - 1] == '(')
dp[i] = (i - 2 >= ? dp[i - 2] : ) + 2;
else if ((i - dp[i - 1] - 1) >= && s[i - dp[i - 1] - 1] == '(')
dp[i] = (i - dp[i - 1] - 2 >= ? dp[i - dp[i - 1] - 2] : ) + dp[i - 1] + 2;
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
};


6. 动态规划

解法一、顺序合并
时间复杂度:O(n)
空间复杂度:O(n)


分享好友

分享这个小栈给你的朋友们,一起进步吧。

数据库技术笔记
创建时间:2020-03-03 00:45:30
oracle技术分享
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • orastar
    栈主

小栈成员

查看更多
  • xzh1980
  • 飘絮絮絮丶
  • Leila
  • gaokeke123
戳我,来吐槽~