p*****2
发帖数: 21240 | 1 一个字符串里边只有 '(' 和 ')'
判断最长的substring, 里边的（和）是合法match的。
输出最长的长度和具有这个长度子串的数目。
比如
(())
4 1
())()
2 2 |
i******r
发帖数: 793 | |
p*****2
发帖数: 21240 | 3
目标是O(n)
【在 i******r 的大作中提到】
: 想到一个O(n^2)的做法
: 应该能有更快的
|
i******r
发帖数: 793 | 4 嗯，O(n)没错
用一个stack，左括号进栈，右括号看看能否出栈
这样scan一次就行了 |
i**********e
发帖数: 1145 | 5 我想到一个办法，利用双链表来表达字符串，每个字符中间有一个数字（首先全都初始
化为 0 ）。
然后一次从头到尾扫描，注意以下这两个条件：
- 每次看到数字左边和右边个别是 ‘（’和‘）’就删掉左边和右边的 node，然后把
数字本身 + 2.
- 另外，如果左边也是个数字，就两个数字加起来进行合并。
直到以上两个条件不符合为止，就继续看下一个 node。
这个似乎要花费 O(n) 空间，但应该是 amortized O(n) 时间. |
i******r
发帖数: 793 | 6 这个实现起来麻烦，呵呵
【在 i**********e 的大作中提到】
: 我想到一个办法，利用双链表来表达字符串，每个字符中间有一个数字（首先全都初始
: 化为 0 ）。
: 然后一次从头到尾扫描，注意以下这两个条件：
: - 每次看到数字左边和右边个别是 ‘（’和‘）’就删掉左边和右边的 node，然后把
: 数字本身 + 2.
: - 另外，如果左边也是个数字，就两个数字加起来进行合并。
: 直到以上两个条件不符合为止，就继续看下一个 node。
: 这个似乎要花费 O(n) 空间，但应该是 amortized O(n) 时间.
|
i**********e
发帖数: 1145 | 7 啊，你说得对，看了你的思路突然想到用 stack 来储存括号和数字就好了，不需要链
表，空间也省一点。
【在 i******r 的大作中提到】
: 嗯，O(n)没错
: 用一个stack，左括号进栈，右括号看看能否出栈
: 这样scan一次就行了
|
i**********e
发帖数: 1145 | 8 你是说实现双链表么，呵呵
双链表实现删除和插入的确麻烦。
不过思路方面应该跟你的一样。
【在 i******r 的大作中提到】
: 这个实现起来麻烦，呵呵
|
H***e
发帖数: 476 | 9 keep一个左括号的count，括号对数countB
遇到 （ , count++;
遇到 ）， count--; 同时 把括号对数 countB++
然后 一旦遇到)并且左括号的为0了，此时说明所有前面的都不再对以后valid了，这时
候countB是一个候选值，跟max 比较，然后countB set to 0； 再继续。。
不知道对否
喔， 还要keep一个变量来记录当前最长长度子串的数目。
【在 p*****2 的大作中提到】
: 一个字符串里边只有 '(' 和 ')'
: 判断最长的substring, 里边的（和）是合法match的。
: 输出最长的长度和具有这个长度子串的数目。
: 比如
: (())
: 4 1
: ())()
: 2 2
|
p*****2
发帖数: 21240 | 10 (())
(0(0)0)
第一遍扫描
(020)
(2)
4
()()
(0)0(0)
20(0)
2(0)
22
4
())()
(0)0)0(0)
20)0(0)
2)0(0)
2)02
2)2
应该是work的。 |
|
|
i**********e
发帖数: 1145 | 11 不用重复扫描，一次就行。
不过要重复判定那两个条件进行合并，直到不符合为止，才进行看下一个。
【在 p*****2 的大作中提到】
: (())
: (0(0)0)
: 第一遍扫描
: (020)
: (2)
: 4
: ()()
: (0)0(0)
: 20(0)
: 2(0)
|
p*****2
发帖数: 21240 | 12
我刚开始用的差不多这个思路不太对。
((((()(((()
【在 H***e 的大作中提到】
: keep一个左括号的count，括号对数countB
: 遇到 （ , count++;
: 遇到 ）， count--; 同时 把括号对数 countB++
: 然后 一旦遇到)并且左括号的为0了，此时说明所有前面的都不再对以后valid了，这时
: 候countB是一个候选值，跟max 比较，然后countB set to 0； 再继续。。
: 不知道对否
: 喔， 还要keep一个变量来记录当前最长长度子串的数目。
|
i**********e
发帖数: 1145 | |
p*****2
发帖数: 21240 | 14
我知道。一次扫描就够了。只是需要回溯一下。不过整体还是（N）的时间。我刚才就
是证明你的算法是对的。
【在 i**********e 的大作中提到】
: 不用重复扫描，一次就行。
: 不过要重复判定那两个条件进行合并，直到不符合为止，才进行看下一个。
|
H***e
发帖数: 476 | 15 蒽。 错的。 ...
【在 p*****2 的大作中提到】
:
: 我知道。一次扫描就够了。只是需要回溯一下。不过整体还是（N）的时间。我刚才就
: 是证明你的算法是对的。
|
p*****2
发帖数: 21240 | 16
可以用stack 和 dp。不过我也是在有提示的情况下做出来的。我本来是hbase的思路。
但是做不对。没想到你那个思路。你这么快能想到正确的解法还是挺赞的。
public class test
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
String str=in.next();
int[] dp=new int[str.length()];
Arrays.fill(dp,-1);
Stack stack=new Stack();
int max=0;
int maxcount=0;
for(int i=0;i
{
char c=str.charAt(i);
if(c=='(')
{
stack.add(i);
}
else
{
if(!stack.isEmpty())
{
int m=stack.pop();
if(m>0 && dp[m-1]!=-1)
dp[i]=Math.min(dp[m-1],m);
else
dp[i]=m;
int len=i-dp[i]+1;
if(len>max)
{
max=len;
maxcount=1;
}
else if(len==max)
maxcount++;
}
}
}
if(max>0)
System.out.println(max+" "+maxcount);
else
System.out.println("0 1");
}
}
【在 i**********e 的大作中提到】
: peking2，你有想到更好的办法吗？
|
i******r
发帖数: 793 | 17 再解释一下我的做法：
1.只有左括号进栈，右括号不进栈
2.栈里面记录括号在字符串的下标，这样就可以计算长度 |
i******r
发帖数: 793 | 18 re
和我想的一样
【在 p*****2 的大作中提到】
:
: 可以用stack 和 dp。不过我也是在有提示的情况下做出来的。我本来是hbase的思路。
: 但是做不对。没想到你那个思路。你这么快能想到正确的解法还是挺赞的。
: public class test
: {
: public static void main(String[] args)
: {
: Scanner in=new Scanner(System.in);
: String str=in.next();
: int[] dp=new int[str.length()];
|
m******6
发帖数: 82 | 19 stack
O(n)?
【在 p*****2 的大作中提到】
: 一个字符串里边只有 '(' 和 ')'
: 判断最长的substring, 里边的（和）是合法match的。
: 输出最长的长度和具有这个长度子串的数目。
: 比如
: (())
: 4 1
: ())()
: 2 2
|
i******r
发帖数: 793 | 20 每个括号最多进栈一次，出栈一次
当然就是O(n)的
【在 m******6 的大作中提到】
: stack
: O(n)?
|
|
|
r*****k
发帖数: 1281 | 21 大侠们帮看看对不对。。。
思想：从第一个开始扫描 遇到 (, i++
遇到 ), 如果i>0 {i--; 如果i==0 或者下一个字符不是），说明找到一个local
longest
match，reset i=0，比较这个是不是目前最大match， 是就存起来，不是就抛弃}
------------------------------------
void matchs(char* str, int& max, int &num){
int i =0; max=0, num=0;
int curr_len=0;
if(*str == '\0' || str == NULL) {max=0; num=0; return;}
//if there is a match, put the len of this match to vector
vector match;
while(*str != '\0'){
char next = *(str+1);
if(*str == '('){
i++;
}
else{
if(i>0) {
i--;
curr_len += 2;
//find a match
if(i==0 || next != ')'){
if(curr_len >= max) {
max = curr_len;
match.push_back(max);
}
curr_len=0;
i=0;
}
}
}
cout<<*str<<" i="<
str++;
}
//compute the number of matchs, which have the maximum lenth
vector::iterator it;
for(it = match.begin(); it!= match.end(); it++)
if(*it==max) num++;
} |
p*****2
发帖数: 21240 | 22
你自己run的结果对吗？
【在 r*****k 的大作中提到】
: 大侠们帮看看对不对。。。
: 思想：从第一个开始扫描 遇到 (, i++
: 遇到 ), 如果i>0 {i--; 如果i==0 或者下一个字符不是），说明找到一个local
: longest
: match，reset i=0，比较这个是不是目前最大match， 是就存起来，不是就抛弃}
: ------------------------------------
: void matchs(char* str, int& max, int &num){
: int i =0; max=0, num=0;
: int curr_len=0;
:
|
r*****k
发帖数: 1281 | 23 测试了几个小例子 是对的
不知道有没有大bug啊 |
r*****k
发帖数: 1281 | 24 太弱了 调试了一个多小时。。
【在 r*****k 的大作中提到】
: 大侠们帮看看对不对。。。
: 思想：从第一个开始扫描 遇到 (, i++
: 遇到 ), 如果i>0 {i--; 如果i==0 或者下一个字符不是），说明找到一个local
: longest
: match，reset i=0，比较这个是不是目前最大match， 是就存起来，不是就抛弃}
: ------------------------------------
: void matchs(char* str, int& max, int &num){
: int i =0; max=0, num=0;
: int curr_len=0;
:
|
m******6
发帖数: 82 | 25 input: (()))
output: 22
expected:41
【在 p*****2 的大作中提到】
:
: 你自己run的结果对吗？
|
m******6
发帖数: 82 | 26 input (()))
output:22
expected:41
【在 p*****2 的大作中提到】
:
: 你自己run的结果对吗？
|
p*****2
发帖数: 21240 | 27
are you sure?
【在 m******6 的大作中提到】
: input: (()))
: output: 22
: expected:41
|
m******6
发帖数: 82 | 28 yes, did you test?
let me check if there is typo in my version.
【在 p*****2 的大作中提到】
:
: are you sure?
|
p*****2
发帖数: 21240 | 29
dp[i]=Math.min(dp[m-1],m);
这句可以处理这种情况呀。我的已经pass了。
【在 m******6 的大作中提到】
: yes, did you test?
: let me check if there is typo in my version.
|
c*****n
发帖数: 96 | 30 像peking2说的， 这个算法对(((()(((()不成立。 我想可以再反向扫描一遍， 这次用
一个变量记录右括号的数目， 对（ ， count--, 对 ）， count++
两次扫描后， 取其大值。
【在 H***e 的大作中提到】
: keep一个左括号的count，括号对数countB
: 遇到 （ , count++;
: 遇到 ）， count--; 同时 把括号对数 countB++
: 然后 一旦遇到)并且左括号的为0了，此时说明所有前面的都不再对以后valid了，这时
: 候countB是一个候选值，跟max 比较，然后countB set to 0； 再继续。。
: 不知道对否
: 喔， 还要keep一个变量来记录当前最长长度子串的数目。
|
|
|
L***Q
发帖数: 508 | 31 大学时候学编译原理，里面讲的括号匹配就是用stack来做滴。
【在 i**********e 的大作中提到】
: 啊，你说得对，看了你的思路突然想到用 stack 来储存括号和数字就好了，不需要链
: 表，空间也省一点。
|
r*****k
发帖数: 1281 | 32 你还记得阿。我都忘了。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 L***Q 的大作中提到】
: 大学时候学编译原理，里面讲的括号匹配就是用stack来做滴。
|
L***Q
发帖数: 508 | 33 当年俺们的course project是写一个简单的compiler，把简单的C语言编译成可执行的
程序。俺用VB写的，嘿嘿，饱受鄙视
【在 r*****k 的大作中提到】
: 你还记得阿。我都忘了。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
r*****k
发帖数: 1281 | 34 唉，不错了。我都是抄你这样的牛人的。。
【在 L***Q 的大作中提到】
: 当年俺们的course project是写一个简单的compiler，把简单的C语言编译成可执行的
: 程序。俺用VB写的，嘿嘿，饱受鄙视
|
i**********e
发帖数: 1145 | 35 反例：
"()()", max = 4，但你的结果是 max = 2.
【在 r*****k 的大作中提到】
: 大侠们帮看看对不对。。。
: 思想：从第一个开始扫描 遇到 (, i++
: 遇到 ), 如果i>0 {i--; 如果i==0 或者下一个字符不是），说明找到一个local
: longest
: match，reset i=0，比较这个是不是目前最大match， 是就存起来，不是就抛弃}
: ------------------------------------
: void matchs(char* str, int& max, int &num){
: int i =0; max=0, num=0;
: int curr_len=0;
:
|
r*****k
发帖数: 1281 | 36 看怎么定义一个合法的match吧。
我的理解是（（））算一个合法match。（）（）实际上是2个合法match，每个长度为
二。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 i**********e 的大作中提到】
: 反例：
: "()()", max = 4，但你的结果是 max = 2.
|
p*****2
发帖数: 21240 | 37
题目的要求是连续最大的。()()是连续的，算一个。
【在 r*****k 的大作中提到】
: 看怎么定义一个合法的match吧。
: 我的理解是（（））算一个合法match。（）（）实际上是2个合法match，每个长度为
: 二。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
H***e
发帖数: 476 | 38 这样行不行会不会简单点：
用一个boolean[] flags 来indicate对应的括号是不是最后valid,valid就是可以组成
一对被stack pop出去
用stack来进出一遍决定此 flags (入stack的也包括括号的index,这样好写flags)
然后扫描一遍flags这个array,看连续为1的最长的连续子array， 及其个数。 |
r*****k
发帖数: 1281 | 39 那我的就不对了。
不过我觉得()()算一个不怎么make sense, 因为它其实包括了两个独立的单元。而(())
算一个很好理解，他就是一个整体。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 题目的要求是连续最大的。()()是连续的，算一个。
|
H***e
发帖数: 476 | 40 原体意思是最长的string可以组成合法的括号结构
((((((())))))) 这个算一
()()()()()这个一算一
))
【在 r*****k 的大作中提到】
: 那我的就不对了。
: 不过我觉得()()算一个不怎么make sense, 因为它其实包括了两个独立的单元。而(())
: 算一个很好理解，他就是一个整体。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
|
|
r*****k
发帖数: 1281 | 41 把我程序里面的match found condition
从if(i==0 || next != ')') 改为 if(i==0 && next != '(')应该就可以handle你这种
情况了。
-----------------------------------------------------
void matchs1(char* str, int& max, int &num){
int i =0; max=0, num=0;
int curr_len=0;
if(*str == '\0' || str == NULL) {max=0; num=0; return;}
//if there is a match, put the len of this match to vector
vector match;
while(*str != '\0'){
char next = *(str+1);
if(*str == '('){
i++;
}
else{
if(i>0) {
i--;
curr_len += 2;
//find a match
if(i==0 && next != '(')
{
if(curr_len >= max) {
max = curr_len;
match.push_back(max);
}
cout<<"max="<
curr_len=0;
i=0;
}
}
}
cout<<*str<<" i="<
str++;
}
//compute the number of matchs, which have the maximum lenth
vector::iterator it;
for(it = match.begin(); it!= match.end(); it++)
if(*it==max) num++;
}
【在 H***e 的大作中提到】
: 原体意思是最长的string可以组成合法的括号结构
: ((((((())))))) 这个算一
: ()()()()()这个一算一
:
: ))
|
i**********e
发帖数: 1145 | 42 try "(()", max = 2
【在 r*****k 的大作中提到】
: 把我程序里面的match found condition
: 从if(i==0 || next != ')') 改为 if(i==0 && next != '(')应该就可以handle你这种
: 情况了。
: -----------------------------------------------------
: void matchs1(char* str, int& max, int &num){
: int i =0; max=0, num=0;
: int curr_len=0;
:
: if(*str == '\0' || str == NULL) {max=0; num=0; return;}
:
|
r*****k
发帖数: 1281 | 43 嗯，很多bug。。
还要加强修炼。。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 i**********e 的大作中提到】
: try "(()", max = 2
|
i**********e
发帖数: 1145 | 44 应该不是ｂｕｇ的问题，而是你这个思路方向不对，无法处理所有ｃａｓｅ。
问题在于：
当你看到 ")" 的时候，你无法找到之前的 "(" 来区配。
你必须用一个 stack 来储存之前遇到的所有 "("
【在 r*****k 的大作中提到】
: 嗯，很多bug。。
: 还要加强修炼。。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
r*****k
发帖数: 1281 | 45 i其实就相当于一个stack。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 i**********e 的大作中提到】
: 应该不是ｂｕｇ的问题，而是你这个思路方向不对，无法处理所有ｃａｓｅ。
: 问题在于：
: 当你看到 ")" 的时候，你无法找到之前的 "(" 来区配。
: 你必须用一个 stack 来储存之前遇到的所有 "("
|
p*i
发帖数: 411 | 46 #include
#include
#include
using namespace std;
void process(const string& str) {
stack s, s1;
for (unsigned i = 0; i < str.size(); i++) {
if ('(' == str[i]) {
s.push(i);
} else {
if (!s.empty()) {
unsigned left = s.top(); s.pop();
unsigned& right = i;
if (s1.empty() || (s1.top()+1 < left)) {
s1.push(left);
s1.push(right);
} else if (s1.top()+1 == left) {
s1.pop();
s1.push(right);
} else {
s1.pop(); s1.pop();
s1.push(left);
s1.push(right);
}
}
}
}
unsigned max_len = 0, max_cnt = 1;
while (!s1.empty()) {
unsigned left, right;
right = s1.top(); s1.pop();
left = s1.top(); s1.pop();
unsigned len = right-left+1;
if (len > max_len) {
max_len = len; max_cnt = 1;
} else if (len == max_len) {
max_cnt++;
}
}
cout << max_len << "\t" << max_cnt << endl;
}
int main(int argc, char** argv) {
if (argc < 2) {
cout << "Usage: " << argv[0] << " str" << endl;
return 0;
}
process(argv[1]);
return 0;
}
【在 p*****2 的大作中提到】
: 一个字符串里边只有 '(' 和 ')'
: 判断最长的substring, 里边的（和）是合法match的。
: 输出最长的长度和具有这个长度子串的数目。
: 比如
: (())
: 4 1
: ())()
: 2 2
|
c*****n
发帖数: 96 | 47 int getLongestBrackets(char *str, int *num){
char *p = str;
int diff = 0;
int maxLen = 0;
int curLen = 0;
while (*p){
while (*p && *p == ')') p++;
while (*p && diff >= 0){
if (*p == '(') diff ++;
if (*p == ')') diff --;
curLen++;
}
if (*p || diff <= 0){
curLen += diff;
if (curLen > maxLen){
maxLen = curLen;
*num = 0;
} else if(curLen == maxLen){
*num += 1;
}
}
curLen = 0;
}
p--;
curLen = 0;
diff = 0;
while (p>= str){
while (p >= str && *p == '(') p--;
while (p >= str && diff >= 0){
if (*p == ')') diff ++;
if (*p == '(') diff --;
curLen ++;
}
if (p >= str || diff <= 0){
curLen += diff;
if (curLen > maxLen){
maxLen = curLen;
*num = 0;
} else if(curLen == maxLen){
*num += 1;
}
}
curLen = 0;
}
return maxLen;
} |
h********e
发帖数: 1972 | 48 O(n)算法：
扫一遍数组遇到( +1, ) -1. 把数记录在数组里。如果遇到负数就停。（后面剩下的括弧可以当做一个新问题重新处理, 显然遇到负数，那么这个 ')'无法作为合法串的一部分。 ）
把记下来的数作为key，位置作为value，散列到[0,i]的桶里面。(假设在i位置遇到负数）在每个桶里面求最大距离。 然后再在各个桶之间求最大距离。
然后处理剩下的括弧。repeat |
h********e
发帖数: 1972 | 49 O(n)算法2：
stack s; //contains, '(', numbers
int c = 0;
int max = 0;
for (i = 0 to n-1)
{
if A(i) == '(', {s.push('('); c++; }
if A(i) == ')' {
if (c == 0) break (restart the process from the next '(');
else if (s.top == '(') {
s.pop();
if (s.top is a number)) s.top += 2;
else s.push(2);
if (max < s.top) max = s.top;
}
else if (s.top is a number) // s = [... X '('N ] case
{
_n = s.pop();
s.pop(); //pop out '('
if (s.top is a number) s.top+= _n; else s.push(_n);
update max...
}
c--;
}
}
}
So finally, s will be like ((N(N(N(( where N are the numbers. |
i**********e
发帖数: 1145 | 50 你这算法会导致 O(n^2) 不是吗？
> 然后处理剩下的括弧。repeat
的括弧可以当做一个新问题重新处理, 显然遇到负数，那么这个 ')'无法作为合法串的
一部分。 ）
负数）在每个桶里面求最大距离。 然后再在各个桶之间求最大距离。
【在 h********e 的大作中提到】
: O(n)算法：
: 扫一遍数组遇到( +1, ) -1. 把数记录在数组里。如果遇到负数就停。（后面剩下的括弧可以当做一个新问题重新处理, 显然遇到负数，那么这个 ')'无法作为合法串的一部分。 ）
: 把记下来的数作为key，位置作为value，散列到[0,i]的桶里面。(假设在i位置遇到负数）在每个桶里面求最大距离。 然后再在各个桶之间求最大距离。
: 然后处理剩下的括弧。repeat
|
|
|
h********e
发帖数: 1972 | 51 不会哈。 每次做到负数 就把前面的扔了吧。剩下的括弧的意思就是出现负数以后后面的。。这个算法跟栈那个其实一样的 |
i**********e
发帖数: 1145 | 52 "()(())" 返回的是 4，不是6.
【在 p*i 的大作中提到】
: #include
: #include
: #include
: using namespace std;
: void process(const string& str) {
: stack s, s1;
: for (unsigned i = 0; i < str.size(); i++) {
: if ('(' == str[i]) {
: s.push(i);
: } else {
|
i**********e
发帖数: 1145 | 53 不是很明白，给个例子：
"(()()(())(("
标记为：
1 2 1 2 1 2 3 2 1 2 3
key->value:
1 -> 0,2,4,8
2 -> 1,3,5,7,9
3 -> 6,10
这里 在桶 1 的最大距离是 [0,8] = 8.
但是 在桶 2 的最大距离 [1,9] = 8 是不合法的。
当然，你可以很容易判定桶里面的两个 index 是否合法。但是这样不能要一个一个在
桶里取两个值来判定吧。
这里感觉漏掉了些逻辑，不知道我有没有理解正确。谢谢。
的括弧可以当做一个新问题重新处理, 显然遇到负数，那么这个 ')'无法作为合法串的
一部分。 ）
负数）在每个桶里面求最大距离。 然后再在各个桶之间求最大距离。
【在 h********e 的大作中提到】
: O(n)算法：
: 扫一遍数组遇到( +1, ) -1. 把数记录在数组里。如果遇到负数就停。（后面剩下的括弧可以当做一个新问题重新处理, 显然遇到负数，那么这个 ')'无法作为合法串的一部分。 ）
: 把记下来的数作为key，位置作为value，散列到[0,i]的桶里面。(假设在i位置遇到负数）在每个桶里面求最大距离。 然后再在各个桶之间求最大距离。
: 然后处理剩下的括弧。repeat
|
c*****n
发帖数: 96 | 54 ihasleetcode, 能否看看我的算法是否有问题？ 谢谢。
【在 i**********e 的大作中提到】
: 不是很明白，给个例子：
: "(()()(())(("
: 标记为：
: 1 2 1 2 1 2 3 2 1 2 3
: key->value:
: 1 -> 0,2,4,8
: 2 -> 1,3,5,7,9
: 3 -> 6,10
: 这里 在桶 1 的最大距离是 [0,8] = 8.
: 但是 在桶 2 的最大距离 [1,9] = 8 是不合法的。
|
i**********e
发帖数: 1145 | 55 我制造了一些测试数据，你的程序显示 Time Limit Exceeded.
不知道是哪个test 造成的，我再测试一下哈。
【在 c*****n 的大作中提到】
: ihasleetcode, 能否看看我的算法是否有问题？ 谢谢。
|
H***e
发帖数: 476 | 56 大牛帮看下有明线错误吗？
》》》
发信人: Hbase (每天都进步一点点), 信区: JobHunting
标 题: Re: 上一道题吧
发信站: BBS 未名空间站 (Wed Feb 29 19:21:56 2012, 美东)
这样行不行会不会简单点：
用一个boolean[] flags 来indicate对应的括号是不是最后valid,valid就是可以组成
一对被stack pop出去
用stack来进出一遍决定此 flags (入stack的也包括括号的index,这样好写flags)
然后扫描一遍flags这个array,看连续为1的最长的连续子array， 及其个数
【在 i**********e 的大作中提到】
: 我制造了一些测试数据，你的程序显示 Time Limit Exceeded.
: 不知道是哪个test 造成的，我再测试一下哈。
|
i**********e
发帖数: 1145 | 57 你测试过你程序吗？
"(" 这个 test case 就过不了，似乎有死循环。
【在 c*****n 的大作中提到】
: ihasleetcode, 能否看看我的算法是否有问题？ 谢谢。
|
c*****n
发帖数: 96 | 58 发现一个bug： 第2遍扫描前没有reset 变量 diff. 这可能造成死循环。我更新了code
， 麻烦你再试一下。谢谢。
【在 i**********e 的大作中提到】
: 我制造了一些测试数据，你的程序显示 Time Limit Exceeded.
: 不知道是哪个test 造成的，我再测试一下哈。
|
i**********e
发帖数: 1145 | 59 你这思路基本跟 peking2 和 itworker 的一样，只不过你的需要扫两遍.
直接利用数组储存 开括号 "(" 的下标 （或者直接储存在 stack 里）就可以了，然后
看到 ")" 的时候，可以从stack里得到对应的 "(" 的下标，直接就能得到距离了啦，
这样扫描一遍就能得到最大距离。
EDIT:
不好意思，看来逻辑还是有点漏洞，以上的算法不能处理这种情况 "()(())"，这样的话应该就必须像 peking2 用数组来保存之前的结果，然后看开括号之前的一个结果，加上去。
【在 H***e 的大作中提到】
: 大牛帮看下有明线错误吗？
: 》》》
: 发信人: Hbase (每天都进步一点点), 信区: JobHunting
: 标 题: Re: 上一道题吧
: 发信站: BBS 未名空间站 (Wed Feb 29 19:21:56 2012, 美东)
: 这样行不行会不会简单点：
: 用一个boolean[] flags 来indicate对应的括号是不是最后valid,valid就是可以组成
: 一对被stack pop出去
: 用stack来进出一遍决定此 flags (入stack的也包括括号的index,这样好写flags)
: 然后扫描一遍flags这个array,看连续为1的最长的连续子array， 及其个数
|
i**********e
发帖数: 1145 | 60 试了，还是死循环啊。
code
【在 c*****n 的大作中提到】
: 发现一个bug： 第2遍扫描前没有reset 变量 diff. 这可能造成死循环。我更新了code
: ， 麻烦你再试一下。谢谢。
|
|
|
h********e
发帖数: 1972 | 61 多谢。。跟我想象中的有点不一样。。找最大距离的时候要从一个（开始，以）结束，
这个match也很简单，找最远的就行。我的算法描述里面貌似漏了这点。。不过那个算
法最后应该会end up with the same as stack..
【在 i**********e 的大作中提到】
: 不是很明白，给个例子：
: "(()()(())(("
: 标记为：
: 1 2 1 2 1 2 3 2 1 2 3
: key->value:
: 1 -> 0,2,4,8
: 2 -> 1,3,5,7,9
: 3 -> 6,10
: 这里 在桶 1 的最大距离是 [0,8] = 8.
: 但是 在桶 2 的最大距离 [1,9] = 8 是不合法的。
|
H***e
发帖数: 476 | 62 蒽
谢谢！
的话应该就必须像 peking2 用数组来保存之前的结果，然后看开括号之前的一个结果
，加上去。
【在 i**********e 的大作中提到】
: 你这思路基本跟 peking2 和 itworker 的一样，只不过你的需要扫两遍.
: 直接利用数组储存 开括号 "(" 的下标 （或者直接储存在 stack 里）就可以了，然后
: 看到 ")" 的时候，可以从stack里得到对应的 "(" 的下标，直接就能得到距离了啦，
: 这样扫描一遍就能得到最大距离。
: EDIT:
: 不好意思，看来逻辑还是有点漏洞，以上的算法不能处理这种情况 "()(())"，这样的话应该就必须像 peking2 用数组来保存之前的结果，然后看开括号之前的一个结果，加上去。
|
p*****2
发帖数: 21240 | 63
不好意思，没时间帮你看你的答案。这题想作对可不容易。我按照以前的想法怎么做都
有漏洞，补了这个就出那个。你要想判断最好去oj一下。
【在 H***e 的大作中提到】
: 蒽
: 谢谢！
:
: 的话应该就必须像 peking2 用数组来保存之前的结果，然后看开括号之前的一个结果
: ，加上去。
|
i**********e
发帖数: 1145 | 64 我总结一下吧，其实这题标准解法就应该像 peking2 的解法一样.
itworker 的解法 只是利用 stack 记住开括号的下标，这是不够的，因为无法处理这
种情况："()()(())".每次看到关括号，只能知道区配的开括号的位置，但这不一定是
最长距离。
用数组保存之前的结果，就是因为要处理以上这样的情况。 stack 只能告诉你区配关
括号的起始位置。
我的解法用双链表也可以，思路虽然容易解释明白，但是编起来的确麻烦不少，不好写。
这题 O(n^3) 暴力解很容易想到， O(n^2) 优化也可以很直接，但是 O(n) 的解法还不
是很明显，利用了stack的特性还有基本 dp 的道理，的确很巧妙。 |
c*****n
发帖数: 96 | 65 一次性写出bug free的code太难了:(. 刚才没有编译器，就直接在网上写的code， 才
发现忘记修改循环变量的值了。 还要多练啊。
【在 i**********e 的大作中提到】
: 试了，还是死循环啊。
:
: code
|
i**********e
发帖数: 1145 | 66 对，重点在于怎么都不能处理general case，无数次的往前回溯这个道理。
【在 p*****2 的大作中提到】
:
: 不好意思，没时间帮你看你的答案。这题想作对可不容易。我按照以前的想法怎么做都
: 有漏洞，补了这个就出那个。你要想判断最好去oj一下。
|
i**********e
发帖数: 1145 | 67 真的很难。
我昨晚利用想到的双链表那个思路写代码，思路很清晰，而且双链表都有自己写好的现
成class，照理说问题不大。
结果写着写着才发现非常不好写，漏掉了一些判定条件。
所以还是要多写多练习。
【在 c*****n 的大作中提到】
: 一次性写出bug free的code太难了:(. 刚才没有编译器，就直接在网上写的code， 才
: 发现忘记修改循环变量的值了。 还要多练啊。
|
h********e
发帖数: 1972 | 68 这题我觉得如果意识到遇到负数的时候可以吧前面的都扔了。基本上stack的做法就已经出来一半了。我把bucket的方法想完的时候，stack的做法很自然就弄出来了。 |
i**********e
发帖数: 1145 | 69 恩，是的。
遇到负数的时候就代表 stack 已经清空了，没有开括号来区配了。
已经出来一半了。我把bucket的方法想完的时候，stack的做法很自然就弄出来了。
【在 h********e 的大作中提到】
: 这题我觉得如果意识到遇到负数的时候可以吧前面的都扔了。基本上stack的做法就已经出来一半了。我把bucket的方法想完的时候，stack的做法很自然就弄出来了。
|
i**********e
发帖数: 1145 | 70 测试数据已经 放在 Online Judge 了。题目为 "Longest Valid Parentheses"，方便
大家测试程序。
http://www.leetcode.com/onlinejudge
大家练练手吧。 |
|
|
p*i
发帖数: 411 | 71 感谢帮忙测试。我的已经通过了
基本思想是用一个stack s0，遇到'('就push当前的index，遇到')'就pop，说明发现一
个'('-')' pair
此时left和right分别记录这个pair的左边'('的位置和右边')'的位置
同时还有一个额外的s1，记录当前已经遇到的所有pair的左右位置
每次发现一个新的pair (lnew, rnew)，就与s1栈顶的pair(假设是lold, rold)进行比较
如果lnew == rold+1，说明他们是()()这种情况，所以需要合并
如果lnew < rold+1，说明是(())这种情况，也需要合并
一旦进行了第一个合并，就需要继续检查s1直到桟为空或者不能继续合并为止，应付()
(())这种情况
下面是我在leetcode上用的code
#include
using namespace std;
class Solution {
public:
int longestValidParentheses(string s) {
Start typing your C/C++ solution below
// DO NOT write int main() function
stack s0, s1;
for (unsigned i = 0; i < s.size(); i++) {
if ('(' == s[i]) {
s0.push(i);
} else {
if (!s0.empty()) {
unsigned left = s0.top(); s0.pop();
unsigned right = i;
while (!s1.empty()) {
if (s1.empty() || (s1.top()+1 < left)) {
// nothing to merge
break;
} else if (s1.top()+1 == left) {
s1.pop();
left = s1.top(); s1.pop();
} else if (s1.top()+1 > left) {
s1.pop(); s1.pop();
}
}
s1.push(left);
s1.push(right);
}
}
}
unsigned max_len = 0, max_cnt = 1;
while (!s1.empty()) {
unsigned left, right;
right = s1.top(); s1.pop();
left = s1.top(); s1.pop();
unsigned len = right-left+1;
if (len > max_len) {
max_len = len; max_cnt = 1;
} else if (len == max_len) {
max_cnt++;
}
}
return max_len;
}
};
【在 i**********e 的大作中提到】
: 测试数据已经 放在 Online Judge 了。题目为 "Longest Valid Parentheses"，方便
: 大家测试程序。
: http://www.leetcode.com/onlinejudge
: 大家练练手吧。
|
