代码随想录算法训练营第二十四天 | leetcode：递增子序列 ,全排列,全排列II
0 / 0 / 创建于 11个月前
_zzh 的个人博客
491. 非递减子序列
注意的地方
- 递增子序列中 至少有两个元素。
- 数组中可能含有重复元素。
- 如出现两个整数相等，可以视作递增序列的一种特殊情况。
- 不能有相同的递增子序列。
解题方法
- 求非递减子序列，实质上就是一种长度大于二，顺序为递增的特殊子集。
- 需要在求子集是排除非递增子集，在path子集收集元素时，判断当前nums[i]是否小于path中的最后一个元素，如果小于则这个子集不是递增子集，需要跳过。
- 在处理完res目标数组时，需要注意path数组要处理回溯，否则会导致res中的path元素个数不对。
- 根据树形结构图，得出去重逻辑是：同一父节点下的同层上使用过的元素就不能再使用了。即与之前题目不同，每一层都需要重置used数组。used数组只对本层负责。
复杂度
时间复杂度
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. 全排列
注意的地方
- nums中包含重复元素。
- 需要返回所有不重复的全排列。
- 本题因为排列时有顺序的每次循环都需要0位置开始遍历，所以不需要使用startIndex控制。
解题方法
给定数组包含重复元素，需要返回不重复的排列。并且返回结果没有递增或者递减要求。（有的话就不能再递归前排序，与上面非递减序列一样，上面的去重方式就与这里不一样）那么就与《40.组合总和II》《90.子集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
注意的地方
- 给定的数组存在重复数字。
- 解集不能包含重复子集。
- 需要先排序。
解题方法
与组合总和II的题目相似，都是给定数组存在相同元素，并且不能有重复的组合。所以本题也会用到“树层去重”和“树枝去重”求解。传送门：组合总和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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号