代码随想录算法训练营29期|day28 任务以及具体安排

发布时间:2024年01月23日
  • ?93.复原IP地址?
    class Solution {
        List<String> result = new ArrayList<>();
        public List<String> restoreIpAddresses(String s) {
            StringBuilder sb = new StringBuilder(s);
            backTracking(sb, 0, 0);
            return result;
        }
        private void backTracking(StringBuilder s, int startIndex, int dotCount){
            if(dotCount == 3){
                if(isValid(s, startIndex, s.length() - 1)){
                    result.add(s.toString());
                }
                return;
            }
            for(int i = startIndex; i < s.length(); i++){
                if(isValid(s, startIndex, i)){
                    s.insert(i + 1, '.');
                    backTracking(s, i + 2, dotCount + 1);
                    s.deleteCharAt(i + 1);
                }else{
                    break;
                }
            }
        }
        //[start, end]
        private boolean isValid(StringBuilder s, int start, int end){
            if(start > end)
                return false;
            if(s.charAt(start) == '0' && start != end)
                return false;
            int num = 0;
            for(int i = start; i <= end; i++){
                int digit = s.charAt(i) - '0';
                num = num * 10 + digit;
                if(num > 255)
                    return false;
            }
            return true;
        }
    }

    思路:与day27的分割回文子串类似,主要是要理解isVaild的思路,当dotCount == 3时,还要进行判断,然后将符合的加入result中

  • ?78.子集?
    class Solution {
        List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
        LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
        public List<List<Integer>> subsets(int[] nums) {
            subsetsHelper(nums, 0);
            return result;
        }
    
        private void subsetsHelper(int[] nums, int startIndex){
            result.add(new ArrayList<>(path));//「遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合」。
            if (startIndex >= nums.length){ //终止条件可不加
                return;
            }
            for (int i = startIndex; i < nums.length; i++){
                path.add(nums[i]);
                subsetsHelper(nums, i + 1);
                path.removeLast();
            }
        }
    }

    思路:和分割问题类似,主要区别是要在每个节点收获结果,所以result.add(new ArrayList<>(path)要放在最上面。

  • ?90.子集II??
    class Solution {
       List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
       LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
       boolean[] used;
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            if (nums.length == 0){
                result.add(path);
                return result;
            }
            Arrays.sort(nums);
            used = new boolean[nums.length];
            subsetsWithDupHelper(nums, 0);
            return result;
        }
        
        private void subsetsWithDupHelper(int[] nums, int startIndex){
            result.add(new ArrayList<>(path));
            if (startIndex >= nums.length){
                return;
            }
            for (int i = startIndex; i < nums.length; i++){
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                    continue;
                }
                path.add(nums[i]);
                used[i] = true;
                subsetsWithDupHelper(nums, i + 1);
                path.removeLast();
                used[i] = false;
            }
        }
    }

    思路:和?40.组合总和II方法一样,都是要进行树层去重。关键是used数组的使用,要确保used[i-1]==false;然后就是每个节点都收获结果。

文章来源:https://blog.csdn.net/m0_68520551/article/details/135786975
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。