代码随想录算法训练营第二十四天 | leetcode:递增子序列 ,全排列,全排列II

491. 非递减子序列

注意的地方

  1. 递增子序列中 至少有两个元素。
  2. 数组中可能含有重复元素。
  3. 如出现两个整数相等,可以视作递增序列的一种特殊情况。
  4. 不能有相同的递增子序列。

解题方法

  1. 求非递减子序列,实质上就是一种长度大于二,顺序为递增的特殊子集。
  2. 需要在求子集是排除非递增子集,在path子集收集元素时,判断当前nums[i]是否小于path中的最后一个元素,如果小于则这个子集不是递增子集,需要跳过。
  3. 在处理完res目标数组时,需要注意path数组要处理回溯,否则会导致res中的path元素个数不对。
  4. 根据树形结构图,得出去重逻辑是:同一父节点下的同层上使用过的元素就不能再使用了。即与之前题目不同,每一层都需要重置used数组。used数组只对本层负责。
    代码随想录算法训练营第二十四天 | leetcode:递增子序列 ,全排列,全排列II

复杂度

时间复杂度

O(n * 2^n)

空间复杂度

O(n)

code

class Solution {
    private $res = [];
    private $path = [];
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function findSubsequences($nums) {
        $this->backtracking($nums, 0);
        return $this->res;
    }

    function backtracking($nums, $startIndex){
        if(count($this->path) >= 2){
            //此处因为需要收集符合条件的所有子集,所以不需要return
            $this->res[] = $this->path;
        }
        //此处不用写终止条件,因为for循环中已经限制了循环次数
        $used = [];
        for($i = $startIndex; $i < count($nums); $i++){
            //因为求得path要求是递增序列,遍历的nums[$i]需要大于path的最后一位,并且当前层hash是否使用过,用过则跳过。
            if((!empty($this->path) && $nums[$i] < end($this->path)) || $used[$nums[$i]]) continue;
            $this->path[] = $nums[$i];
            //构建hash
            $used[$nums[$i]] = true;
            $this->backtracking($nums, $i + 1);
            array_pop($this->path);
        }
    }
}

46. 全排列

注意的地方

  1. nums中包含重复元素。
  2. 需要返回所有不重复的全排列。
  3. 本题因为排列时有顺序的每次循环都需要0位置开始遍历,所以不需要使用startIndex控制。

解题方法

给定数组包含重复元素,需要返回不重复的排列。并且返回结果没有递增或者递减要求。(有的话就不能再递归前排序,与上面非递减序列一样,上面的去重方式就与这里不一样)那么就与《40.组合总和II》《90.子集II》的去重逻辑是一样的了。
代码随想录算法训练营第二十四天 | leetcode:递增子序列 ,全排列,全排列II

复杂度

时间复杂度

O(n! * n)

空间复杂度

O(n)

code

class Solution {
    private $res = [];
    private $path = [];
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute($nums) {
        $this->backtracking($nums);
        return $this->res;
    }
    function backtracking($nums){
        if(count($this->path) == count($nums)){
            $this->res[] = $this->path;
            return;
        }

        for($i = 0; $i < count($nums); $i++){
            //判断当前path中是否有重复元素
            if(in_array($nums[$i],$this->path)) continue;
            $this->path[] = $nums[$i];
            $this->backtracking($nums);
            array_pop($this->path);
        }
    }
}

47. 全排列 II

注意的地方

  1. 给定的数组存在重复数字。
  2. 解集不能包含重复子集。
  3. 需要先排序。

解题方法

与组合总和II的题目相似,都是给定数组存在相同元素,并且不能有重复的组合。所以本题也会用到“树层去重”和“树枝去重”求解。传送门:组合总和II
代码随想录算法训练营第二十三天 | leetcode:复原IP地址 ,子集,子集II

复杂度

时间复杂度

O(n! * n)

空间复杂度

O(n)

code

class Solution {
    private $res = [];
    private $path = [];
    private $used = [];
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permuteUnique($nums) {
        //先排序
        sort($nums);
        $this->backtracking($nums);
        return $this->res;
    }
    function backtracking($nums){
        if(count($this->path) == count($nums)){
            //收集结果
            $this->res[] = $this->path;
            return;
        }
        for($i = 0; $i < count($nums); $i++){
            // used[i - 1] == true,说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false,说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if($i > 0 && $nums[$i-1] == $nums[$i] && $this->used[$i-1] == false) continue;
            if($this->used[$i] == false){
                $this->used[$i] = true;
                $this->path[] = $nums[$i];
                $this->backtracking($nums);
                $this->used[$i] = false;
                array_pop($this->path);
            }
        }
    }
}

拓展

如果改成 used[i - 1] == true, 也是正确的!,去重代码如下:

if($i > 0 && $nums[$i-1] == $nums[$i] && $this->used[$i-1] == true) continue;

解答传送门:代码随想录-全排列II

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!