学生物的还不赶紧转码工，想什么呢 - 未名空间MITBBS历史存档

学生物的还不赶紧转码工，想什么呢# Biology - 生物学

s*n2015-07-29 07:07

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; rightcurrentif (leftcurrent>=leftsize) {for (int j=rightcurrent;jright[j]=-1; break;}
if (left[leftcurrent]leftcurrent++;
}
else right[rightcurrent]=-1; //remove it
}
for (int j=leftcurrent; j}

s*n2015-07-29 07:07

2 楼

买房的时候没考虑过风水的问题，结果买的townhouse进门就是楼梯，而且空间比较小
，请问如何化解？

f*i2015-07-29 07:07

3 楼

学生物的还不赶紧转码工，想什么呢
早转早得利，自己血淋淋的经验教训

r*g2015-07-29 07:07

4 楼

MARK

B*o2015-07-29 07:07

5 楼

放绿色植物
★ Sent from iPhone App: iReader Mitbbs 7.18 - iPhone Lite

f*92015-07-29 07:07

6 楼

楼主什么经验

【在 f********i 的大作中提到】

: 学生物的还不赶紧转码工，想什么呢
: 早转早得利，自己血淋淋的经验教训

i*d2015-07-29 07:07

7 楼

直接用一个stack做左右括号匹配不就好了么？

s*n2015-07-29 07:07

8 楼

假的成么？我养不活植物。
哪种植物合适呢？

【在 B****o 的大作中提到】

: 放绿色植物
: ★ Sent from iPhone App: iReader Mitbbs 7.18 - iPhone Lite

g*02015-07-29 07:07

9 楼

等生物老中辛辛苦苦转了马工第一轮电面就被阿三使坏放倒的时候肯定会想还是原来的
中国发考题nice啊。

d*l2015-07-29 07:07

10 楼

题目有点不清楚。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);

C*r2015-07-29 07:07

11 楼

仿照明定陵，放些朱漆的箱子。

e*o2015-07-29 07:07

12 楼

马工的nice 程度跟 faculty nice 程度没有可比性。根本不在一个数量级。

【在 g********0 的大作中提到】

: 等生物老中辛辛苦苦转了马工第一轮电面就被阿三使坏放倒的时候肯定会想还是原来的
: 中国发考题nice啊。

i*d2015-07-29 07:07

13 楼

根据lz说的例子，我感觉他的意思是删除最少的括弧，使得expression是合法的。

少？

【在 d*******l 的大作中提到】

: 题目有点不清楚。s除了包含括号还包含其它字符？能做的操作有哪些，插入，删除？
: 把')'改成'('可不可以？minimum differences怎么定义？是说从s到算s1所需操作最少？
: 对于")))((("，“()()()"只改动4个字符，算不算比”“更近些呢？
:
: right

m*o2015-07-29 07:07

14 楼

赞

【在 e*******o 的大作中提到】

: 马工的nice 程度跟 faculty nice 程度没有可比性。根本不在一个数量级。

d*l2015-07-29 07:07

15 楼

那感觉就有点trivial了，就像你上面说的直接用栈把能匹配上的抵消掉，剩下就是必
须要删除的。否则没别的办法让他们合法。

【在 i**d 的大作中提到】

: 根据lz说的例子，我感觉他的意思是删除最少的括弧，使得expression是合法的。
:
: 少？

S*r2015-07-29 07:07

16 楼

为了几个钱一辈子受阿三使唤，两到三年被辞退一次，然后45岁后找不到工作？这是你
想要的生活？

【在 f********i 的大作中提到】

: 学生物的还不赶紧转码工，想什么呢
: 早转早得利，自己血淋淋的经验教训

w*x2015-07-29 07:07

17 楼

是这样的吗??
有必要用stack吗?? 计数不就得了

f*y2015-07-29 07:07

18 楼

45岁的千老被辞了可以找到工作？

【在 S****r 的大作中提到】

: 为了几个钱一辈子受阿三使唤，两到三年被辞退一次，然后45岁后找不到工作？这是你
: 想要的生活？

i*d2015-07-29 07:07

19 楼

我理解的是，用stack可以存储括弧的位置信息，以便第二次遍历的时候，把不合法的
括弧去掉。

【在 w****x 的大作中提到】

: 是这样的吗??
: 有必要用stack吗?? 计数不就得了

Z*o2015-07-29 07:07

20 楼

显然不了解千老在生物界还有别的途径可以找个稳妥钱也不少可以安稳退休的职场路径
.... :)
算了，就不告诉你了。
去转码工去吧。

【在 f*****y 的大作中提到】

: 45岁的千老被辞了可以找到工作？

d*l2015-07-29 07:07

21 楼

我就是顺着楼上那么一说。。如果题意真的是那样，这些实现细节就影响不大了

【在 w****x 的大作中提到】

: 是这样的吗??
: 有必要用stack吗?? 计数不就得了

o*e2015-07-29 07:07

22 楼

“别的途径”不外乎是到微博上去“科普”，大不了来点"安保资金"
现在国内网络上言必称科学的，除了三流本科的在校懵懂学生，剩下的不就是你们这些
成天只会把液体从这个试管倒入另一个试管的学生物学的么？
装啥装呢？

【在 Z****o 的大作中提到】

: 显然不了解千老在生物界还有别的途径可以找个稳妥钱也不少可以安稳退休的职场路径
: .... :)
: 算了，就不告诉你了。
: 去转码工去吧。

s*n2015-07-29 07:07

23 楼

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; rightcurrentif (leftcurrent>=leftsize) {for (int j=rightcurrent;jright[j]=-1; break;}
if (left[leftcurrent]leftcurrent++;
}
else right[rightcurrent]=-1; //remove it
}
for (int j=leftcurrent; j}

w*a2015-07-29 07:07

24 楼

尼玛，我们都用移液器的好伐，谁倒来倒去的？

【在 o*********e 的大作中提到】

: “别的途径”不外乎是到微博上去“科普”，大不了来点"安保资金"
: 现在国内网络上言必称科学的，除了三流本科的在校懵懂学生，剩下的不就是你们这些
: 成天只会把液体从这个试管倒入另一个试管的学生物学的么？
: 装啥装呢？

r*g2015-07-29 07:07

25 楼

MARK

s*y2015-07-29 07:07

26 楼

手拿一把移液枪，走到哪里都不慌

【在 o*********e 的大作中提到】

: “别的途径”不外乎是到微博上去“科普”，大不了来点"安保资金"
: 现在国内网络上言必称科学的，除了三流本科的在校懵懂学生，剩下的不就是你们这些
: 成天只会把液体从这个试管倒入另一个试管的学生物学的么？
: 装啥装呢？

i*d2015-07-29 07:07

27 楼

直接用一个stack做左右括号匹配不就好了么？

Z*o2015-07-29 07:07

28 楼

你果然是不知道 :)
我也继续装，多好啊！

【在 o*********e 的大作中提到】

: “别的途径”不外乎是到微博上去“科普”，大不了来点"安保资金"
: 现在国内网络上言必称科学的，除了三流本科的在校懵懂学生，剩下的不就是你们这些
: 成天只会把液体从这个试管倒入另一个试管的学生物学的么？
: 装啥装呢？

d*l2015-07-29 07:07

29 楼

题目有点不清楚。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);

o*e2015-07-29 07:07

30 楼

我当然是不知道了，而且更不屑知道。
你有什么“金点子”最好自己去实现（了先），然后写书去告诉别人有什么绝招。
千万别和饶毅11g之类的去中国叫卖什么“我有一个梦想”。
而不是现在就凭你这种装神弄鬼的“生物学式神秘法”，你去找赵本山斗吧，别跟我神
神叨叨的。

【在 Z****o 的大作中提到】

: 你果然是不知道 :)
: 我也继续装，多好啊！

i*d2015-07-29 07:07

31 楼

根据lz说的例子，我感觉他的意思是删除最少的括弧，使得expression是合法的。

少？

【在 d*******l 的大作中提到】

: 题目有点不清楚。s除了包含括号还包含其它字符？能做的操作有哪些，插入，删除？
: 把')'改成'('可不可以？minimum differences怎么定义？是说从s到算s1所需操作最少？
: 对于")))((("，“()()()"只改动4个字符，算不算比”“更近些呢？
:
: right

b*y2015-07-29 07:07

32 楼

阿三有好有坏，但起码没法拿科学，情怀忽悠人，大家一手交钱，一手交货。

【在 g********0 的大作中提到】

: 等生物老中辛辛苦苦转了马工第一轮电面就被阿三使坏放倒的时候肯定会想还是原来的
: 中国发考题nice啊。

d*l2015-07-29 07:07

33 楼

那感觉就有点trivial了，就像你上面说的直接用栈把能匹配上的抵消掉，剩下就是必
须要删除的。否则没别的办法让他们合法。

【在 i**d 的大作中提到】

: 根据lz说的例子，我感觉他的意思是删除最少的括弧，使得expression是合法的。
:
: 少？

w*x2015-07-29 07:07

34 楼

是这样的吗??
有必要用stack吗?? 计数不就得了

i*d2015-07-29 07:07

35 楼

我理解的是，用stack可以存储括弧的位置信息，以便第二次遍历的时候，把不合法的
括弧去掉。

【在 w****x 的大作中提到】

: 是这样的吗??
: 有必要用stack吗?? 计数不就得了

d*l2015-07-29 07:07

36 楼

我就是顺着楼上那么一说。。如果题意真的是那样，这些实现细节就影响不大了

【在 w****x 的大作中提到】

: 是这样的吗??
: 有必要用stack吗?? 计数不就得了

s*f2015-07-29 07:07

37 楼

//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*02015-07-29 07:07

38 楼

这个题我看到好像要求是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*s2015-07-29 07:07

39 楼

Left从左往右找左括号, Right从右往左找右括号。
left找到一个，right应该找到一个，找不到了把当前left的左括号删除。
left找不到了，right继续找，找到一个删一个。
还要记录第一个左括号的index与最后一个右括号的index(从右往左就是第一个了），
删除第一个左括号的index之前的右括号，删除最后一个右括号的index之后的左括号
Time O(n), Space O(1)