Twitter电面

Dream_Hunter 发表于 2016-3-24 08:20
就是当栈为空的时候。如果发现是“（”就push进去。如果是“）”就不做处理，顺便把当前长度改为0.
其次 ...

比如说(())和()()这两种情况的话，后一种用这个方法输出的就是()()，那前一种第二次pop“（”的时候你怎么知道他是在第一次pop出来的“（”前面push进去的而不是后来push进去的呢？

补充内容 (2016-3-24 09:19):
不知道有没有表达清楚，就是括号输出也要按照顺序，"(()())"的话输出也要是"(()())"而不能是“()()()”

norafang 发表于 2016-3-24 09:14
比如说(())和()()这两种情况的话，后一种用这个方法输出的就是()()，那前一种第二次pop“（”的时候你怎 ...

def longestSubsequence(s):
     #use stack and a int to record maxlength
     #if the stack append again, we need to recalculate the maxlength
    maxlength = 0
    length = 0
    stack = []
    rs = ""
    maxrs = ""
    for c in s:
        if not stack:
            if c ==")":
                length = 0
                rs = ""
            else:
                stack.append(c)
                rs +="("
        else:
            if c == "(":
                stack.append(c)
                rs +="("
            else:
                if stack.pop() == "(":
                    length +=2
                    rs +=")"
                # else:
                #     length = 0
        if len(maxrs)<len(rs):
            maxrs = rs
        if maxlength<length:
            maxlength = length
    return maxlength,maxrs

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

sorry我题目看错了。。其实道理一样。你可以用一个string来记录当前走过的parenthesis。然后判断stirng的长度，保留长度最长那个。这样其实就不用maxlength了。。我一直以为是要求最大长度。

求问楼主是什么职位？多谢！

jiebour 发表于 2016-3-25 11:38
求问楼主是什么职位？多谢！

SWE, entry level role

楼主是这个代码的意思么

1. public class Solution {
   
2.   public String findLongestWellFormatedSubstring(String s) {
   
3.     String ret = "";
   
4.     Deque<Integer> stack = new ArrayDeque<>();
   
5.     for (int i = 0; i < s.length(); i++) {
   
6.       if (s.charAt(i) == '(') {
   
7.         stack.push(i);
   
8.       } else if (s.charAt(i) == ')') {
   
9.         if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
   
10.           stack.pop();
    
11.           int idx = stack.isEmpty() ? -1 : stack.peek();
    
12.           if (i - idx > ret.length()) {
    
13.             ret = s.substring(idx + 1, i + 1);
    
14.           }
    
15.         }
    
16.       }
    
17.     }
    
18.     return ret;
    
19.   }
    
20. 
    
21.   public int findLongestWellFormatedSubstringLength(String s) {
    
22.     int ret = 0;
    
23.     Deque<Integer> stack = new ArrayDeque<>();
    
24.     for (int i = 0; i < s.length(); i++) {
    
25.       if (s.charAt(i) == '(') {
    
26.         stack.push(i);
    
27.       } else if (s.charAt(i) == ')') {
    
28.         if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
    
29.           stack.pop();
    
30.           ret = Math.max(ret, i - (stack.isEmpty() ? -1 : stack.peek()));
    
31.         }
    
32.       }
    
33.     }
    
34.     return ret;
    
35.   }
    
36. 
    
37.   public static void main(String[] args) {
    
38.     Solution ss = new Solution();
    
39.     String s = "((()())";
    
40.     System.out.println(ss.findLongestWellFormatedSubstringLength(s));
    
41.     System.out.println(ss.findLongestWellFormatedSubstring(s));
    
42.   }
    
43. }
    

复制代码

sealove999 发表于 2016-3-27 01:55
楼主是这个代码的意思么

刚才那个是错的，看这个

1. public class Solution {
   
2.   public String findLongestWellFormatedSubstring(String s) {
   
3.     String ret = "";
   
4.     Deque<Integer> stack = new ArrayDeque<>();
   
5.     for (int i = 0; i < s.length(); i++) {
   
6.       if (s.charAt(i) == ')' && (!stack.isEmpty() && s.charAt(stack.peek()) == '(')) {
   
7.         stack.pop();
   
8.         int idx = stack.isEmpty() ? -1 : stack.peek();
   
9.         if (i - idx > ret.length()) {
   
10.           ret = s.substring(idx + 1, i + 1);
    
11.         }
    
12.       } else {
    
13.         stack.push(i);
    
14.       }
    
15.     }
    
16.     return ret;
    
17.   }
    
18. 
    
19.   public int findLongestWellFormatedSubstringLength(String s) {
    
20.     int ret = 0;
    
21.     Deque<Integer> stack = new ArrayDeque<>();
    
22.     for (int i = 0; i < s.length(); i++) {
    
23.       if (s.charAt(i) == '(') {
    
24.         stack.push(i);
    
25.       } else if (s.charAt(i) == ')') {
    
26.         if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
    
27.           stack.pop();
    
28.           ret = Math.max(ret, i - (stack.isEmpty() ? -1 : stack.peek()));
    
29.         } else {
    
30.           stack.push(i);
    
31.         }
    
32.       }
    
33.     }
    
34.     return ret;
    
35.   }
    
36. 
    
37.   public static void main(String[] args) {
    
38.     Solution ss = new Solution();
    
39.     String s = ")(()())";
    
40.     System.out.println(ss.findLongestWellFormatedSubstringLength(s));
    
41.     System.out.println(ss.findLongestWellFormatedSubstring(s));
    
42.   }
    
43. }
    

复制代码

sealove999 发表于 2016-3-27 02:03
刚才那个是错的，看这个

不是求最长substring是最长subsequence, 所以()))(()()) 的话要返回()(()())

norafang 发表于 2016-3-29 02:11
不是求最长substring是最长subsequence, 所以()))(()()) 的话要返回()(()())

楼主好棒

1. public class Solution {
   
2.   public String findLongestWellFormatedSubstring(String s) {
   
3.     StringBuilder sb = new StringBuilder();
   
4.     String ret = "";
   
5.     Deque<Integer> stack = new ArrayDeque<>();
   
6.     for (int i = 0; i < s.length(); i++) {
   
7.       if (s.charAt(i) == ')' && (!stack.isEmpty() && s.charAt(stack.peek()) == '(')) {
   
8.         stack.pop();
   
9.         int idx = stack.isEmpty() ? -1 : stack.peek();
   
10.         if (i - idx > ret.length()) {
    
11.           ret = s.substring(idx + 1, i + 1); // current longest substring
    
12.         }
    
13.       } else {
    
14.         stack.push(i);
    
15.         if (s.charAt(i) == ')') {
    
16.           sb.append(ret); // invalid
    
17.           ret = "";
    
18.         }
    
19.       }
    
20.     }
    
21.     sb.append(ret); // last
    
22.     return sb.toString();
    
23.   }
    
24. 
    
25.   public static void main(String[] args) {
    
26.     Solution ss = new Solution();
    
27.     String s = "()))(()())";
    
28.     System.out.println(ss.findLongestWellFormatedSubstring(s));
    
29.   }
    
30. }
    

复制代码

最长subsequence不是连续的也可以的喽？每次合法的都得加上去？

Dream_Hunter 发表于 2016-3-29 04:08
最长subsequence不是连续的也可以的喽？每次合法的都得加上去？

是的～～～～～～～～～～