LC里的 List<List<Integer>>

以前就发现这个问题了，返回类型时，lc的默认是List<List<Integer>>
但我经常把它改为 ArrayList<ArrayList<Integer>>, 还没遇到过出错的情况。
但当提交subsets 时，就出错了。
Line 15: error: incompatible types: ArrayList<ArrayList<Integer>> cannot be converted to List<List<Integer>>


请教俩问题，
1。为啥lc要默认这个List<List<Integer>>，而不是ArrayList<ArrayList<Integer>>？

2。 subsets 这题为什么我改成ArrayList<ArrayList<Integer>>就不行了？
再补充个问题，3， 为什么lintcode经常把in[] nums 参数 改为 ArrayaList<Integer> nums, 而且是大部分都改了，为啥？多谢

1. public class Solution {
   
2.     public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
   
3.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
   
4.         ArrayList<Integer> curr = new ArrayList<Integer>();
   
5.         if(nums == null || nums.length == 0)
   
6.         {
   
7.             return result;
   
8.         }
   
9.         Arrays.sort(nums);
   
10.         subsets(nums, 0, curr, result);
    
11.         return result;
    
12.     }
    
13.    
    
14.     public void subsets(int[] nums, int j, ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result)
    
15.     {
    
16.         ArrayList<Integer> temp = new ArrayList<Integer>(curr);
    
17.         result.add(temp);
    
18.         
    
19.         for(int i = j; i < nums.length; i++)
    
20.         {
    
21.             curr.add(nums[i]);
    
22.             subsets(nums, i+1, curr, result);
    
23.             curr.remove(curr.size()-1);
    
24.         }
    
25.     }
    
26. }

复制代码

yhfyhf 发表于 2015-6-14 21:14
怎么不行，我说了那一处你就只改了那一处吗？其他地方都要改呀。还是帮你一次性改完吧，现在可以AC了。
...

你这样改，的确能ac，那我的问题又来了。

请问，为什么，在combination sum里，我们同样把它默认的List<List<Integer>> 改成ArrayList的，可以过，为啥subsets改了就不行呢？

1. public class Solution {
   
2.     public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
   
3.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
   
4.         ArrayList<Integer> curr = new ArrayList<Integer>();
   
5.         
   
6.         if(candidates == null || candidates.length == 0)
   
7.         {
   
8.             return result;
   
9.         }
   
10.         Arrays.sort(candidates);
    
11.         combinationSum(candidates, target, 0, curr, result);
    
12.         return result;
    
13.     }
    
14.    
    
15.     public void combinationSum(int[] candidates, int target, int j, ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result)
    
16.     {
    
17.         //递归的终止条件，递归一定要有终止条件
    
18.         if(target == 0)
    
19.         {
    
20.             ArrayList<Integer> temp = new ArrayList<Integer>(curr);
    
21.             result.add(temp);
    
22.             return;
    
23.         }
    
24.         
    
25.         for(int i = j; i < candidates.length; i++)
    
26.         {
    
27.             //如果该元素大于target，超过了，肯定不符合，退出
    
28.             if(target < candidates[i])
    
29.             {
    
30.                 return;
    
31.             }
    
32.             curr.add(candidates[i]);
    
33.             //递归
    
34.             combinationSum(candidates, target-candidates[i], i, curr, result);
    
35.             //如果没找到，回溯
    
36.             curr.remove(curr.size()-1);
    
37.         }
    
38.     }
    
39. }

复制代码

非常诡异。

我把中间几行放空，结果错误还是在第15行，关键是第15行就没代码
Line 15: error: incompatible types: ArrayList<ArrayList<Integer>> cannot be converted to List<List<Integer>>

1. public class Solution {
   
2.     public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
   
3.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
   
4.         ArrayList<Integer> curr = new ArrayList<Integer>();
   
5.         if(nums == null || nums.length == 0)
   
6.         {
   
7.             return result;
   
8.         }
   
9.         Arrays.sort(nums);
   
10.         subsets(nums, 0, curr, result);
    
11.         return result;
    
12.     }
    
13.    
    
14.    
    
15.    
    
16.    
    
17.    
    
18.    
    
19.     public void subsets(int[] nums, int j, ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result)
    
20.     {
    
21.       
    
22.         ArrarList<Integer> temp = new ArrayList<Integer>(curr);
    
23.         result.add(temp);
    
24.         
    
25.         for(int i = j; i < nums.length; i++)
    
26.         {
    
27.             curr.add(nums[i]);
    
28.             subsets(nums, i+1, curr, result);
    
29.             curr.remove(curr.size()-1);
    
30.         }
    
31.     }
    
32. }

复制代码

把lz的代码改成这样就过了。

保持原本函数的List<List<Integer>>，instantiate的时候用 new ArrayList<List<Integer>>(); 原因和楼上几位说的一样， List作为interface不能建instance，但是ArrayList可以。这样的写法是为了更好的利用多态。

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        ArrayList<Integer> curr = new ArrayList<Integer>();
        if(nums == null || nums.length == 0)
        {
            return result;
        }
        Arrays.sort(nums);
        subsets(nums, 0, curr, result);
        return result;
    }
   
    public void subsets(int[] nums, int j, ArrayList<Integer> curr, List<List<Integer>> result)
    {
        ArrayList<Integer> temp = new ArrayList<Integer>(curr);
        result.add(temp);
        
        for(int i = j; i < nums.length; i++)
        {
            curr.add(nums[i]);
            subsets(nums, i+1, curr, result);
            curr.remove(curr.size()-1);
        }
    }
}

／／ 随便说说啊，错了别打我 －，－

1. ArrayList是List interface的一种实现，要求返回list我觉得可能：一是认为这样是好的Java编程风格，二是不需要管你程序里面用的具体到底是哪个list interface 的实现，其他程序调用这个method的时候只要call method of list interface 就可以，i.e. for polymorphism.
2. 我猜测是OJ并不能识别overload, 他看你写了同名函数于是就会试着直接用他的testcase去测试，于是就错了。你在其他题目里面用过overload 吗？

错误里的15行是哪一行？

List是一个interface，而ArrayList是实现了List interface的一个class。以List作为参数类型，意味着它可以接受所有实现了List interface的类作为参数，比如LinkedList。这就是所谓的“Program to interface, not implementation”。

至于第二问，你要先确定出错的究竟是哪一行。

pyx115 发表于 2015-6-14 19:42
／／ 随便说说啊，错了别打我 －，－

1. ArrayList是List interface的一种实现，要求返回list我觉得可能 ...

多谢回答

我试着改了第二个方法名，还是报错

不过，我把我代码放到eclipse，是正确的代码

yhfyhf 发表于 2015-6-14 19:44
错误里的15行是哪一行？

多谢回答

lc 报的15行就是 {

不过，我把我代码放到eclipse，是正确的代码

stellari 发表于 2015-6-14 19:54
List是一个interface，而ArrayList是实现了List interface的一个class。以List作为参数类型，意味着它可以 ...

多谢回答

lc 报的15行就是 {，你把我代码放到lc去看看？

不过，我把我代码放到eclipse，是正确的代码

try ArrayList<List<Integer>>

用这个：List<List<Integer>> result = new ArrayList<>();   

List是Interface，可以用ArrayList, LinkedList等来实现。将result声明为List，是为了实现多态。

想一下，假设我还有个函数 public void doSomething(List<Integer> list)，用来对List<Integer>类型进行处理。这时，就不用管List的具体实现方式，ArrayList和LinkedList都可以处理。所以，多态的好处是，变量的具体类型，程序运行期间才确定。而不用对ArrayList和LinkedList都各自写一遍函数。

yhfyhf 发表于 2015-6-14 20:33
用这个：List result = new ArrayList();   

List是Interface，可以用ArrayList, LinkedList等来实现。 ...

谢谢。但依然不行