leetcode

发布时间:2024年01月17日

代码随想录计划

Day 25–回溯算法

非递减子序列

非递减子序列

这题个人理解为有两个点需要实现:

1.深度递归时需要做非递减的判断。这个好像到就使用 !path.isEmpty() && nums[i] < path.get(path.size() - 1)这句判断就行。由于path中存放的是非递减的子序列,所以新加入的元素一定要不小于最后一个值。

2.宽度for循环遍历时的去重。由于有重复元素,在宽度遍历时需要过滤掉之前重复遍历的元素。之前的做法是if(i>start && nums[i]==nums[i-1]) continue;,但是由于这次的数组并不可以进行排序所以,nums[i]==nums[i-1]这个操作也就不行了。

最终解决方法是使用一个hash表来解决。可以是map,set,也可以是数组,因为nums数组中的值是有范围的 -100 <= nums[i] <= 100

剩下还有一些小细节,比如之前有return 操作,而这次不能return

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        return res;
    }

    private void backtracking (int[] nums, int start) {
        if (path.size() > 1) {
            res.add(new ArrayList<>(path));
        }

        int[] used = new int[201];
        for (int i = start; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
                    (used[nums[i] + 100] == 1)) continue;
            used[nums[i] + 100] = 1;
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

全排列

全排列

要满足两个条件:

1.全排列,序列大小要跟数组一样

2.不能重复添加元素 --两种解决办法 除了代码中的还可以用一个数组来标记该元素是否使用过。

class Solution {
    private List<List<Integer>> result;
    private List<Integer> list;
    public List<List<Integer>> permute(int[] nums) {
        result = new LinkedList<>();
        list = new LinkedList<>();
        backtracking(nums);
        return result;
    }
    public void backtracking(int[] nums){
        if(list.size() == nums.length){
            result.add(new LinkedList<>(list));
            return;
        }
        for(int i= 0 ;i<nums.length;i++){
            if(list.contains(nums[i]) ) continue;
            list.add(nums[i]);
            backtracking(nums);
            list.remove(list.size()-1);
        }
    }
}
全排列 II

全排列 II

现在有重复的数字

在上一题中不能重复添加元素,其实就是深度递归时的去重。由于上题有没有重复元素的限制所以不用考虑宽度for循环遍历时的去重。

这题去重则需要设计两个方向

1.宽度for循环时去重,重复元素不需要再求全排列,方法还是先对数组进行排序,然后使用i>0 && nums[i]==nums[i-1] 这个条件,但是光这样写还不够,你无法区分现在判断的是在尽显深度还是宽度,所以要加上&& used[i-1] ==0,这个条件就是为了确定他是在宽度时的遍历。

2.深度去重,深度去重则和上题一样,只不过由于存在重复元素不能使用contains函数了,只能使用hash数组来进行标记。

class Solution {
    private List<List<Integer>> result;
    private List<Integer> list;
    public List<List<Integer>> permuteUnique(int[] nums) {
        result = new LinkedList<>();
        list = new LinkedList<>();
        int[] used = new int[nums.length];
        Arrays.sort(nums);
        backtraking(nums,used);
        return result;
    }
    public void backtraking(int[] nums,int[] used){
        if(list.size() == nums.length){
            result.add(new LinkedList<>(list));
            return ;
        }
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1] && used[i-1] ==0) continue;
            if(used[i] !=0) continue;
    
            list.add(nums[i]);
            used[i] = 1;
            backtraking(nums,used);
            used[i] = 0;
            list.remove(list.size()-1);
        }
    }
}
文章来源:https://blog.csdn.net/zhl129/article/details/135624022
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。