狗家跪经

第二题用了个hashset自动去重，不知道我这么做是不是naive了。。

1. import java.util.*;
   
2. 
   
3. public class CommonAndDiffElement {
   
4.         public static void main (String[] args) {
   
5.                 int[] s1 = new int[]{1, 2, 3, 4};
   
6.                 int[] s2 = new int[]{1, 3, 4, 5};
   
7.                 List<Integer> c = common(s1, s2);
   
8.                 System.out.println(c);
   
9.                 List<Integer> d = diff(s1, s2);
   
10.                 System.out.println(d);
    
11.         }
    
12.         private static List<Integer> common(int[] s1, int[] s2) {
    
13.                 List<Integer> res = new ArrayList<>();
    
14.                 if (s1 == null || s1.length == 0) return res;
    
15.                 if (s2 == null || s2.length == 0) return res;
    
16.                 Set<Integer> set = new HashSet<>();
    
17.                 for (int num : s1) {
    
18.                         set.add(num);
    
19.                 }
    
20.                 for (int num : s2) {
    
21.                         if (set.contains(num)) {
    
22.                                 res.add(num);
    
23.                         }
    
24.                 }
    
25.                 return res;
    
26.         }
    
27.         private static List<Integer> diff(int[] s1, int[] s2) {
    
28.                 List<Integer> res = new ArrayList<>();
    
29.                 if (s1 == null || s1.length == 0) return res;
    
30.                 if (s2 == null || s2.length == 0) return res;
    
31.                 Set<Integer> set = new HashSet<>();
    
32.                 for (int num : s1) {
    
33.                         set.add(num);
    
34.                 }
    
35.                 for (int num : s2) {
    
36.                         if (!set.contains(num)) {
    
37.                                 res.add(num);
    
38.                         }
    
39.                 }
    
40.                 Set<Integer> set2 = new HashSet<>();
    
41.                 for (int num : s2) {
    
42.                         set2.add(num);
    
43.                 }
    
44.                 for (int num : s1) {
    
45.                         if (!set2.contains(num)) {
    
46.                                 res.add(num);
    
47.                         }
    
48.                 }
    
49.                 return res;
    
50.         }
    
51. }

复制代码

直接保存深度就可以吧，感觉保存index不太好写

1.     public static List<List<Integer>> test1(String str) {
   
2.         char[] arr = str.toCharArray();
   
3.         Stack<Integer> depth = new Stack<>();
   
4.         List<List<Integer>> list = new ArrayList<>();
   
5.         int count=0;
   
6.         for (int i=0;i<arr.length;i++){
   
7.             if (arr[i]=='('){
   
8.                 List<Integer> tmp = new ArrayList<>();
   
9.                 tmp.add(i);
   
10.                 list.add(tmp);
    
11.                 depth.push(count);
    
12.                 count++;
    
13.             }
    
14.             else{
    
15.                 int leftindex = depth.pop();
    
16.                 list.get(leftindex).add(i);
    
17.             }
    
18.         }
    
19.         return list;
    
20.     }
    

复制代码

taoqi610 发表于 2017-1-3 09:55
直接保存深度就可以吧，感觉保存index不太好写

忘了说是第一题

1. public List<List<Integer>> parenIndex1(String s){
   
2.                 List<List<Integer>> rst=new ArrayList<>();
   
3.                 if(s==null||s.length()==0) return rst;
   
4.                 List<List<Integer>> tmprst=new ArrayList<>();
   
5.                 Stack<Integer> stack=new Stack<>();
   
6.                 for(int i=0;i<s.length();i++){
   
7.                         if(s.charAt(i)=='('){
   
8.                                 stack.push(i);
   
9.                         }else{
   
10.                                 int smallIndex=stack.pop();
    
11.                                 List<Integer> list=new ArrayList<>();
    
12.                                 list.add(smallIndex);
    
13.                                 list.add(i);
    
14.                                 if(stack.isEmpty()){
    
15.                                         rst.add(list);
    
16.                                         for(List<Integer> iter:tmprst){
    
17.                                                 List<Integer> toadd=new ArrayList<>(iter);
    
18.                                                 rst.add(toadd);
    
19.                                         }
    
20.                                         tmprst.clear();
    
21.                                 }else{
    
22.                                         tmprst.add(list);
    
23.                                 }
    
24.                                
    
25.                         }
    
26.                 }
    
27.                 return rst;
    
28.         }

复制代码

把楼主的大致思路实现了一下，感觉只要输入是合法的，就是每个 ')' 之前一定有对应的 '(' 的话这个方法应该没啥问题吧

1. public List<List<Integer>> parenIndex2(String s){
   
2.                 List<List<Integer>> rst=new LinkedList<>();
   
3.                 if(s==null||s.length()==0) return rst;
   
4.                 Stack<Integer> stack=new Stack<>();
   
5.                 Stack<List<Integer>> liststack=new Stack<>();
   
6.                 for(int i=s.length()-1;i>=0;i--){
   
7.                         if(s.charAt(i)==')'){
   
8.                                 stack.push(i);
   
9.                         }else{
   
10.                                 int largeIndex=stack.pop();
    
11.                                 List<Integer> list=new ArrayList<>();
    
12.                                 list.add(i);
    
13.                                 list.add(largeIndex);
    
14.                                 liststack.push(list);
    
15.                         }
    
16.                 }
    
17.                
    
18.                 while(!liststack.isEmpty()){
    
19.                         rst.add(liststack.pop());
    
20.                 }
    
21.                 return rst;
    
22.                 }

复制代码

楼上有两位说的从后往前扫，然后逆序输出的思路挺好的。不过要逆序输出的话得再用个栈吧？List<List<>>这种貌似没有addFirst()的方法

您好！
本帖隐藏的内容需要积分高于 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

taoqi610 发表于 2017-1-2 20:55
直接保存深度就可以吧，感觉保存index不太好写

我的思路跟你的其实一样，只不过我用的Array。。。一个数组保存index，然后直接插入该index：

1. public class Solution {
   
2.     public static String[] test1(String str) {
   
3.         String[] res = new String[str.length()/2];
   
4.         char[] chars = str.toCharArray();
   
5.         int leftnum = 0;
   
6.         int[] numofleft = new int[str.length()];
   
7.         Stack<Integer> stack = new Stack<>();
   
8.         for(int i = 0; i<chars.length; i++){
   
9.             char c = chars[i];
   
10.             if(c=='('){
    
11.                 stack.push(i);
    
12.                 numofleft[i] = leftnum;
    
13.                     leftnum++;
    
14.             }else if(c == ')'){
    
15.                 String tmp = "";
    
16.                 int left = stack.pop();
    
17.                 tmp += left+",";
    
18.                 tmp += i;
    
19.                 // the next line has ensured the sequence;
    
20.                 res[numofleft[left]] = tmp;              
    
21.             }
    
22.         }
    
23.         for(String s: res){
    
24.                 System.out.println(s);
    
25.         }
    
26.         
    
27.         return res;
    
28.     }
    
29.     public static void main(String[] args){
    
30.             test1("(())(())()()");
    
31.     }
    
32. }

复制代码

第二轮第二题，求一个二叉树的最大路径 返回路径， 最大路径指的什么，是找路径上各点和最大类似lc 124 Binary Tree Maximum Path Sum，要把这个路径输出，还是找就是节点最多的一条路径？有没有限制只是parent 到child 不能是left + root + right这种，还是任意路径，楼主能解释一下吗？感谢！