算法笔记|Day22回溯算法IV

算法笔记|Day22回溯算法IV

• ☆☆☆☆☆leetcode 491.递增子序列
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 46.全排列
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 47.全排列II
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 332.重新安排行程（待补充）
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 51. N皇后（待补充）
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 37. 解数独（待补充）
• • 题目分析
  • 代码

☆☆☆☆☆leetcode 491.递增子序列

题目链接：leetcode 491.递增子序列

题目分析

本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了，可以用数组来做哈希。注意used数组是记录本层元素是否重复使用，新的一层used都会重新定义（清空），所以要知道used只负责本层，回溯并不需要赋值恢复。

代码

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

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

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

☆☆☆☆☆leetcode 46.全排列

题目链接：leetcode 46.全排列

题目分析

排列问题仍然可以使用回溯，同样使用used数组，记录此时path里都有哪些元素使用，一个排列里一个元素只能使用一次。

代码

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

    public List<List<Integer>> permute(int[] nums) {
        int used[]=new int[nums.length];
        backtracking(nums,used);
        return res;
    }

    public void backtracking(int nums[],int used[]){
        if(path.size()==nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]==1)
                continue;
            path.add(nums[i]);
            used[i]=1;
            backtracking(nums,used);
            path.remove(path.size()-1);
            used[i]=0;
        }
    }
}

☆☆☆☆☆leetcode 47.全排列II

题目链接：leetcode 47.全排列II

题目分析

所求排列不能重复，需要去重的逻辑，对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用。另外，注意到对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

代码

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

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int used[]=new int[nums.length];
        backtracking(nums,used);
        return res;
    }

    public void backtracking(int nums[],int used[]){
        if(path.size()==nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]==1)
                continue;
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0)
                continue;
            path.add(nums[i]);
            used[i]=1;
            backtracking(nums,used);
            path.remove(path.size()-1);
            used[i]=0;
        }
    }
}

提示：
去重逻辑中：
if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0)//树层去重
continue;
改为
if(i>0&&nums[i]==nums[i-1]&&used[i-1]==1)//树枝去重
continue;
效果相同。

☆☆☆☆☆leetcode 332.重新安排行程（待补充）

题目链接：leetcode 332.重新安排行程

题目分析

代码

☆☆☆☆☆leetcode 51. N皇后（待补充）

题目链接：leetcode 51. N皇后

题目分析

代码

☆☆☆☆☆leetcode 37. 解数独（待补充）

题目链接：leetcode 37. 解数独

题目分析

代码