代码学习记录23--回溯算法第四天

随想录日记part23

$time：$ 2024.03.19

主要内容：回溯算法在代码学习中尤其重要，所以今天继续加深对其的理解：1：复原IP地址 ；2.子集 ；3.子集II

• 93.复原IP地址
• 78.子集
• 90.子集II

Topic1复原IP地址

题目：

有效 IP 地址正好由四个整数（每个整数位于 $0$ 到 $255$ 之间组成，且不能含有前导 $0$），整数之间用 ‘.’ 分隔。例如：$"0.1.2.201"$ 和 $"192.168.1.1"$ 是 有效 IP 地址，但是 $"0.011.255.245"、"192.168.1.312"$ 和 $"192.168@1.1"$ 是 无效 $IP$ 地址。
给定一个只包含数字的字符串 $s$ ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 $s$ 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

输入： $s="25525511135"$
输出： $["255.255.11.135","255.255.111.35"]$

思路：

切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来
按照回溯模板我们进行回溯三部曲：
递归三部曲：
1.回溯函数模板返回值以及参数
在这里要定义一个全局变量$result$用来存放符合条件结果的集合。回溯函数里需要一个参数为 $int$ 型变量 $startIndex$，来表示切割字符的起始索引，同时还需要一个$int$ 类型的变量 $numPoint$ 来记录切割点数。
所以整体代码如下：

List<String> result = new LinkedList<>();// 保存最后结果的数组
 void reback(String s, int startIndex, int numPoint)

2.回溯函数终止条件
本题明确要求只会分成 $4$ 段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。$numPoint$ 表示逗点数量，$numPoint$ 为 $3$ 说明字符串分成了 $4$ 段了。然后验证一下第四段是否合法，如果合法就加入到结果集里
代码如下：

if (numPoint == 3) {
            if (isVaid(s, startIndex, s.length() - 1))
                result.add(s);
            else
                return;
        }

3.回溯搜索的遍历过程
在$for(inti=startIndex;i<s.size();i++)$循环中 $[startIndex,i]$ 这个区间就是截取的子串，需要判断这个子串是否合法。如果合法就在字符串后面加上符号 $.$ 表示已经分割。
如果不合法就结束本层循环，如图中剪掉的分支：

然后就是递归和回溯的过程：
递归调用时下一层递归的 $startIndex$ 要从 $i+2$开始（因为需要在字符串中加入了分隔符 $.$ ），同时记录分割符的数量 $numPoint$ 要 $+1$。
回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，$numPoint$也要 $-1$。
实现代码如下：

for (int i = startIndex; i < s.length(); i++) {
            if (isVaid(s, startIndex, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                numPoint++;
                reback(s, i + 2, numPoint);
                numPoint--;// 回溯
                s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯
            } else {
                break;// 这里注意思考为啥不用return或者continue
            }

完整的代码如下：

class Solution {
    List<String> result = new LinkedList<>();// 保存最后结果的数组

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12)
            return result;
        reback(s, 0, 0);
        return result;
    }

    private void reback(String s, int startIndex, int numPoint) {
        if (numPoint == 3) {
            if (isVaid(s, startIndex, s.length() - 1))
                result.add(s);
            else
                return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isVaid(s, startIndex, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                numPoint++;
                reback(s, i + 2, numPoint);
                numPoint--;// 回溯
                s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯
            } else {
                break;// 这里注意思考为啥不用return或者continue
            }
        }
    }

    private Boolean isVaid(String s, int begin, int end) {// 判断字符是否合法
        if (end < begin)
            return false;
        if (s.charAt(begin) == '0' && begin != end)
            return false;
        int count = 0;// 计算器
        for (int i = begin; i <= end; i++) {
            if (s.charAt(i) < '0' || s.charAt(i) > '9')
                return false;
            count = count * 10 + s.charAt(i) - '0';
        }
        if (count > 255)
            return false;
        else
            return true;
    }
}

时间复杂度: $O(3^4)$，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式，则搜索树的最大深度为4，每个节点最多有3个子节点。
空间复杂度: $O(n)$

Topic2子集

题目：

给你一个整数数组 $nums$ ，数组中的元素互不相同 。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

输入： $nums=[1,2,3]$
输出： $[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]$

思路：

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！以示例中 $nums=[1,2,3]$ 为例把求子集抽象为树型结构，如下：

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。
按照回溯模板我们进行回溯三部曲：
递归三部曲：
1.回溯函数模板返回值以及参数
在这里要定义两个全局变量，$path$用来存放符合条件单一结果，$result$用来存放符合条件结果的集合。回溯函数里需要一个参数为 $int$ 型变量 $startIndex$。
所以整体代码如下：

List<List<Integer>> result=new ArrayList<>();
LinkedList<Integer> path=new LinkedList<>();
void reback(int[] nums,int startIndex)

2.回溯函数终止条件
就是 $startIndex$ 已经大于数组的长度了，就终止了，因为没有元素可取了，代码如下:
代码如下：

if(startIndex>=nums.length) {
            return; 
        }

3.回溯搜索的遍历过程
求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

实现代码如下：

 for(int i=startIndex;i<nums.length;i++){
            path.add(nums[i]);
            reback(nums,i+1);
            path.removeLast();
        }

完整的代码如下：

class Solution {
    List<List<Integer>> result=new ArrayList<>();//记录最后的结果
    List<Integer> path=new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        reback(nums,0);
        return result;
    }
    private void reback(int[] nums,int startIndex){
        result.add(new ArrayList(path));
        if(startIndex>=nums.length) {
            return; 
        }
        for(int i=startIndex;i<nums.length;i++){
            path.add(nums[i]);
            reback(nums,i+1);
            path.removeLast();
        }
    }
}

时间复杂度: $O(n\ast 2^n)$
空间复杂度: $O(n)$

Topic3子集II

题目：

给你一个整数数组 $nums$ ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

输入： $nums=[1,2,2]$
输出： $[[],[1],[1,2],[1,2,2],[2],[2,2]]$

思路：
这个就是上面的方法加上了去重操作，去重的两种方法和之前如出一辙，下面直接给出两种代码：

1.使用used数组的

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        used=new boolean[nums.length];
        reback(nums,0);
        return result;
    }
    private void reback(int[] nums,int startIndex){
        result.add(new ArrayList(path));
        if(startIndex>=nums.length) {
            return; 
        }
        for(int i=startIndex;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1] && !used[i-1]){
                continue;
            }
            path.add(nums[i]);
            used[i]=true;
            reback(nums,i+1);
            path.removeLast();
            used[i]=false;
        }
    }
}

2.不使用used数组的

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        
        reback(nums,0);
        return result;
    }
    private void reback(int[] nums,int startIndex){
        result.add(new ArrayList(path));
        if(startIndex>=nums.length) {
            return; 
        }
        for(int i=startIndex;i<nums.length;i++){
            if(i>startIndex && nums[i]==nums[i-1]){
                continue;
            }
            path.add(nums[i]);
            
            reback(nums,i+1);
            path.removeLast();
            
        }
    }
}

时间复杂度: $O(n\ast 2^n)$
空间复杂度: $O(n)$