代码随想录算法训练营第二十一天 | 93.复原IP地址 | 78.子集

时间：2024-11-21 07:35:43

Day 20 总结

  • 自己实现中遇到哪些困难
    • 一句话讲明白问题分类
      • 组合问题和分割问题都是收集树的叶子节点，子集问题是找树的所有节点！
    • 切割字符串问题回顾
      • 昨天的切割回文子串，和今天的切割ip地址，都是需要将字符串拆分成 n 份。
      • 只不过每一小份的长度不定，切完当前这一小份，再交给下层去切割剩余部分。
  • 今日收获，记录一下自己的学习时间
    • 17:30 - 19:00

93.复原IP地址

题目链接/文章讲解：代码随想录

题目链接：https://leetcode.cn/problems/restore-ip-addresses/

题目描述：

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

实现思路：

将字符串分隔成四个部分，并且每个部分都是有效的数字0-255。

1.字符串分隔：一定是从前向后进行切割，先切割一个数字出来，然后再对剩下的字符串再次进行切割。然后要检查当前切割出来的字符串是不是合格的，如果前面都切不出来合格的字符串，后面的切割也没有意义，直接结束该分支的搜索。找到了一个合适的字符串，就传递到下层一次，再剩余字符串中继续切割。当前层切割的字符串长度慢慢递增。

2.检查切割的结果：到达搜索树的结尾时，要确保整个字符串已经切割完了，并且切割成了四个部分。排除不符合条件的分支，并把切割完的字符串收集到结果集合中。

回溯模板：

代码实现：

class Solution {
    public List<String> results = new ArrayList<>();
    public List<String> path = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        backtrack(s, 0);
        return results;
    }

    // 参数：
    // 返回值:
    public void backtrack(String s, int startIndex) {
        // 终止条件
        if (path.size() > 4) {return;} 
        if (startIndex == s.length() && path.size() == 4) {
            StringBuffer ipAddr = new StringBuffer();
            for (int i=0; i<4; i++) {
                ipAddr.append(path.get(i));
                if (i < 3) {ipAddr.append(".");}
            }
            results.add(ipAddr.toString());
        }

        // 回溯单层搜索过程
        for (int i=startIndex; i<s.length(); i++){
            if (!isValid(s, startIndex, i+1)) {continue;}
            path.add(s.substring(startIndex, i+1));
            backtrack(s, i+1);
            path.remove(path.size()-1);
        }
    }

    public boolean isValid(String s, int start, int end) {
        if (end - start > 3) {return false;}
        if (s.charAt(start) == '0') {
            if (end - start > 1) {return false;}
        }
        if (end - start > 2) {
            if (s.charAt(start) == '0') {return false;}
            if (Integer.parseInt(s.substring(start,end)) > 255) {return false;}
        }
        return true;
    }
}

// 实现方案2
class Solution {
    List<Integer> path = new ArrayList<>();
    List<String> results = new ArrayList<>();
    char[] arr;

    public List<String> restoreIpAddresses(String s) {
        arr = s.toCharArray();
        backtrack(0);
        return results;
    }

    public void backtrack(int startIdx) {
        if (path.size() > 4 || startIdx > arr.length) return;
        if (startIdx == arr.length && path.size() == 4) {
            String s = "";
            for (Integer i : path) s = s+i+".";
            results.add(s.substring(0,s.length()-1));
        }

        for (int i=startIdx; i<arr.length; i++) {
            int num = getNum(startIdx, i);
            if (num == -1) return;

            path.add(num);
            backtrack(i+1);
            path.remove(path.size()-1);
            
        }
    }

    public int getNum(int start, int end) {
        // 小于四位数
        if (end - start >= 3) return -1;
        // 没有前导0
        if (arr[start] == '0') {
            if (end > start) return -1;
            return 0;
        }
        // 1-255
        int num = 0;
        while (start <= end) {
            num = num * 10 + (int)(arr[start++]-'0');
        }
        if (num > 255) return -1;
        return num;
    }
}

78.子集

题目链接/文章讲解：代码随想录

题目链接：https://leetcode.cn/problems/subsets/

题目描述：

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

实现思路：

收集搜索树上的所有节点。

回溯模板：

代码实现：

class Solution {
    // 全局变量免去参数传递
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        results.add(new ArrayList<>(path)); // 空集
        backtrace(0);
        return results;
    }

    public void backtrace(int startIdx) {
        // 到达底搜索树底层，向上返回
        if (startIdx >= nums.length) return;
        
        for (int i=startIdx; i<nums.length; i++) {
            path.add(nums[i]);
            results.add(new ArrayList<>(path)); // 收集所有情况
            backtrace(i+1);
            path.remove(path.size()-1);
        }
    }
}

相关文章