寒光博客

[CC150]904集合的子集 所有的组合
题目大意 请编写一个方法,返回某集合的所有非空子集。 给定一个int数组A和数组的大小int n,请返回A的所有非...
扫描右侧二维码阅读全文
01
2019/08

[CC150]904集合的子集 所有的组合

题目大意

请编写一个方法,返回某集合的所有非空子集。
给定一个int数组A和数组的大小int n,请返回A的所有非空子集。
保证A的元素个数小于等于20,且元素互异。

代码

递归增量构造法

    private static Set<Set<Integer>> getSubsets3(int[] A, int n) {
        return getSubsets3Core(A, n, n - 1);
    }

    private static Set<Set<Integer>> getSubsets3Core(int[] A, int n, int cur) {
        Set<Set<Integer>> newSet = new HashSet<>();
        if (cur == 0) {//处理第一个元素
            Set<Integer> nil = new HashSet<>();//空集
            Set<Integer> first = new HashSet<>();//包括一个元素的集合
            first.add(A[0]);
            newSet.add(nil);
            newSet.add(first);
            return newSet;
        }
        Set<Set<Integer>> oldSet = getSubsets3Core(A, n, cur - 1);
        for (Set<Integer> set : oldSet) {
            //对于每个子集,cur这个元素可以加进去,也可以不加进去
            newSet.add(set);//保留原样 就是不加进去
            //克隆旧的 再旧的里面加上新的
            Set<Integer> clone = (Set<Integer>) ((HashSet) set).clone();
            clone.add(A[cur]);

            newSet.add(clone);
        }
        return newSet;
    }

逐步生成迭代大法

    public static Set<Set<Integer>> getSubsets2(int[] A, int n) {
        Set<Set<Integer>> res = new HashSet<>();
        res.add(new HashSet<>());//空集
        //从第一个元素开始
        for (int i = 0; i < n; i++) {
            Set<Set<Integer>> res_new =new HashSet<>();//新建一个大集合
            res_new.addAll(res);//把原来集合中的每个子集都加入到新集合中
            for (Set e:res) {//遍历之前的集合 并克隆加入新的
                Set clone=(Set)((HashSet)e).clone();
                clone.add(A[i]);
                res_new.add(clone);
            }
            res=res_new;
        }
        return res;
    }

二进制法

巧用二进制 例如三个集合 就有2^3 -1 个非空子集
000~111 除去000的空集
下列算法 巧用二进制 并得到按字典序排序的逆序结果
改算法课用做模板

public static ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        Arrays.sort(A);//正序排序
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();//大集合
        for (int i = (int) Math.pow(2, n) - 1; i > 0; i--) {//大数字减1
            ArrayList<Integer> s = new ArrayList<>();//对每个i建立集合
            for (int j = n - 1; j >= 0; j--) {
                //检查哪个位上的二进制为1,从高位开始检查,高位对应这素组靠后的元素
                if (((i >> j) & 1) == 1) {
                    System.out.println(Integer.toBinaryString(i)+":"+Integer.toBinaryString(j));
                    s.add(A[j]);
                    System.out.println(A[j]);
                }
            }
            res.add(s);
        }
        return res;
    }

Github

本文作者:Author:     文章标题:[CC150]904集合的子集 所有的组合
本文地址:https://dxoca.cn/Algorithm/209.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 3rd, 2019 at 02:17 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment