【算法训练 day30 复原IP地址、子集、子集Ⅱ】

一、复原IP地址-LeetCode 93

Leecode链接: leetcode 93
文章链接: 代码随想录
视频链接: B站

有效 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"]

思路

这道题是一个分割问题，可以用回溯穷举出所有结果。主要分为三个部分：切割ip段、验证ip段是否合法、插入结果到res中。ip切割这里不是使用substr函数，只需要使用insert成员函数即可，因为结果只需要一个完整的ip段，而不是一段一段。验证ip写一个自定义函数即可，插入结果到res这一步使用index来判断已经不适用了，因为ip有四个段，所以判断依据只需要改为是否使用了三个点即可。

实现代码

//cpp
class Solution {
public:
    vector<string>res;
    
    bool isvalid(const string& s,int begin,int end){
        if(begin > end) return false;

        if(s[begin] == '0' && begin != end) return false;

        int num = 0;
        for(int i = begin;i<=end;i++){
            if(s[i]<'0' || s[i]>'9') return false;

            num = num*10+(s[i]-'0');
            if(num>255) return false;
        }
        return true;
    }

    void restor(int pointnum,string&s,int index){
        if(pointnum==3){
            if(isvalid(s,index,s.size()-1)){
                res.push_back(s);
            }
            return;
        }

        for(int i = index;i<s.size();i++){
            if(isvalid(s,index,i)){
                pointnum++;
                s.insert(s.begin()+i+1,'.');
                restor(pointnum,s,i+2);
                pointnum--;
                s.erase(s.begin()+i+1);
            }
            else{
                break;
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        res.clear();
        restor(0,s,0);
        return res;
    }
};

个人问题

没有想到怎么在字符串中插入字符’.'，对insert用的比较少。

总结

难度中等，与分割回文串那题类似，需要注意的点有：插入结果的条件不再依靠index，而是依据段数；递归时不能传入i+1，因为插入字符后，前面的字符都往后移动一位；插入结果时需要对最后一段进行额外的一次判断，因为会有这种情况：192.168.1.399，这显然是不对的。

二、子集-LeetCode 78

Leecode链接: LeetCode 78
文章链接: 代码随想录
视频链接: B站

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的
子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例：

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

思路

题目与求组和类似，但有一个地方不同，在插入数据到res中时，组合需要进行一个判定，而子集不需要进行判断，每次进入一层递归就将结果插入到res中。至于为什么不需要判断，因为题目要求所有子集，任意一个数或者他们的组合都是子集，也就不要条件判断。

实现代码

//cpp
class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;

    void sub(vector<int>& nums,int index){
        res.push_back(path);

        for(int i = index;i<nums.size();i++){
            path.push_back(nums[i]);
            sub(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        res.clear();
        path.clear();
        sub(nums,0);
        return res;
    }
};

个人问题

无。

三.子集Ⅱ-LeeCode 90

Leecode链接: LeetCode 90
文章链接: 代码随想录
视频链接: B站

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的
子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

示例：

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

思路

题目有重复元素，需要去重，不能包含重复的子集。解题思路与与组合总和Ⅱ类似。个人没有使用数组来判断是否使用相同的元素，感觉这样比较方便。

实现代码

//cpp
class Solution {
public:
    vector<int>path;
    vector<vector<int>>res;

    void sub(int index,vector<int>& nums){
        res.push_back(path);
        
        for(int i = index;i<nums.size();i++){
            if(i>index && nums[i] == nums[i - 1]){
                continue;
            }
            path.push_back(nums[i]);
            sub(i+1,nums);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        res.clear();
        path.clear();
        sort(nums.begin(),nums.end());
        sub(0,nums);
        return res;
    }
};