LeetCode DayBackTracking 第 4 部分-java教程-PHP中文网

LeetCode DayBackTracking 第 4 部分

PHPz

发布： 2024-07-09 18:30:02

转载

724人浏览过

leetcode daybacktracking 第 4 部分

491. 非减子数列

给定一个整数数组 nums，返回给定数组中至少有两个元素的所有不同的可能非递减子序列。您可以按任何顺序返回答案。

示例1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6, 7,7],[7,7]]
示例2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

限制：

1 -100 原始页面

 public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> seq = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        backTracking(列表, seq, nums, 0, 设置);

        返回列表；

    }
    public void backTracking(List<List<Integer>>list, List<Integer> seq, int[] nums, int start, Set<Integer> set){
        if(start == nums.length){
            返回;
        }

        for(int i=start; i<nums.length; i++){
            // 修剪相同的元素
            if(i!=start && set.contains(nums[i])){
                继续;
            }

            if(seq.size() >= 1 && (nums[i] < seq.get(seq.size()-1))){
                继续;
            }
            // 第一个元素
            set.add(nums[i]);

            seq.add(nums[i]);

            // 评估非递减
            if(seq.size() > 1 && nums[i]>= seq.get(seq.size()-2)){
                list.add(new ArrayList<>(seq));  
            }

            if(seq.size() == 1 || nums[i]>= seq.get(seq.size()-1)){
                backTracking(list,seq, nums, i+1, new HashSet<>());
            }
                // 回溯
            seq.remove(seq.size()-1);
        }
    }

登录后复制

46. 排列

给定一个由不同整数组成的数组 nums，返回所有可能的排列。您可以按任何顺序返回答案。

示例1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] 】
示例2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例3：

输入：nums = [1]
输出：[[1]]

限制：

1 -10 nums 的所有整数都是唯一的。

 public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();

        List<Integer> 排列 = new LinkedList<>();

        Integer[] numsI = Arrays.stream(nums).boxed().toArray(Integer[]::new);

        List<Integer> numList = new ArrayList(Arrays.asList(numsI));

        backTracking(列表、排列、numList);
        返回列表；

    }

    public void backTracking(List<List<Integer>> list, List<Integer> 排列, List<Integer> nums){
        if(nums.size()==0){
            list.add(new ArrayList<>(排列));
            返回;
        }

        for(int i=0; i<nums.size(); i++){
            permutation.add(nums.get(i));

            List<Integer> workNums = new ArrayList<>(nums);
            workNums.remove(Integer.valueOf(nums.get(i)));
            backTracking(列表、排列、workNums);

            排列.删除(排列.size()-1);

        }
    }

登录后复制

47. 排列 II

给定可能包含重复项的数字 nums 集合，以任何顺序返回所有可能的唯一排列。

示例1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] 】

限制：

1 -10 原始页面

 List<List<Integer>> list = new ArrayList<>();
    公共列表<列表<整数>> permuteUnique(int[] nums) {
        List<Integer> 排列 = new LinkedList<>();
        int[] flags = new int[nums.length];

        backTracking（排列、数字、标志）；

        返回列表；        
    }

    public void backTracking(List<Integer> permutation, int[] nums, int[] flags){
        if(permutation.size() == nums.length){
            list.add(new ArrayList<>(排列));
            返回;
        }

        Set<Integer> set = new HashSet<>();
        for(int i=0; i<nums.length; i++){
            // 标记work为递归，设置work为循环 
            if(flags[i] != 0 || set.contains(nums[i])){
                继续;
            }

            int num = nums[i];
            排列.add(num);
            设置.add(num);
            标志[i] = 1；
            backTracking（排列、数字、标志）；
            //恢复到标志；
            标志[i] = 0;
            排列.删除(排列.size()-1);

        }

    }

登录后复制

以上就是LeetCode DayBackTracking 第 4 部分的详细内容，更多请关注php中文网其它相关文章！