1. 首页
  2. Leetcode经典148题

leetCode-78-Subsets

题目描述(中等难度)

leetCode-78-Subsets

给一个数组,输出这个数组的所有子数组。

解法一 迭代一

leetCode-78-Subsets

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    ans.add(new ArrayList<Integer>());
    res.add(new ArrayList<Integer>());
    int n = nums.length;
    // 第一层循环,子数组长度从 1 到 n
    for (int i = 1; i <= n; i++) {
        // 第二层循环,遍历上次的所有结果
        List<List<Integer>> tmp = new ArrayList<List<Integer>>();
        for (List<Integer> list : res) {
            // 第三次循环,对每个结果进行扩展
            for (int m = 0; m < n; m++) {
                //只添加比末尾数字大的数字,防止重复
                if (list.size() > 0 && list.get(list.size() - 1) >= nums[m])
                    continue;
                List<Integer> newList = new ArrayList<Integer>(list);
                newList.add(nums[m]);
                tmp.add(newList);
                ans.add(newList);
            }
        }
        res = tmp;
    }
    return ans;
}

解法二 迭代法2

参照leetCode-78-Subsets

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    ans.add(new ArrayList<>());//初始化空数组
    for(int i = 0;i<nums.length;i++){
        List<List<Integer>> ans_tmp = new ArrayList<>();
        //遍历之前的所有结果
        for(List<Integer> list : ans){
            List<Integer> tmp = new ArrayList<>(list);
            tmp.add(nums[i]); //加入新增数字
            ans_tmp.add(tmp);
        }
        ans.addAll(ans_tmp);
    }
    return ans;
}

解法三 回溯法

参考public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); getAns(nums, 0, new ArrayList<>(), ans); return ans; } private void getAns(int[] nums, int start, ArrayList<Integer> temp, List<List<Integer>> ans) { ans.add(new ArrayList<>(temp)); for (int i = start; i < nums.length; i++) { temp.add(nums[i]); getAns(nums, i + 1, temp, ans); temp.remove(temp.size() - 1); } }

解法四 位操作

前方高能!!!!这个方法真的是太太太牛了。参考1 2 3 0 0 0 -> [ ] 0 0 1 -> [ 3] 0 1 0 -> [ 2 ] 0 1 1 -> [ 2 3] 1 0 0 -> [1 ] 1 0 1 -> [1 3] 1 1 0 -> [1 2 ] 1 1 1 -> [1 2 3]

所以我们只需要遍历 0 0 0 到 1 1 1,也就是 0 到 7,然后判断每个比特位是否是 1,是 1 的话将对应数字加入即可。如果数组长度是 n,那么每个比特位是 2 个状态,所有总共就是 2 的 n 次方个子数组。遍历 00 … 0 到 11 … 1 即可。

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    int bit_nums = nums.length;
    int ans_nums = 1 << bit_nums; //执行 2 的 n 次方
    for (int i = 0; i < ans_nums; i++) {
        List<Integer> tmp = new ArrayList<>();
        int count = 0; //记录当前对应数组的哪一位
        int i_copy = i; //用来移位
        while (i_copy != 0) { 
            if ((i_copy & 1) == 1) { //判断当前位是否是 1
                tmp.add(nums[count]);
            }
            count++;
            i_copy = i_copy >> 1;//右移一位
        }
        ans.add(tmp);

    }
    return ans;
}

同样是很经典的一道题,回溯,迭代,最后的位操作真的是太强了,每次遇到关于位操作的解法就很惊叹。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-78-Subsets

链接:https://www.javajike.com/article/3214.html

« leetCode-77-Combinations
leetCode-79-Word-Search»

相关推荐

QR code