我们为什么要在某些递归算法中复制ArrayList?

光碟

http://oj.leetcode.com/problems/subsets-ii/

给定一个可能包含重复项S的整数集合,返回所有可能的子集。

笔记:

* Elements in a subset must be in non-descending order.
* The solution set must not contain duplicate subsets.

例如,如果S = [1,2,2],则解决方案是:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

答案是:

public class Solution {
   public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
       ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
       ArrayList<Integer> tmp = new ArrayList<Integer>();
       Arrays.sort(num);
       sub(num, 0, tmp, ans);
       return ans;        
   }

   public void sub(int[] num, int k, ArrayList<Integer> tmp, ArrayList<ArrayList<Integer>> ans) {
       ArrayList<Integer> arr = new ArrayList<Integer>(tmp);            
       ans.add(arr);       

       for (int i = k; i < num.length; i++) {
           if (i != k && num[i] == num[i-1]) continue;

           tmp.add(num[i]);
           sub(num, i+1, tmp, ans);
           tmp.remove(tmp.size()-1);
       }
   }
}

我不知道为什么

 ArrayList<Integer> arr = new ArrayList<Integer>(tmp);            
 ans.add(arr);

但不直接:

 ans.add(tmp);
伯恩哈德·巴克(Bernhard Barker)

如果您只想打印结果,由于您删除了在递归调用之后添加的任何元素tmp,因此在函数的开始和结束处应该看起来完全相同,因此不应有任何区别(您的方式会首选,因为它不会ArrayList在每个步骤都复制)。

但是,当您将结果添加到时,问题就来了ans

如果您使用自己的方式,那么只会有一个ArrayList浮动对象-您只需将其添加ans多次即可。

请注意,将其添加到ans不实际创建它的副本,它只是增加了一个参考ArrayListans因此,在添加原始文件后对其进行更改也会更改的元素ans

现场演示通过打印出来显示正确的结果,并在返回的数组中显示不正确的结果

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Java

为什么我们需要在Java中对ArrayList使用迭代器?

来自分类Dev

我们为什么要在pytorch中“打包”序列?

来自分类Dev

为什么我们需要在 Go 中的 Diffie Hellman 密钥交换算法中恢复公钥

来自分类Dev

为什么我们不需要在某些 Rust 迭代器中从 Result 中提取值?

来自分类Dev

为什么每次我们需要在TensorFlow中运行某些东西时都构建bazel?

来自分类Dev

为什么我们需要在并发 GC 跟踪中使用 SATB 算法?

来自分类Dev

为什么我们需要在这里复制u的值?

来自分类Dev

为什么我们需要在Linux上挂载?

来自分类Dev

为什么我们要在OnCreate中检查重叠的片段?(来自文档)

来自分类Dev

为什么我们需要在/ dev / null 2>&1中有2>&1?

来自分类Dev

为什么我们需要在React Hook中返回一个函数?

来自分类Dev

为什么我们需要在Guice模块中实现configure()?

来自分类Dev

为什么我们需要在此脚本中调用“ c.set.bind(c)”?

来自分类Dev

为什么我们需要在Android应用中存储Goefence数据?

来自分类Dev

为什么我们需要在链接列表中填充数据?

来自分类Dev

为什么我们要在 docker 中同时使用 --detach 开关与 --interactive 和 --tty ?

来自分类Linux

为什么我们需要在PyTorch中调用zero_grad()?

来自分类Dev

为什么我们需要在React Native中绑定函数?

来自分类Linux

为什么我们需要在民意调查中调用poll_wait?

来自分类Dev

我们为什么要在字体中包含ttf,eot,woff,svg,...

来自分类Dev

我们为什么需要在vaadin的绑定中设置bean ** binder.setBean(object)**

来自分类Dev

为什么我们需要在MSIL中显式调用父构造函数?

来自分类Dev

为什么我们要在dpkg中添加i386体系结构?

来自分类Dev

为什么我们不需要在React中绑定箭头功能?

来自分类Dev

为什么我们需要在ConnectionString中设置最小池大小

来自分类Dev

为什么我们要在 useIsMounted 钩子中使用回调来从钩子中返回 ref?

来自分类Dev

为什么我们需要在C#中锁定并反对?

来自分类Dev

为什么我们要在Kotlin / Android中“获得稳定的参考”?

来自分类Dev

为什么我们需要在哈希导航URL中添加标记?

Related 相关文章

  1. 1

    为什么我们需要在Java中对ArrayList使用迭代器?

  2. 2

    我们为什么要在pytorch中“打包”序列?

  3. 3

    为什么我们需要在 Go 中的 Diffie Hellman 密钥交换算法中恢复公钥

  4. 4

    为什么我们不需要在某些 Rust 迭代器中从 Result 中提取值?

  5. 5

    为什么每次我们需要在TensorFlow中运行某些东西时都构建bazel?

  6. 6

    为什么我们需要在并发 GC 跟踪中使用 SATB 算法?

  7. 7

    为什么我们需要在这里复制u的值?

  8. 8

    为什么我们需要在Linux上挂载?

  9. 9

    为什么我们要在OnCreate中检查重叠的片段?(来自文档)

  10. 10

    为什么我们需要在/ dev / null 2>&1中有2>&1?

  11. 11

    为什么我们需要在React Hook中返回一个函数?

  12. 12

    为什么我们需要在Guice模块中实现configure()?

  13. 13

    为什么我们需要在此脚本中调用“ c.set.bind(c)”?

  14. 14

    为什么我们需要在Android应用中存储Goefence数据?

  15. 15

    为什么我们需要在链接列表中填充数据?

  16. 16

    为什么我们要在 docker 中同时使用 --detach 开关与 --interactive 和 --tty ?

  17. 17

    为什么我们需要在PyTorch中调用zero_grad()?

  18. 18

    为什么我们需要在React Native中绑定函数?

  19. 19

    为什么我们需要在民意调查中调用poll_wait?

  20. 20

    我们为什么要在字体中包含ttf,eot,woff,svg,...

  21. 21

    我们为什么需要在vaadin的绑定中设置bean ** binder.setBean(object)**

  22. 22

    为什么我们需要在MSIL中显式调用父构造函数?

  23. 23

    为什么我们要在dpkg中添加i386体系结构?

  24. 24

    为什么我们不需要在React中绑定箭头功能?

  25. 25

    为什么我们需要在ConnectionString中设置最小池大小

  26. 26

    为什么我们要在 useIsMounted 钩子中使用回调来从钩子中返回 ref?

  27. 27

    为什么我们需要在C#中锁定并反对?

  28. 28

    为什么我们要在Kotlin / Android中“获得稳定的参考”?

  29. 29

    为什么我们需要在哈希导航URL中添加标记?

热门标签

归档