Twitter电面

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

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不是连续的也可以的喽？每次合法的都得加上去？

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