leetcode解题报告 32. Longest Valid Parentheses 动态规划DP解
2024-10-12 13:08:07
dp[i]表示以s[i]结尾的完全匹配的最大字符串的长度。
dp[] = ;
if( s[i] == '(' )
dp[i] = ;
开始递推 s[i] = ')' 的情况
先想到了两种情况：
1、s[i-1] = '(' 相邻匹配
这种情况下，dp [i] = dp[i-2] + 2。
2、s[i-1] = ')'
这种情况下，第一感觉是要看dp[i-1]的值，即 j...i-1是完全匹配的话，i相当于在外面再包一个括号。
如果s[i] 和 s[ i-1-dp[i-1] ] 匹配，dp[i] = dp[i-1] + 2。否则dp[i] = 0。
提交发现 WA。
不通过的数据是这个：
上图中的23列，本来23应该和2列的'('匹配，得到22。但是计算中，23列只得到了6。
加上一行代码AC了： dp[i] += dp[ i-1-dp[i-1] ];
如果当前完整块前面相邻了一个完整块，就把它的长度也算在内。
连蒙带猜的过了。。。有点水。希望以后赶紧提升。
int longestValidParentheses(char *s)
{
int n = strlen(s);
int i,cnt ,ans = ; if(n == && s == NULL) return ; dp = (int*)malloc(n*sizeof(int)); //dp[i]表示以s[i]结尾的匹配字符串的长度。 memset(dp,,n*sizeof(int)); for(i=;i<n;i++)
{
if( s[i]=='(' ){
dp[i] = ;
}
else
{ /* 0 1 2 3 4 5 6 i */
if( s[i-] == '(' ) /* ( ( ( ) ) ) ( ) */
{
int tmp = i-;
if(tmp >= )
{
dp[i] = dp[tmp] + ;
}
else
{
dp[i] = ;
}
}
/* 0 1 2 3 4 5 i ( ( ( ) ) ) ) 0 0 0 2 4 6
*/
else
{
int tmp = i--dp[i-];
if(tmp >= && s[tmp] == '(')
{
dp[i] = dp[i-] + ;
dp[i] += dp[i-dp[i]];
}
}
}
}
cnt = ;
ans = ;
for( i=n-; i>=; )
{
if(dp[i] > )
{
cnt += dp[i];
i -= dp[i]; if(cnt > ans) ans = cnt;
}
else
{
cnt = ;
--i;
}
}
free(dp); return ans;
}
最新文章
- Linux系统上通知网关更新arp
- mongodb（分片）
- .NET Remoting获取配置通道：
- JavaScript实现在文本框中输入空格时自动填写某个值
- 从客户端中检测到有潜在危险的Request.Form 值
- Silverlight中弹出网页
- PAT_1040 有几个PAT
- Shell脚本——中继DHCP服务器自动部署
- 【Cocos2d-X游戏实战开发】捕鱼达人之开发前准备工作（一）
- [nginx]Windows和Mac下，nginx反向代理服务器配置
- SQL server中事务的四个属性特征(ACID)
- 团队项目7——团队冲刺（beta版本）
- Fiddler抓取https的设置
- Change default network name (ens33) to old “eth0” on Ubuntu 18.04 / Ubuntu 16.04
- LeetCode-Valid Number - 有限状态机
- LeetCode OJ：Valid Number
- LINUX 下 NMAP 内网扫描
- vim文本编辑
- C# 创建一个WCF服务
- MySQL（C#的链接姿势）