s*****n
发帖数: 994 | 1 Implement a function string balanceParanthesis(string s); which given a
string s consisting of some parenthesis returns a string s1 in which
parenthesis are balanced and differences between s and s1 are minimum.
Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
")))(((" -> ""
Is my idea correct:?
void eliminate (int left[], int right[],leftsize, rightsize)//in left right
there are position info. left[0] is the position of first left paranthesis
{
sort (left, left+leftsize);
sort (right, right+rightsize);
int leftcurrent=0, rightcurrent;
for (int rightcurrent=0; rightcurrent
if (leftcurrent>=leftsize) {for (int j=rightcurrent;j
right[j]=-1; break;}
if (left[leftcurrent]
leftcurrent++;
}
else right[rightcurrent]=-1; //remove it
}
for (int j=leftcurrent; j
} |
r*******g
发帖数: 1335 | |
i**d
发帖数: 357 | |
d*******l
发帖数: 338 | 4 题目有点不清楚。s除了包含括号还包含其它字符？能做的操作有哪些，插入，删除？
把')'改成'('可不可以？minimum differences怎么定义？是说从s到算s1所需操作最少？
对于")))((("，“()()()"只改动4个字符，算不算比”“更近些呢？
right
【在 s*****n 的大作中提到】
: Implement a function string balanceParanthesis(string s); which given a
: string s consisting of some parenthesis returns a string s1 in which
: parenthesis are balanced and differences between s and s1 are minimum.
: Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
: ")))(((" -> ""
: Is my idea correct:?
: void eliminate (int left[], int right[],leftsize, rightsize)//in left right
: there are position info. left[0] is the position of first left paranthesis
: {
: sort (left, left+leftsize);
|
i**d
发帖数: 357 | 5 根据lz说的例子，我感觉他的意思是删除最少的括弧，使得expression是合法的。
少？
【在 d*******l 的大作中提到】
: 题目有点不清楚。s除了包含括号还包含其它字符？能做的操作有哪些，插入，删除？
: 把')'改成'('可不可以？minimum differences怎么定义？是说从s到算s1所需操作最少？
: 对于")))((("，“()()()"只改动4个字符，算不算比”“更近些呢？
:
: right
|
d*******l
发帖数: 338 | 6 那感觉就有点trivial了，就像你上面说的直接用栈把能匹配上的抵消掉，剩下就是必
须要删除的。否则没别的办法让他们合法。
【在 i**d 的大作中提到】
: 根据lz说的例子，我感觉他的意思是删除最少的括弧，使得expression是合法的。
:
: 少？
|
w****x
发帖数: 2483 | 7 是这样的吗??
有必要用stack吗?? 计数不就得了 |
i**d
发帖数: 357 | 8 我理解的是，用stack可以存储括弧的位置信息，以便第二次遍历的时候，把不合法的
括弧去掉。
【在 w****x 的大作中提到】
: 是这样的吗??
: 有必要用stack吗?? 计数不就得了
|
|
d*******l
发帖数: 338 | 9 我就是顺着楼上那么一说。。如果题意真的是那样，这些实现细节就影响不大了
【在 w****x 的大作中提到】
: 是这样的吗??
: 有必要用stack吗?? 计数不就得了
|
s*****n
发帖数: 994 | 10 Implement a function string balanceParanthesis(string s); which given a
string s consisting of some parenthesis returns a string s1 in which
parenthesis are balanced and differences between s and s1 are minimum.
Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
")))(((" -> ""
Is my idea correct:?
void eliminate (int left[], int right[],leftsize, rightsize)//in left right
there are position info. left[0] is the position of first left paranthesis
{
sort (left, left+leftsize);
sort (right, right+rightsize);
int leftcurrent=0, rightcurrent;
for (int rightcurrent=0; rightcurrent
if (leftcurrent>=leftsize) {for (int j=rightcurrent;j
right[j]=-1; break;}
if (left[leftcurrent]
leftcurrent++;
}
else right[rightcurrent]=-1; //remove it
}
for (int j=leftcurrent; j
} |
|
|
r*******g
发帖数: 1335 | |
i**d
发帖数: 357 | 12 直接用一个stack做左右括号匹配不就好了么？ |
d*******l
发帖数: 338 | 13 题目有点不清楚。s除了包含括号还包含其它字符？能做的操作有哪些，插入，删除？
把')'改成'('可不可以？minimum differences怎么定义？是说从s到算s1所需操作最少？
对于")))((("，“()()()"只改动4个字符，算不算比”“更近些呢？
right
【在 s*****n 的大作中提到】
: Implement a function string balanceParanthesis(string s); which given a
: string s consisting of some parenthesis returns a string s1 in which
: parenthesis are balanced and differences between s and s1 are minimum.
: Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
: ")))(((" -> ""
: Is my idea correct:?
: void eliminate (int left[], int right[],leftsize, rightsize)//in left right
: there are position info. left[0] is the position of first left paranthesis
: {
: sort (left, left+leftsize);
|
i**d
发帖数: 357 | 14 根据lz说的例子，我感觉他的意思是删除最少的括弧，使得expression是合法的。
少？
【在 d*******l 的大作中提到】
: 题目有点不清楚。s除了包含括号还包含其它字符？能做的操作有哪些，插入，删除？
: 把')'改成'('可不可以？minimum differences怎么定义？是说从s到算s1所需操作最少？
: 对于")))((("，“()()()"只改动4个字符，算不算比”“更近些呢？
:
: right
|
d*******l
发帖数: 338 | 15 那感觉就有点trivial了，就像你上面说的直接用栈把能匹配上的抵消掉，剩下就是必
须要删除的。否则没别的办法让他们合法。
【在 i**d 的大作中提到】
: 根据lz说的例子，我感觉他的意思是删除最少的括弧，使得expression是合法的。
:
: 少？
|
w****x
发帖数: 2483 | 16 是这样的吗??
有必要用stack吗?? 计数不就得了 |
i**d
发帖数: 357 | 17 我理解的是，用stack可以存储括弧的位置信息，以便第二次遍历的时候，把不合法的
括弧去掉。
【在 w****x 的大作中提到】
: 是这样的吗??
: 有必要用stack吗?? 计数不就得了
|
d*******l
发帖数: 338 | 18 我就是顺着楼上那么一说。。如果题意真的是那样，这些实现细节就影响不大了
【在 w****x 的大作中提到】
: 是这样的吗??
: 有必要用stack吗?? 计数不就得了
|
s*******f
发帖数: 1114 | 19 //Implement a function string balanceParanthesis(string s); which given a
//string s consisting of some parenthesis returns a string s1 in which
//parenthesis are balanced and differences between s and s1 are minimum.
//Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
//")))(((" -> ""
void DelBrackets(char *str){
if (!str)
return;
deque sc;
deque sp;
char *p = str;
while (*p){
if (*p == '('){
sc.push_back('(');
sp.push_back(p);
}else if (*p == ')'){
if (!sc.empty() && sc.back() == '('){
sc.pop_back();
sp.pop_back();
}else{
sc.push_back(')');
sp.push_back(p);
}
}
++p;
}
p = str;
char *q = str;
while (*q){
if (q == sp.front()){
++q;
sp.pop_front();
}else{
*p++ = *q++;
}
}
*p = '\0';
}
right
【在 s*****n 的大作中提到】
: Implement a function string balanceParanthesis(string s); which given a
: string s consisting of some parenthesis returns a string s1 in which
: parenthesis are balanced and differences between s and s1 are minimum.
: Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
: ")))(((" -> ""
: Is my idea correct:?
: void eliminate (int left[], int right[],leftsize, rightsize)//in left right
: there are position info. left[0] is the position of first left paranthesis
: {
: sort (left, left+leftsize);
|
l*******0
发帖数: 176 | 20 这个题我看到好像要求是O(n)的时间，O(1)的空间..
【在 s*******f 的大作中提到】
: //Implement a function string balanceParanthesis(string s); which given a
: //string s consisting of some parenthesis returns a string s1 in which
: //parenthesis are balanced and differences between s and s1 are minimum.
: //Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
: //")))(((" -> ""
: void DelBrackets(char *str){
: if (!str)
: return;
: deque sc;
: deque sp;
|
e***s
发帖数: 799 | 21 Left从左往右找左括号, Right从右往左找右括号。
left找到一个，right应该找到一个，找不到了把当前left的左括号删除。
left找不到了，right继续找，找到一个删一个。
还要记录第一个左括号的index与最后一个右括号的index(从右往左就是第一个了），
删除第一个左括号的index之前的右括号，删除最后一个右括号的index之后的左括号
Time O(n), Space O(1) |
