代码随想录算法训练营day29 || 491.非递减子序列,46.全排列,47. 全排列||

发布时间:2024年01月24日

视频讲解:

回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili

组合与排列的区别,回溯算法求解的时候,有何不同?| LeetCode:46.全排列_哔哩哔哩_bilibili

回溯算法求解全排列,如何去重?| LeetCode:47.全排列 II_哔哩哔哩_bilibili

491.非递减子序列

思路:组合问题,存在重复元素,强调nums内元素顺序。采用startindex以及set局部已用元素去重;

// 时间复杂度最大是O(n^k),n是生成树的最大高度,k是ans的长度
// 空间复杂度最大是O(kn)
class Solution {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        // 类似于子集题目
        if(nums.length == 0)
            return ans;
        backtracking(nums, 0, new boolean[nums.length]);
        return ans;
    }

    public void backtracking(int[] nums, int startindex, boolean[] visited){
        // 遍历到末尾,终止条件
        if(startindex == nums.length){
            return;
        }
        // 新的去重操作,ArrayList的时间效率高于HashSet
        List<Integer> set = new ArrayList<>();
        for(int i=startindex; i<nums.length; i++){
            // 节点处理,仅仅是递增的元素或者list为空时可以加入元素,其他的情况全部continue
            // 此外去重的操作是必须的,且是树层去重,重复的元素在同一个for循环中只可以被选中一次
            if(set.contains(nums[i]))
                continue;
            else if(list.size() == 0 || (list.size()>0 && nums[i] >= list.get(list.size()-1)))
                list.add(nums[i]);
            else
                continue;

            set.add(nums[i]);
            if(list.size()>=2)
                ans.add(new ArrayList<Integer>(list));
            backtracking(nums, i+1, visited);
            // 回溯
            list.remove(list.size()-1);
        }

        return;
    }
}

46.全排列

// 时间复杂度O(n*n(n-1)(n-2)……*2*1),全排列一共有n(n-1)(n-2)……*2*1)种结果,形成每种结果都需要一次nums的遍历
// 空间复杂度O(n*n(n-1)(n-2)……*2*1),每一种结果的长度都是n
class Solution {
    
    // 时间效率更快的话就是将list使用数组来代替
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        // 需要处理特殊情况,backtracking函数中没有涉及特殊情况的处理
        if(nums.length == 0)
            return ans;
        backtracking(nums, new boolean[nums.length]);
        return ans;
    }

    public void backtracking(int[] nums, boolean[] visited){
        if(list.size() == nums.length){
            ans.add(new ArrayList<Integer>(list));
            return;
        }

        // 全排列,元素遍历时可以回头,因此仅仅需要一个visited元素控制已经访问的位置即可
        for(int i=0; i<nums.length; i++){
            if(!visited[i]){
                visited[i] = true;
                list.add(nums[i]);
                backtracking(nums, visited);
                list.remove(list.size()-1);
                visited[i] = false;
            }
        }

        return;
    }
}

47. 全排列||?

思路:要求结果不重复,数组内存在重复元素,但是不强调元素顺序不可变,所以使用visited数组结合数组排序解题。

// 时间复杂度O(n^k),n是nums的长度,k是ans的长度
// 空间复杂度O(nk)
class Solution {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 出现重复元素,但是强调nums内元素的顺序性,那么是排序结合visited数组进行去重
        // 全排列不需要startindex参数控制遍历仅仅是一个方向,全排列是可以两个方向的
        if(nums.length == 0)
            return ans;
        Arrays.sort(nums);
        backtracking(nums, new boolean[nums.length]);
        return ans;
    }

    public void backtracking(int[] nums, boolean[] visited){
        if(list.size() == nums.length){
            ans.add(new ArrayList<>(list));
            return;
        }

        for(int i=0; i<nums.length; i++){
            if(!visited[i]){
                if(i-1>=0 && nums[i] == nums[i-1] && visited[i-1] == false)
                    continue;
                visited[i] = true;
                list.add(nums[i]);
                backtracking(nums, visited);
                list.remove(list.size()-1);
                visited[i] = false;
            }
            
        }

        return;
    }
}

结合非递减子序列、组合、组合II、子集、子集||,关于回溯中去重的方法我们可以做如下总结:

  • 组合类问题,仅仅强调nums的访问方向,使用startindex参数即可,也即startindex参数可以保证回溯递归过程中遍历方向始终向后;
  • 子集类问题,子集| 强调遍历方向且结果内不可以存在重复结果,使用startindex完成解题;但子集|| 中开始出现nums内存在重复元素,但仍然不强调nums数组内元素的顺序不可变动,所以使用nums排序配以startindex或者nums排序配以startindex以及visited数组即可;
  • 非递减子序列,强调遍历方向,存在重复元素,且强调nums内元素顺序不可变动,因此排序配以startindex和visited方法不可行,因此使用了startindex以及局部set查重的操作完成解题;
  • 全排列问题,不强调遍历方向,仅仅是每个元素仅仅可以使用一次,因此使用visited数组即可解题;排列|| 中,不强调遍历方向,每个元素使用一次,不可以存在重复的结果,但不强调nums内元素的顺序,所以使用visited数组配以数组排序即可解题。
  • 基于以上的内容,我们对所有采用的操作做出如下的归纳:
  • startindex,单独使用保证nums遍历方向始终向后,强调遍历顺序的题目使用;
  • visited数组,单独使用保证每个元素仅仅被使用一次;排列题目使用;
  • 数组排序,单独使用没有意义,联合visited数组和startindex 或 仅联合startindex 或 仅联合visited数组,保证重复的元素在一个for循环中仅仅可以被选中一次,属于全局去重,强调不出现重复结果但不强调nums元素顺序的题目使用;
  • set去重,保证重复的元素在一个for循环中仅仅可以被选中一次,属于局部去重,在每一个递归体内新建一个局部set用以去重;强调不出现重复结果且nums元素顺序不可以变的题目中使用;
  • 以上的方法直接可以相互配置实现回溯题解题,各个方法的使用需要依据题目的具体要求进行实际的组合或搭配。
文章来源:https://blog.csdn.net/weixin_44316285/article/details/135817199
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。