算法训练day30 LeetCode93.78.90

93.复原IP地址

题目

93. 复原 IP 地址 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• 使用'.'切割字符串、结束条件为字符串中有三个'.'、同时要确定字符串符合的条件

  • 长度为不为1时，首字符不能是0
  • 数值大小在[0,255]
  • 单个字符在'0'~'9'

• class Solution
  {
  private:
      vector<string> result; // 记录结果
      void backtracking(string &s, int startIndex, int pointNUm)
      {
          if (pointNUm == 3)		//结束条件：有三个'.'，并且最后的字符串合法
          {
              if (isValid(s, startIndex, s.size() - 1))
              {
                  result.push_back(s);
              }
              return;
          }
          for (int i = startIndex; i < s.size(); i++)	//遍历各种切割长度组合
          {
              if (isValid(s, startIndex, i))		//当子字符串合法 
              {
                  s.insert(s.begin() + i + 1, '.');	//切割
                  pointNUm++;
                  backtracking(s, i + 2, pointNUm);	//并判断后面的子字符串
                  pointNUm--;						//回溯
                  s.erase(s.begin() + i + 1);
              }
              else
                  break;
          }
      }
      bool isValid(const string &s, int start, int end)	//字符串是否合法
      {
          if (start > end)
          {
              return false;
          }
          if (s[start] == '0' && start != end)	//长度大于1 首字符不为0
              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)						//值在[0,255]
                  return false;
          }
          return true;
      }
  
  public:
      vector<string> restoreIpAddresses(string s)
      {
          result.clear();
          if (s.size() < 4 || s.size() > 12)
              return result;
          backtracking(s, 0, 0);
          return result;
      }
  };
  

78.子集

题目

78. 子集 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• 子集中元素的数目是0~n,与切割和组合的区别是除了收集叶子结点外，其他各结点的结果也要收集

• class Solution
  {
  private:
      vector<vector<int>> result;
      vector<int> path;
      void backtracking(vector<int> &nums, int startIndex)
      {
          result.push_back(path);	//提前收集，防止遗漏
          if (startIndex >= nums.size())	//结束的条件是待选择元素集已经遍历完
          {
              return;
          }
          for (int i = startIndex; i < nums.size(); i++)	//横向遍历不同组合
          {
              path.push_back(nums[i]);
              backtracking(nums, i + 1);
              path.pop_back();	//回溯
          }
      }
  
  public:
      vector<vector<int>> subsets(vector<int> &nums)
      {
          result.clear();
          path.clear();
          backtracking(nums, 0);
          return result;
      }
  };
  

90.子集II

题目

90. 子集 II - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• 集合中有重复元素，并且子集不能重复，需要在树层去重

  • 去重采用used数组标记集合中对应数字是否使用，默认标记为已使用，可以较方便的实现后出现重复元素的确认

  class Solution
  {
  private:
      vector<vector<int>> result;
      vector<int> path;
      //used为元素是否使用标记数组
      //used[i]==false 意味着i-1元素在树层被使用过
      //used[i]==true 意味着i-1元素在树枝被使用过
      void backtracking(vector<int> &nums, int startIndex, vector<bool> &used)
      {
          result.push_back(path);
          for (int i = startIndex; i < nums.size(); i++) //横向选择剩余元素
          {
              if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
                  continue;			//同层使用过，跳过
              path.push_back(nums[i]);
              used[i] = true;
              backtracking(nums, i + 1, used);
              used[i] = false;		//回溯
              path.pop_back();
          }
      }
  
  public:
      vector<vector<int>> subsetsWithDup(vector<int> &nums)
      {
          result.clear();
          path.clear();
          vector<bool> used(nums.size(), false);
          sort(nums.begin(), nums.end());
          backtracking(nums, 0, used);
          return result;
      }
  };