Twitter电面

请问lz可以把题目说的再仔细一点么？？给的string是只有括号么？还有well formed的requirement都有什么？？
谢谢谢～～

我没理解错误的话。。。
def longestSubsequence(s):
     #use stack and a int to record maxlength
     #if we find it's unmatch, we need to recalculate the maxlength
    maxlength = 0
    length = 0
    stack = []
    for c in s:
        if not stack:
            if c ==")":
                length = 0
            else:
                stack.append(c)
        else:
            if c == "(":
                stack.append(c)
            else:
                if stack.pop() == "(":
                    length +=2
                else:
                    length = 0
        if maxlength<length:
            maxlength = length
    return maxlength

print longestSubsequence("()((()))())")

补充内容 (2016-3-24 08:22):
else:length = 0 #这两行可以注释掉。stack里面不可能有“）”

我感觉用个栈，每弹出来一个括号长度+2. 应该就可以了

有几个build xxxx好像还蛮不错，而且是中国人主导的

alanyip 发表于 2016-3-23 07:15
楼主是什么时候完成问卷的? 我们才刚刚收到问卷

上上周吧～～～～～

jiebour 发表于 2016-3-23 07:51
听说最近网申有很多拿到twitter OA的？thanks

这个我就不清楚啦～

Teamocara 发表于 2016-3-23 08:00
请问lz可以把题目说的再仔细一点么？？给的string是只有括号么？还有well formed的requirement都有什么？？ ...

他给的例子是只有括号的，well formed意思就是要是成对的括号才算，单个不行

singku 发表于 2016-3-23 08:17
我感觉用个栈，每弹出来一个括号长度+2. 应该就可以了

不行的，这道题的难点在于max sebsequent, 比如(()()),最外面的那个括号也算是合法的，所以输出也应该是(()())， 记录长度是不行的

Dream_Hunter 发表于 2016-3-23 08:13
我没理解错误的话。。。
def longestSubsequence(s):
     #use stack and a int to record maxlength

不是很懂你的这个解法，但是我当时也说了记录长度这种做法，烙印说不行啊

norafang 发表于 2016-3-24 07:28
不是很懂你的这个解法，但是我当时也说了记录长度这种做法，烙印说不行啊

就是当栈为空的时候。如果发现是“（”就push进去。如果是“）”就不做处理，顺便把当前长度改为0.
其次栈不为空的时候。如果继续发现“（”就继续push进去。直到发现“）”就从栈里pop出来.我发现我多写了一句else：length=0.。因为栈里不可能有“）”。。sorry

补充内容 (2016-3-24 08:24):
pop出来的同时长度加2.

补充内容 (2016-3-24 08:24):
pop出来的同时长度加2.

补充内容 (2016-3-24 08:24):
pop出来的时候长度加2