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

93. 复原 IP 地址

注意的地方

  1. 判断IP地址合法性:是数字,小于255,首尾是0时,长度不超过1。
  2. ip地址是四段,切割三次,最后一份需要特殊处理。并且控住递归深度。
  3. 截取字符串时注意起始位置与长度表示。

解题方法

  1. 需要使用splitNum作为切割次数标志
  2. 循环递归字符串时判断切割字符是否符合IP地址属性,符合属性则放入path数组,当splitNum == 3时 代表此时已经切割三次,符合IP地址由四个整数组成原则。此时收获path结果。但是此时path只有三个元素,需要截取此时startIndex到字符串end位置的第四个ip,并且判断它是否合法,合法才能加入res目标数组。
  3. 在处理完res目标数组时,需要注意path数组要处理回溯,否则会导致res中的path元素个数不对。
  4. 切割流程图如下
    代码随想录算法训练营第二十三天 | leetcode:复原IP地址 ,子集,子集II

复杂度

时间复杂度

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. 子集

注意的地方

  1. []空数组也是子集之一。
  2. 组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点。
  3. 收集结果的时机很重要。

解题方法

  1. 子集问题是收集所有节点的情况,所以res收集path数组没有条件限制,进入递归就进行收集,并且收集后不能return,否则节点收集不全。
  2. 收集的时机:必须在return之前收集结果,否则容易当前return时的path节点值。
  3. 遍历参考图。
    代码随想录算法训练营第二十三天 | leetcode:复原IP地址 ,子集,子集II

复杂度

时间复杂度

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

注意的地方

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

解题方法

与组合总和II的题目相似,都是给定数组存在相同元素,并且不能有重复的组合。所以本题也会用到“树层去重”和“树枝去重”求解。传送门:组合总和II
代码随想录算法训练营第二十三天 | leetcode:复原IP地址 ,子集,子集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 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 4
南城以南

兄弟 刷完了 还继续做PHP吗? 目前没有几个公司(除了大厂)面试会问算法

2个月前 评论
_zzh (楼主) 2个月前
南城以南 (作者) 2个月前
_zzh (楼主) 2个月前

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