首页 > 其他分享 >day28

day28

时间:2023-03-07 21:13:11浏览次数:38  
标签:used day28 nums int List new path

1、leetcode491 递增子序列

  1. 回溯三部曲

    1. 递归参数

      • 本题求子序列,很明显一个元素不能重复使用,所以需要startIndex,调整下一层递归的起始位置。

      •     List<Integer> path = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            public void backTracking(int[] nums, int startIndex) {
        
            }
        
    2. 递归终止条件

      • 题目要求递增子序列大小至少为2 且 startIndex每次都会加1,并不会无限递归。

        if(path.size() > 1) {
            res.add(new ArrayList<>(path));
            // 注意这里不要加return,因为要取树上的所有节点
        } 
        
    3. 单层搜索逻辑

      1. 同一父节点下的同层上使用过的元素就不能再使用了
  2. 代码

    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));
                // 注意这里不要加return,要取树上的节点
            }
    
            int[] used = new int[201]; // 这里使用数组来进行去重操作,题目说数值范围[-100, 100]
            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);
            }
        }
    }
    

    注意:

    数组,set,map都可以做哈希表,而且数组干的活,map和set都能干,但如果数值范围小的话能用数组尽量用数组

2、leetcode46 全排列

  1. 回溯三部曲

    1. 递归参数

      • 首先排列是有序的

      • 可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。

      • 但排列问题需要一个used数组,标记已经选择的元素

        • used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次
      • List<Integer> path = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        public void backTracking(int[] nums, boolean[] used) {
        
            }
        
    2. 递归终止条件

      • 当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。
    3. 单层搜索逻辑

      for(int i=0; i<nums.length; i++) {
                  if(used[i] == true) { // path里已经收录的元素,直接跳过
                      continue;
                  }
                  used[i] = true; //处理
                  path.add(nums[i]); //处理
                  backTracking(nums, used); //递归
                  used[i] = false; //回溯
                  path.remove(path.size()-1); //回溯
              }
      
  2. 代码

    class Solution {
        List<Integer> path = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
    
        public List<List<Integer>> permute(int[] nums) {
            boolean[] used = new boolean[nums.length];
            backTracking(nums, used);
            return res;
        }
    
        public void backTracking(int[] nums, boolean[] used) {
            if(path.size() == nums.length) { // 此时说明找到了一组
                res.add(new ArrayList<>(path));
                return;
            }
    
            for(int i=0; i<nums.length; i++) {
                if(used[i] == true) { // path里已经收录的元素,直接跳过
                    continue;
                }
                used[i] = true; //处理
                path.add(nums[i]); //处理
                backTracking(nums, used); //递归
                used[i] = false; //回溯
                path.remove(path.size()-1); //回溯
            }
    
        }
    }
    

3、leetcode47 全排列Ⅱ

  1. 代码

    class Solution {
        List<Integer> path = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
    
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);// 排序
            boolean[] used = new boolean[nums.length];
            backTracking(nums, used);
            return res;
        }
    
        public void backTracking(int[] nums, boolean[] used) {
            if(path.size() == nums.length) {
                res.add(new ArrayList<>(path));
                return;
            }
    
            for(int i=0; i<nums.length; i++) {
                // used[i - 1] == true,说明同一树枝nums[i - 1]使用过
                // used[i - 1] == false,说明同一树层nums[i - 1]使用过 
                // 如果同一树层nums[i - 1]使用过则直接跳过
                if(i>=1 && nums[i] == nums[i-1] && used[i-1] == true) {
                    continue;
                }
                if(used[i] == false) {
                    used[i] = true;
                    path.add(nums[i]);
                    backTracking(nums, used);
                    used[i] = false;
                    path.remove(path.size()-1);
                }
            }
        }
    }
    
  2. 对于排列问题,树层上去重和树枝上去重,都是可以的,但是树层上去重效率更高!

标签:used,day28,nums,int,List,new,path
From: https://www.cnblogs.com/hzj-bolg/p/17189663.html

相关文章