代码随想录算法训练营 DAY 27 | 93.复原IP地址 78.子集 90.子集II

93.复原IP地址

和分割回文串很类似，用StringBuilder！区别在于这里要实际加"."，还多了一个pointNum计算打点个数。pointNum=3了就检验最后一段isValid(sb, startIndex,sb.length()-1)，合法就提交。最后一次就不用拼东西了！。

注意单层搜索逻辑中，要 s.insert(i + 1, '.');拼接！然后下一层搜索传的是i+2（加上"."了）。如果判断不合法就break退出循环（不要让i继续往后搜了！）

[startIndex, i] 这个区间就是for循环里每次截取的子串！！！

判断地址是否合法，主要判断3个：

• 如果是长度不为1的段，首位0
• 段位如果大于255了不合法（num累加每一位的数字，每一次for循环都要判断是否num＞255）

  ---

  • 回顾回溯算法模板：

    void backtracking(参数) {
        if (终止条件) {
            存放结果;
            return;
        }
        for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
            处理节点;
            backtracking(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
    }
    

    1. 递归参数：s，startIndex，pointNum

    void backtracking(String s, int startIndex, int pointNum)
    

    1. 终止条件

    不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件！

    if(pointNum == 3) {
        //判断第四段是否合法 [startIndex,s.length()-1]
        if(isValid(s,startIndex,s.length()-1)) {
            result.add(sb.toString);
        }
    }
    

    1. 单层搜索逻辑

    [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。

    语法点注意：

    • 构造sb同时传一个String：StringBuilder sb = new StringBuilder(s);

    • sb可以在指定位置插入指定字符：sb.insert(i + 1, ‘.’);

      在指定位置删除指定字符：sb.deleCharAt(i + 1);

      获取指定位置字符也用sb.charAt()

    • 判断合法时，for循环每一次累加都要判断一次是否num>255，不要累加完再判断！

    • 完整代码

      class Solution {
          List result = new ArrayList();
          public List restoreIpAddresses(String s) {
              StringBuilder sb = new StringBuilder(s);
              backtracking(sb,0,0);
              return result;
          }
          public void backtracking(StringBuilder sb, int startIndex, int pointNum) {
              if(pointNum == 3) {
                  //判断第四段合不合法，合法直接把提交sb（不用再拼了！）
                  if(isValid(sb, startIndex,sb.length()-1)) {
                      result.add(sb.toString());
                  }
                  return;
              }
              for(int i = startIndex; i  end) return false;
              if(sb.charAt(start) == '0' && start != end) return false;
              int num = 0; //遍历 计算这一段表示的数值大小
              for(int i = start; i 
                  int digit = sb.charAt(i) - '0'; //这一位上的数字
                  num = 10 * num + digit;
                  if(num  255) return false;
              }
              return true;
          }                    
      }
      

      78.子集

      遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合（组合问题是遍历到结果了才记录）

      子集、组合、分割问题，回溯算法的for都是从startIndex开始（无序，取过的不会重复取）

      • 注意：每次进入递归就收集一次结果！（收集的是上一层的！）

        class Solution {
            List result = new ArrayList();
            List path = new ArrayList();
            public List subsets(int[] nums) {
                backtracking(nums, 0);
                return result;
            }
            public void backtracking(int[] nums, int startIndex) {
                result.add(new ArrayList(path));  //每次进入递归就收集一次结果！（收集的是上一层的！）
                //终止条件
                if(startIndex >= nums.length) return;
                for(int i = startIndex; i  
        90.子集II
         
        区别在于能集合中可能包含重复元素（比如给定nums[1,2,2] 子集可以是[2,2]）
         
        

        • 类似于40.组合总和 II，我们要树枝去重（排序后用used数组）

          排序后相同元素相邻了，根据used[i-1]==0树枝去重！（当i>0时）continue跳到下一个i

          ​ if(i > 0 && nums[i]==nums[i-1] && used[i-1]==0) continue;

          class Solution {
              List result = new ArrayList();
              List path = new ArrayList();
              public List subsetsWithDup(int[] nums) {
                  Arrays.sort(nums);
                  int[] used = new int[nums.length];
                  Arrays.fill(used,0);
                  backtracking(nums,0,used);
                  return result;
              }
              public void backtracking(int[] nums,int startIndex, int[] used){
                  result.add(new ArrayList(path));
                  if(startIndex >= nums.length) return;
                  for(int i = startIndex; i 0时）continue跳到下一个i
                      if(i > 0 && nums[i]==nums[i-1] && used[i-1]==0) continue;
                      path.add(nums[i]);
                      used[i] = 1;
                      backtracking(nums,i+1,used);
                      path.remove(path.size()-1);
                      used[i] = 0;
                  }
              }
          }
          

          Day28 总结

          • 如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

          • 子集，组合，分割问题，回溯算法的for都是从startIndex开始！（无序，取过的元素不会重复取）排列问题的for是从0开始！（有序，[1,2]和[2,1]是两个）

          • 子集问题进入递归就先收集结果（收集的其实是上一层的）-

          • 如果nums有重复元素，先排序。树枝去重用used数组（i > 0 && nums[i]==nums[i-1] && used[i-1]==0），continue跳到下一个i