一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2146|回复: 26
收起左侧

[算法题] LC里的 List<List<Integer>>

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-14 19:06:12 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 love1point 于 2015-6-14 20:31 编辑

以前就发现这个问题了,返回类型时,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. }
复制代码
pyx115 发表于 2015-6-14 19:42:33 | 显示全部楼层
本帖最后由 pyx115 于 2015-6-14 19:47 编辑

// 随便说说啊,错了别打我 -,-

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

使用道具 举报

yhfyhf 发表于 2015-6-14 19:44:21 | 显示全部楼层
错误里的15行是哪一行?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-14 19:54:50 | 显示全部楼层
List是一个interface,而ArrayList是实现了List interface的一个class。以List作为参数类型,意味着它可以接受所有实现了List interface的类作为参数,比如LinkedList。这就是所谓的“Program to interface, not implementation”。

至于第二问,你要先确定出错的究竟是哪一行。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 20:09:02 | 显示全部楼层
pyx115 发表于 2015-6-14 19:42
// 随便说说啊,错了别打我 -,-

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

多谢回答

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

不过,我把我代码放到eclipse,是正确的代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 20:09:40 | 显示全部楼层
yhfyhf 发表于 2015-6-14 19:44
错误里的15行是哪一行?

多谢回答

lc 报的15行就是 {

不过,我把我代码放到eclipse,是正确的代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 20:10:22 | 显示全部楼层
stellari 发表于 2015-6-14 19:54
List是一个interface,而ArrayList是实现了List interface的一个class。以List作为参数类型,意味着它可以 ...

多谢回答

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

不过,我把我代码放到eclipse,是正确的代码
回复 支持 反对

使用道具 举报

flyingcatok 发表于 2015-6-14 20:16:01 | 显示全部楼层
try ArrayList<List<Integer>>
回复 支持 反对

使用道具 举报

yhfyhf 发表于 2015-6-14 20:33:39 | 显示全部楼层
用这个: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都各自写一遍函数。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 20:43:54 | 显示全部楼层
yhfyhf 发表于 2015-6-14 20:33
用这个:List result = new ArrayList();   

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

谢谢。但依然不行
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 20:48:56 | 显示全部楼层
非常诡异。

我把中间几行放空,结果错误还是在第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. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 20:52:20 | 显示全部楼层
用了别人几个ac过的代码,发现,对于这题,但凡改成 ArrayList<ArrayList<List>>现在全过不了??
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-14 20:54:29 | 显示全部楼层
love1point 发表于 2015-6-14 20:48
非常诡异。

我把中间几行放空,结果错误还是在第15行,关键是第15行就没代码

“第15行”并非你自己代码的15行。系统在你的代码之前加了一些初始化语句。15行是这两者合起来的第15行。所以我才说让你确定出错的是哪一行。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 21:00:52 | 显示全部楼层
stellari 发表于 2015-6-14 20:54
“第15行”并非你自己代码的15行。系统在你的代码之前加了一些初始化语句。15行是这两者合起来的第15行。 ...

“系统在你的代码之前加了一些初始化语句。15行是这两者合起来的第15行”

没看懂? 求解?
回复 支持 反对

使用道具 举报

yhfyhf 发表于 2015-6-14 21:14:11 | 显示全部楼层
本帖最后由 yhfyhf 于 2015-6-14 21:15 编辑
love1point 发表于 2015-6-14 20:43
谢谢。但依然不行

怎么不行,我说了那一处你就只改了那一处吗?其他地方都要改呀。

  1. public class Solution {
  2.     public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> result = new ArrayList<>();
  4.         List<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, List<Integer> curr, List<List<Integer>> result)
  15.     {
  16.         List<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. }
复制代码
还是帮你一次性改完吧,现在可以AC了。
建议好好看一下Oracle的文档,Interface, Class, Implement.
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2015-6-14 21:17:12 | 显示全部楼层
把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);
        }
    }
}
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 21:20:20 | 显示全部楼层
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. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 21:24:17 | 显示全部楼层
yhfyhf 发表于 2015-6-14 21:14
怎么不行,我说了那一处你就只改了那一处吗?其他地方都要改呀。还是帮你一次性改完吧,现在可以AC了。
...

这行不太理解:List<List<Integer>> result = new ArrayList<>();
这个ArrayList<>() 咋可以这样写啊
回复 支持 反对

使用道具 举报

yhfyhf 发表于 2015-6-14 21:32:25 | 显示全部楼层
love1point 发表于 2015-6-14 21:24
这行不太理解:List result = new ArrayList();
这个ArrayList() 咋可以这样写啊

对,为了简便可以这么写。这是Java8才有的貌似。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-14 21:37:56 | 显示全部楼层
yhfyhf 发表于 2015-6-14 21:32
对,为了简便可以这么写。这是Java8才有的貌似。

不懂为啥非得这样List result = new ArrayList();
这样List result = new ArrayList<ArrayList<Integer>>() 就错

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 22:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表