代码随想录算法训练营第二十三天 | leetcode：复原IP地址 ,子集,子集II

_zzh 的个人博客 / 60 / 4 / 创建于 2个月前 / 更新于 2个月前

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);
        }
    }
}