注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex32 Longest Valid Parentheses  

2015-05-29 23:04:05|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.


传统的括号匹配的一个变形,用一个栈来匹配"(",另一个栈来存下标,最后匹配完了之后在栈里面留下的下标就是匹配的分割点。
ps 用暴力的方法不好~~

class Solution {
public:
/*
* 可以用暴力搜索的方法,不过这样很傻
* 思考了一下,一次遍历就可以完成,用栈实现,最后没有被弹出来的就是分割线
* 最后计算一下分割线的距离就可以了
* 据说此题还有人用动态规划,我那个去,这都行!!
*/
int longestValidParentheses1(string s) {
//用栈来实现,遍历一次,每次把下标放进去,一旦匹配就把下标弹出来
//没有被弹出来的就是分割不匹配的字符括号的
int len = s.size();
if (len < 2)
return 0;
int i;
i = len - 1;
stack<char>myStack;
stack<int>indexStack; //存储下标的括号
int count = 0;
int maxLen = INT_MIN;
while (i >= 0)
{
indexStack.push(i);
if (s[i] == ')')
{
myStack.push(')');
}
else
{
//如果是前括号的话
if (!myStack.empty())
{
myStack.pop();
indexStack.pop();
indexStack.pop();//一旦匹配,就把两个都弹出来
}

}
i--;
}
maxLen = 0;
len = indexStack.size();
//最后的下标还少保留了两个,一个是字符串末尾,一个是字符串开头
if (indexStack.empty()) //如果indexStack为空的话,说明全部匹配
{
return s.length();
}

int current;
int previous = indexStack.top();
if (previous != 0)
maxLen = myMax(maxLen,previous);
//如果开头不是分割线的话,说明需要计算从0到栈顶下标的距离


for (i = 0; i < len; i++)
{
current = indexStack.top();
indexStack.pop();
maxLen = myMax(maxLen,current-previous-1);
previous = current;
}

current = s.length(); //计算一下最后一个保存的index到 字符串末尾的距离
maxLen = myMax(maxLen, current - previous - 1);


return maxLen;
}
int myMax(int a,int b)
{
return a > b ? a : b;
}
int myMin(int a, int b)
{
return a > b ? b : a;
}
int longestValidParentheses(string s) {
int len = s.size();
if (len < 2)
return 0;
int i, j;
bool mark;
int maxLen = 0;
int tmpLen = 0;
for (i = 0; i < len; i++)
{
for (j = i + 1; j < len; j += 2)
{
string tmp = s.substr(i,j-i+1);
tmpLen = tmp.size();
mark = validParentheses(tmp);

if (mark)
{
maxLen = maxLen>tmpLen ? maxLen : tmpLen;
}

}
}
return maxLen;
}
bool validParentheses(string s)
{
stack<char> myStack;
int len = s.length();
int i = len - 1;
while (i >= 0)
{
if (s[i] == ')')
{
i--;
myStack.push(')');
}
else
{
if (myStack.empty())
return false;
else
{
myStack.pop();
i--;
}

}
}
if (!myStack.empty())
return false;
else
return true;
}
};


  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017