算法练习-day23

回溯算法

93. 复原 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 中的任何数字。你可以按 任何 顺序返回答案。

示例：

思路：本题的思路主要由两部分组成：

1. 插入和删除分隔符，即点(.)
2. 判断每段IP地址是否合法

首先是插入和删除部分，我们可以使用库函数insert和erase轻松搞定，但是在插入和删除操作前，需要判断插入是否合适，不合适直接跳过该层循环

其次是判断IP地址，这里需要满足三点：

1. 0字符不能是首字符
2. 字符串显示的数字不能大于255
3. 字符串中出现非数字字符

这三种情况全部排除，才是合法的IP字段

且在保存字段时，由于我们只判断了三个区间，因此还需要对第四个区间进行合法判断才能保存

C++代码：

    vector<string> arr;
    bool JudgIP(string s,int left,int right)//这里需要判断IP的字段是否合法
    {
        if(left>right||(s[left]=='0'&&left!=right))//当区间非法，区间首元素为0时都是非法的
        {
            return false;
        }
        int sum=0;
        for(int i=left;i<=right;i++)
        {
            if(s[i]<'0'||s[i]>'9')//当出现不为数字的字符，非法
            {
                return false;
            }
            sum=sum*10+s[i]-'0';
            if(sum>255)//当区间大小大于255时，非法
            {
                return false;
            }
        }
        return true;
    }
    void RecvIP(string s,int begin,int points)
    {
        if(points==3)//当.为三个，说明前三个IP区间正确，在判断第四个正确即可保存
        {
            if(JudgIP(s,begin,s.size()-1))
            {
                arr.push_back(s);
            }
            return;
        }
        for(int i=begin;i<s.size();i++)
        {
            if(JudgIP(s,begin,i))//这里只能判断三个IP字段是否合法，合法将。加入其中，i向后移动两格开始
            {
                s.insert(s.begin()+i+1,'.');
                points++;
                RecvIP(s,i+2,points);
                points--;
                s.erase(s.begin()+i+1);
            }
            else//不对，直接跳出整层回溯
            {
                break;
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        RecvIP(s,0,0);
        return arr;
    }

78. 子集

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

示例：

思路：本题我们的思想很简单，就是在每次遍历时都存储组合，且遍历必须不重复，代码也比较简单，如下所示

C++代码：

    vector<vector<int>> arr;
    vector<int> tmp;
    void ComSubset(vector<int>& nums,int begin)
    {
        arr.push_back(tmp);//这里解决了两个问题：1.保存空数组 2.将每次遍历到的组合都保存到且不重复
        if(begin>=nums.size())
        {
            return;
        }
        for(int i=begin;i<nums.size();i++)//这样遍历就不会遍历到重复的组合
        {
            tmp.push_back(nums[i]);
            ComSubset(nums,i+1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        ComSubset(nums,0);
        return arr;
    }

90. 子集 II

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

示例：

思路：本题思路和40. 组合总和 II的思路一模一样，这里就不细说了。我们再插入时只需要主要，本题是没有明确的递归结束条件的，我们只需要for循环完毕，递归结束，而存储数组需要在每次循环时都进行操作

C++代码：

    vector<vector<int>> arr;
    vector<int> tmp;
    void ComSubset(vector<int>& nums,int begin,vector<bool> block)
    {
        arr.push_back(tmp);
        for(int i=begin;i<nums.size();i++)
        {
            if(i>0&&block[i-1]==false&&nums[i-1]==nums[i])
            {
                continue;
            }
            tmp.push_back(nums[i]);
            block[i]=true;
            ComSubset(nums,i+1,block);
            block[i]=false;
            tmp.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<bool> block(nums.size(),false);
        sort(nums.begin(),nums.end());
        ComSubset(nums,0,block);
        return arr;
    }