java求解集合的子集的实例

 java求解集合的子集的实例

方式1:我们知道子集个数 2的n次方

比如a,b,c的子集

* 000  0  {}
     *001  1   a
     *010  2   b
     *011  3   a,b (b,a)
     *100  4   c
     * 101  5   a,c (c,a)
     * 110  6   b,c (c,b)
     * 111  7   a,b,c

利用二进制的对应关系

@Test
public void test1() throws Exception { 

  Set<ArrayList<Integer>> subsets = getSubsets( Arrays.asList(1,2,6));
  Set<ArrayList<String>> subsets2 = getSubsets( Arrays.asList("a","b","c"));
  Set<ArrayList<Character>> subsets3 = getSubsets( Arrays.asList('b','c','d'));
  System.out.println(subsets);
  System.out.println(subsets2);
  System.out.println(subsets3);
} 

//集合接受各种类型数据
public <T> Set<ArrayList<T>> getSubsets(List<T> subList) {
  //考虑去重
  Set<ArrayList<T>> allsubsets = new LinkedHashSet<>();
  int max = 1 << subList.size();
  for (int loop = 0; loop < max; loop++) {
    int index = 0;
    int temp = loop;
    ArrayList <T> currentCharList = new ArrayList<T>();
    //控制索引
    while (temp > 0) {
      if ((temp & 1) > 0) {
        currentCharList.add(subList.get(index));
      }
      temp >>= 1;
      index++;
    }
    allsubsets.add(currentCharList);
  }
  return allsubsets;
}

方式2:归纳法

   @Test
public void testName() throws Exception {
  Set<List<Integer>> subsets2 = getSubsets2(Arrays.asList(1,2,3));
  System.out.println(subsets2);
} 

//方式2 归纳法
//从{}和最后一个元素开始,每次迭代加一个元素组成一个新的集合
public  Set<List<Integer>> getSubsets2(List<Integer> list) {
   if (list.isEmpty()) {
     Set<List<Integer>> ans=new LinkedHashSet<>();
     ans.add(Collections.emptyList());
     return ans;
   } 

   Integer first=list.get(0);
   List<Integer> rest=list.subList(1, list.size());
   Set<List<Integer>> list1 = getSubsets2(rest);
   Set<List<Integer>> list2 = insertAll(first, list1);//
   System.out.println(list1);
   System.out.println(list2);
   System.out.println("================");
   return concat(list1, list2);
} 

   public  Set<List<Integer>> insertAll(Integer first,Set<List<Integer>> lists){
  //
  Set<List<Integer>> result=new LinkedHashSet<>();
  for (List<Integer> list : lists) {
    List<Integer> copy=new ArrayList<>();
    copy.add(first);
    copy.addAll(list);
    result.add(copy);
  }
  return result;
} 

  //这样写可以不影响lists1,lists2的值
  private Set<List<Integer>> concat(Set<List<Integer>> lists1,Set<List<Integer>> lists2) {
  Set<List<Integer>> temp=new LinkedHashSet<>(lists1);
  temp.addAll(lists2);
  return temp;
}

如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • Java 得到集合中所有子集

    面试中有一道笔试题,大概意思如下: 输入一个集合,输出这个集合的所有子集.例如输入:1,2,4 输出结果如下所示: [1] [2] [4] [1, 2] [1, 4] [2, 4] [1, 2, 4] 需要认识的:空集是任何集合的子集:真子集为不包含子集的集合:非空真子集即不包含子集与空集合 解题思路: 这道题可以使用"按位对应法"进行计算 如集合A={a,b,c},对于任意一个元素,在每个子集中,要么存在,要么不存在. 映射为子集: (a,b,c) (1,1,1)->(a,b,

  • Java 通过位运算求一个集合的所有子集方法

    Java没有自带的求一个集合的所有子集的方法,我们可以通过集合的子集规律来求. 一个集合的所有子集等于2^该集合的长度.比如{c,b,a}的长度为3,这个集合的子集就有8个. 这句话看起来很简单,但同时也隐含着高深的哲理.其实一个集合的所有集合,和2^该集合的长度这个数字有关.比如上面的例子,{c,b,a}的长度为3,则可以用0-7表示其所有子集.如下所示,改数字所对应的位置为1,则说明我需要这个数字形成子集.从0-7的二进制表示,刚好代表完,一个长度为3,子集个数为8的所有子集. 0(000)

  • java求解集合的子集的实例

     java求解集合的子集的实例 方式1:我们知道子集个数 2的n次方 比如a,b,c的子集 * 000  0  {}      *001  1   a      *010  2   b      *011  3   a,b (b,a)      *100  4   c      * 101  5   a,c (c,a)      * 110  6   b,c (c,b)      * 111  7   a,b,c 利用二进制的对应关系 @Test public void test1() thro

  • JAVA collection集合之扑克牌游戏实例

    Collection 层次结构中的根接口.Collection表示一组对象,这些对象也称为collection的元素.一些 collection 允许有重复的元素,而另一些则不允许.一些 collection 是有序的,而另一些则是无序的.JDK 不提供此接口的任何直接 实现:它提供更具体的子接口(如 Set 和 List)实现.此接口通常用来传递 collection,并在需要最大普遍性的地方操作这些 collection. 主要内容:这里使用collection集合,模拟香港电影中大佬们玩的

  • Java Collection集合遍历运行代码实例

    Iterator : 迭代器,集合的专用遍历方式 Iterator <E> iterator() : 返回此集合中元素的迭代器,通过集合的iterator()方法得到 迭代器是通过集合的iterator()方法得到的,所以我们说它是依赖于集合而存在的 Iterator中的常用方法 E next() : 返回迭代中的下一个元素 boolean hasNext() : 如果迭代具有更多元素,则返回true 代码如下 public class CollectionDemo_01 { public s

  • Java集合删除元素ArrayList实例详解

    Java集合删除元素ArrayList实例详解 AbstractCollection集合类中有一个remove方法,该方法为了适配多种不同的集合,允许删除空的元素,看这部分代码的时候产生了疑问,为什么这里直接用it.remove()就直接删除了? public boolean remove(Object o) { Iterator<E> it = iterator(); if (o==null) { while (it.hasNext()) { if (it.next()==null) { i

  • Java数组集合的深度复制代码实例

    这篇文章主要介绍了Java数组集合的深度复制代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java当我们想要对一个数组进行一些操作,同时又不希望对原来的数组数据有影响的时候,使用引用是不能满足我们的需求的, 这时候我们可以使用System.arraycopy()方法实现,对用这两种复制方式,我们习惯称前者为浅复制,后者为深复制.深复制的 实现方法如下: public static void arraycopyTest() { int[

  • Java LinkedList集合功能实例解析

    由于LinkedList底层数据结构是链表,因此有一些特有的功能从链表对应到集合中. 框架代码: public class LinkedListDemo { public static void main(String[] args) { //创建集合对象 LinkedList<String> linkedList = new LinkedList<String>(); //添加元素 linkedList.add("hello"); linkedList.add

  • Java求解二叉树的最近公共祖先实例代码

    一.题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先. 百度百科中最近公共祖先的定义为:"对于有根树 T 的两个结点 p.q,最近公共祖先表示为一个结点 x,满足 x 是 p.q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)." 例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] 二.分析 本题需要找公共祖先,如果可以从下往上查找,就可以很方便的找到公共祖先 所以需要先访问叶子节点,然后在往上访问,对应着二叉树的

  • java与JSON数据的转换实例详解

    java与JSON数据的转换实例详解 JSON与JAVA数据的转换(JSON 即 JavaScript Object Natation,它是一种轻量级的数据交换格式,非常适合于服务器与 JavaScript 的交互.) 代码中有这么一句,是后台的封装数据. JSONObject jo = JSONObject.fromObject(map); 常见的java代码转换成json --请注意,这个方法曾经给我造成过困惑.因为,它在对Object转换的时候是按照domain类中的所有getXXX()方

  • 详解java各种集合的线程安全

    线程安全 首先要明白线程的工作原理,jvm有一个main memory,而每个线程有自己的working memory,一个线程对一个variable进行操作时,都要在自己的working memory里面建立一个copy,操作完之后再写入main memory.多个线程同时操作同一个variable,就可能会出现不可预知的结果.根据上面的解释,很容易想出相应的scenario. 而用synchronized的关键是建立一个monitor,这个monitor可以是要修改的variable也可以其

随机推荐