代码随想录算法训练营第二十九天|491.递增子序列、46.全排列、47.全排列 II

491.递增子序列

491. 非递减子序列 - 力扣(LeetCode)
本题也是子集问题,问题在于不能排序,并且数组中含有重复数值,所以需要在数层去重,但是因为两个重复的元素不一定相邻,所以和组合的去重不同,需要新建一个set

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }

    public void backTracking(int[] nums, int startIndex) {
        if (path.size() >= 2) {
            result.add(new ArrayList<>(path));
        }
        Set<Integer> hs = new HashSet<>(); //存储数层遍历时使用过的值
        for (int i = startIndex; i < nums.length; i++) {
            //2种情况不符合条件,一是nums[i]小于最后值,二是树层中已经遍历过该值
            if (!path.isEmpty() && path.getLast() > nums[i] || hs.contains(nums[i])) {
                continue;
            }
            hs.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

46.全排列

46. 全排列 - 力扣(LeetCode)
全排列问题不需要startIndex参数,因为当选择了一个数后,前面的数还需要遍历,需要一个used数组存储在该树枝上遍历过的数值

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backTracking(nums);
        return result;
    }

    public void backTracking(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            backTracking(nums);
            used[i] = false;
            path.removeLast();
        }
    }
}

47.全排列 II

47. 全排列 II - 力扣(LeetCode)
本题和组合以及子集去重原理相同,都是去除数层中的重复数值,树枝中重复元素不需要去重,但是只需要遍历没有使用过的数值

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return result;
    }

    public void backTracking(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i-1] == nums[i] && !used[i-1]) {
                continue;
            }
            if (!used[i]) {
                used[i] = true;
                path.add(nums[i]);
                backTracking(nums);
                used[i] = false;
                path.removeLast();
            }
        }
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容