狗家跪经

第一题

1. import java.lang.reflect.Array;
   
2. import java.util.*;
   
3. 
   
4. public class Solution {
   
5.     public List<List<Integer>> test1(String str) {
   
6.         List<List<Integer>> res = new ArrayList<>();
   
7.         char[] chars = str.toCharArray();
   
8.         Stack<Integer> stack = new Stack<>();
   
9.         for(int i = 0; i<chars.length; i++){
   
10.             char c = chars[i];
    
11.             if(c=='('){
    
12.                 stack.push(i);
    
13.             }else if(c == ')'){
    
14.                 List<Integer> tmp = new ArrayList<>();
    
15.                 int left = stack.pop();
    
16.                 tmp.add(left);
    
17.                 tmp.add(i);
    
18. 
    
19.                 if(left < res.size()) res.add(left, tmp);
    
20.                 else res.add(tmp);
    
21.             }
    
22.         }
    
23.         return res;
    
24.     }
    
25. }
    

复制代码

补充内容 (2017-1-3 06:12):
应该是 if(left/2 < res.size()) res.add(left/2, tmp);

第二题

1. import java.lang.reflect.Array;
   
2. import java.util.*;
   
3. 
   
4. public class Solution {
   
5.     public List<List<Integer>> test1(int[] nums1, int[] nums2) {//nums1和nums2是sorted
   
6.         //nums1和nums2可以有重复 例如
   
7.         //int[] nums1 = {1,1,1,2,2,2,2,3,3,4,4,4};
   
8.         //int[] nums2 = {1,1,3,3,4,4,4,5,5,5,5,5,5,5,5};
   
9.         List<List<Integer>> res = new ArrayList<>();
   
10.         List<Integer> diff = new ArrayList<>();
    
11.         List<Integer> common = new ArrayList<>();
    
12.         res.add(diff); res.add(common);
    
13. 
    
14.         int p1 = 0;
    
15.         int p2 = 0;
    
16. 
    
17.         while(p1<nums1.length || p2<nums2.length){
    
18.             if(p2 == nums2.length || ( p1 < nums1.length && nums1[p1] < nums2[p2])){
    
19.                 diff.add(nums1[p1++]);
    
20.             }else if(p1 == nums1.length || nums1[p1] > nums2[p2]){
    
21.                 diff.add(nums2[p2++]);
    
22.             }else{
    
23.                 common.add(nums1[p1]);
    
24.                 p1++; p2++;
    
25.             }
    
26.             while(p1 > 0 && p1 < nums1.length && nums1[p1] == nums1[p1-1]) p1++;
    
27.             while(p2 > 0 && p2 < nums2.length && nums2[p2] == nums2[p2-1]) p2++;
    
28.         }
    
29.         return res;
    
30.     }
    
31. }
    

复制代码

吃啥才算成熟 发表于 2017-1-2 01:58
第一题

(())(()())能过？

第一题在stack里面存结果的index，'('的时候把string的index加到结果里，碰到')‘再把另一个index加上去

第一题顺序要对的话可以从右往左扫，完了逆序输出

吃啥才算成熟 发表于 2017-1-2 02:16
第二题

问下第二题为什么判断里要加 nums1[p1] < nums2[p2]？

sixtysix 发表于 2017-1-3 05:50
问下第二题为什么判断里要加 nums1 < nums2？

two pointers 两个数要是不等 加入diff 移动较小的数的pointer；要是相等 加入common 两个pointer都移动。

mirrorlol501 发表于 2017-1-2 05:43
(())(()())能过？

嗯 改了一下

第一题感觉从后往前逆序push, pop index会比较好。

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

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