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

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