代码随想录算法训练营第二十三天 | leetcode：复原IP地址 ,子集,子集II
0 / 4 / 创建于 11个月前 /
_zzh 的个人博客
93. 复原 IP 地址
注意的地方
- 判断IP地址合法性：是数字，小于255，首尾是0时，长度不超过1。
- ip地址是四段，切割三次，最后一份需要特殊处理。并且控住递归深度。
- 截取字符串时注意起始位置与长度表示。
解题方法
- 需要使用splitNum作为切割次数标志
- 循环递归字符串时判断切割字符是否符合IP地址属性，符合属性则放入path数组，当splitNum == 3时 代表此时已经切割三次，符合IP地址由四个整数组成原则。此时收获path结果。但是此时path只有三个元素，需要截取此时startIndex到字符串end位置的第四个ip，并且判断它是否合法，合法才能加入res目标数组。
- 在处理完res目标数组时，需要注意path数组要处理回溯，否则会导致res中的path元素个数不对。
- 切割流程图如下
复杂度
时间复杂度
O(3^4)
IP地址最多包含4个数字，每个数字最多有3种可能的分割方式，则搜索树的最大深度为4，每个节点最多有3个子节点
空间复杂度
O(n)
code
class Solution {
class Solution {
private $res = [];
private $path = [];
/**
* @param String $s
* @return String[]
*/
function restoreIpAddresses($s) {
if(strlen($s) < 4 || strlen($s) > 12) return $this->res;
$this->backtracking($s, 0, 0);
foreach($this->res as $key => $val){
$this->res[$key] = implode(".",$val);
}
return $this->res;
}
function backtracking($s, $startIndex, $splitNum){
if($splitNum == 3){
//截取最后一段字符串
$finalStr = substr($s, $startIndex, strlen($s) - $startIndex);
//判断最后一段字符串合法性再加入res数组
if($this->isValid($finalStr)){
$this->path[] = $finalStr;
$this->res[] = $this->path;
//加入结果数组后要回溯，否则下次加入数量会错误
array_pop($this->path);
}
return;
}
for($i = $startIndex; $i < strlen($s); $i++){
$str = substr($s, $startIndex, $i - $startIndex + 1);
if($this->isValid($str)){
$this->path[] = $str;
$splitNum++;
$this->backtracking($s, $i + 1, $splitNum);
$splitNum--;
array_pop($this->path);
}else{
break;//不合法没必要继续循环
}
}
}
function isValid($str){
//当前字符串首位==0 && 字符串长度大于1
if($str[0] == 0 && strlen($str) > 1) return false;
//大于255
if($str > 255) return false;
//不是数字
if(!is_numeric($str)) return false;
return true;
}
}78. 子集
注意的地方
- []空数组也是子集之一。
- 组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。
- 收集结果的时机很重要。
解题方法
- 子集问题是收集所有节点的情况，所以res收集path数组没有条件限制，进入递归就进行收集，并且收集后不能return，否则节点收集不全。
- 收集的时机：必须在return之前收集结果，否则容易当前return时的path节点值。
- 遍历参考图。
复杂度
时间复杂度
O(n * 2^n)
空间复杂度
O(n)
code
class Solution {
private $res = [];
private $path = [];
/**
* @param Integer[] $nums
* @return Integer[][]
*/
function subsets($nums) {
$this->backtracking($nums, 0);
return $this->res;
}
function backtracking($nums, $startIndex){
//不能写在return下面，否则会丢失最后一次结果，进入循环时就要先收集path
$this->res[] = $this->path;
if($startIndex >= count($nums)) return;
for($i = $startIndex; $i < count($nums); $i++){
$this->path[] = $nums[$i];
$this->backtracking($nums, $i + 1);
array_pop($this->path);
}
}
}90. 子集 II
注意的地方
- 给定的数组存在重复数字。
- 解集不能包含重复子集。
- 需要先排序。
解题方法
与组合总和II的题目相似，都是给定数组存在相同元素，并且不能有重复的组合。所以本题也会用到“树层去重”和“树枝去重”求解。传送门：组合总和II
复杂度
时间复杂度
O(n * 2^n)
空间复杂度
O(n)
code
class Solution {
private $res = [];
private $path = [];
private $used = [];
/**
* @param Integer[] $nums
* @return Integer[][]
*/
function subsetsWithDup($nums) {
sort($nums);
$this->backtracking($nums, 0);
return $this->res;
}
function backtracking($nums, $startIndex){
//print_r($this->used);
$this->res[] = $this->path;
//used [i - 1] != empty，说明同一树枝 candidates [i - 1] 使用过
//used [i - 1] == empty，说明同一树层 candidates [i - 1] 使用过
for($i = $startIndex; $i < count($nums); $i++){
if($i > 0 && empty($this->used[$i-1]) && $nums[$i-1] == $nums[$i]) continue;
$this->path[] = $nums[$i];
$this->used[$i] = $nums[$i];
$this->backtracking($nums, $i + 1);
array_pop($this->used);
array_pop($this->path);
}
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
兄弟 刷完了 还继续做PHP吗? 目前没有几个公司(除了大厂)面试会问算法