代码随想录算法训练营Day24 | Leetcode 93 复原IP地址 Leetcode 78 子集 Leetcode 90 子集Ⅱ

前言

今天对回溯算法的理解更上一层楼，子集问题也是有自己的思路并且能独立完成，复原IP地址还需要思考一下。

Leetcode 93 复原IP地址

题目链接：93. 复原 IP 地址 - 力扣（LeetCode）

代码随想录题解：代码随想录 (programmercarl.com)

思路：还是按照回溯问题的模板来分析，这个题目的终止条件比较特殊，是通过判断分割点的个数来终止的，而且在for循环树形结构里也要对字符串做一个处理，还需要判断IP地址是否合法，比较复杂。

代码：

class Solution {
public:
    vector<string>res;
    bool isvaild(const string&s,int start,int end)//判断IP地址是否合法
    {
        if(start>end)
        {
            return false;
        }
        if(s[start]=='0'&&start!=end)
        {
            return false;
        }
        int num=0;
        for(int i=start;i<=end;i++)
        {
 
        if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
            return false;
        }
        num = num * 10 + (s[i] - '0');
        if (num > 255) { // 如果大于255了不合法
            return false;
        }
    }
    return true;
    }
    void backtracking(string s,int index,int pointsum)
    {
        if(pointsum==3)//终止条件
        {
            if(isvaild(s, index,s.size()-1 ))//如果合法
            {
                res.push_back(s);
               
            }
             return;
        }
        for(int i=index;i<s.size();i++)//树形结构
        {
            if(isvaild(s, index, i))
            {
                s.insert(s.begin()+i+1,'.');
                pointsum++;
                backtracking(s, i+2, pointsum);//注意i+2，因为插入了一个句号
                pointsum--;
                s.erase(s.begin()+i+1);
            }
        }
        return;
    }
    vector<string> restoreIpAddresses(string s) {
    backtracking(s, 0, 0);
    return res;
    }
};

Leetcode 78 子集 

题目链接：78. 子集 - 力扣（LeetCode）

代码随想录题解：代码随想录 (programmercarl.com)

思路：这个题目是很典型的模板题目，需要注意的一点就是需要将往res数组中插入的语句写在终止条件上面，不然会漏掉每层的元素。可以这么理解，这条语句在最开头就是统计每层的情况，在终止条件里面就是统计符合终止条件的情况。

代码：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int>&nums,int index)
    {
         res.push_back(path) ;//注意
        if(index>=nums.size())
        {
            return;
        }
        for(int i=index;i<nums.size();i++)
        {
            path.push_back(nums[i]);
            backtracking(nums, i+1);
            path.pop_back();
        }
        return;
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
     backtracking(nums, 0);
     return res;
    }
};

Leetcode 90 子集Ⅱ

题目链接：90. 子集 II - 力扣（LeetCode）

代码随想录题解：代码随想录 (programmercarl.com)

思路：这个题目与普通子集的区别是统计的数组中可能有重复元素，那么我们就需要考虑去重的逻辑，而去重昨天的题目中也涉及到了，就是用一个used数组标记。

代码：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int>&nums,int index,vector<bool>used)
    {
     res.push_back(path);
     if(index>=nums.size())
     {
        return;
     }
     for(int i=index;i<nums.size();i++)
     {
      if(i>0&&used[i-1]==false&&nums[i]==nums[i-1])//注意去重
      {
        continue;
      }
      path.push_back(nums[i]);
      used[i]=true;
      backtracking(nums, i+1, used);
      path.pop_back();
      used[i]=false;
     }
     return;
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
     sort(nums.begin(),nums.end());
     vector<bool>used(nums.size(),false);
     backtracking(nums, 0, used);
     return res;
     
    }
};

总结

回溯算法需要注意的点不多，一个就是终止条件，一个是树形逻辑，递归语句是一个往下层推的过程，for循环是在当前层遍历的过程。