• 每日刷题记录 (六)

    文章目录

    第一题: 剑指 Offer II 079. 所有子集

    LeetCode: 剑指 Offer II 079. 所有子集
    描述:
    给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
    解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
    在这里插入图片描述

    解题思路:

    经典回溯题;
    注意这里的剪枝.

    • 剪枝1: 不能重复使用同一元素
    • 剪枝2: 不能包含重复的子集

    代码实现:

    class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return result;
    }
    public void dfs(int[] nums, int start) {
        result.add(new ArrayList<>(ret));
        // 剪枝1: i=start 就是确保了不包含重复子集
        for(int i = start; i < nums.length; i++) {
            ret.add(nums[i]);
            // 剪枝2: 这里传 i+1 确保了不重复使用同一个元素
            dfs(nums,i+1);
            ret.remove(ret.size()-1);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    第二题: 剑指 Offer II 080. 含有 k 个元素的组合

    LeetCode: 剑指 Offer II 080. 含有 k 个元素的组合
    描述:
    给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
    在这里插入图片描述

    解题思路:

    经典回溯
    注意剪枝

    • 剪枝1: 不能使用重复元素
    • 剪枝2: 不能有重复的子集

    代码实现:

    class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = i+1;
        }
        dfs(arr,0,k);
        return result;
    }
    public void dfs(int[] arr,int start, int k) {
        if(ret.size() == k) {
            result.add(new ArrayList<>(ret));
            return;
        }
        // 剪枝1: 让i=start 确保了没有重复的子集
        for(int i = start; i < arr.length; i++) {
            ret.add(arr[i]);
            // 剪枝2: 传入 i+1 确保了不使用重复元素
            dfs(arr,i+1,k);
            ret.remove(ret.size() - 1);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    第三题: 剑指 Offer II 081. 允许重复选择元素的组合

    LeetCode: 剑指 Offer II 081. 允许重复选择元素的组合
    描述:
    给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

    candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。

    对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
    在这里插入图片描述

    解题思路:

    经典回溯
    注意剪枝

    • 剪枝1: 不要出现重复的情况

    代码实现:

    class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,0,target);
        return result;
    }
    public void dfs(int[] candidates, int start, int target) {
        if (target == 0) {
            result.add(new ArrayList<>(ret));
            return;
        }
        // 剪枝1: i = start 确保不会重复子集
        for(int i = start; i < candidates.length; i++) {
            if(candidates[i] <= target){
                ret.add(candidates[i]);
                // 传入i 就会重复使用当前元素
                dfs(candidates,i,target-candidates[i]);
                ret.remove(ret.size()-1);
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    第四题: 剑指 Offer II 082. 含有重复元素集合的组合

    LeetCode: 剑指 Offer II 082. 含有重复元素集合的组合
    描述:
    给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

    candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。
    在这里插入图片描述

    解题思路:

    经典回溯:
    这里注意剪枝:

    • 剪枝1: 不能出现重复组合
    • 剪枝2: 不能重复使用元素
    • 剪枝3: 数组含有重复元素

    代码实现:

    class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] tmp = new boolean[candidates.length];
        dfs(candidates,0,target,tmp);
        return result;
    }
    public void dfs(int[] candidates, int start, int target,boolean[] tmp) {
        if(target == 0) {
            result.add(new ArrayList<>(ret));
            return;
        }
        // 剪枝1: i=start确保不会出现重复组合
        for (int i = start; i < candidates.length; i++) {
         	// 剪枝3: 使用boolean数组来标记,确保了出现重复元素的情况
            if(i>0 && candidates[i] == candidates[i-1] && !tmp[i-1]){
                continue;
            }
            if(candidates[i] <= target) {
                ret.add(candidates[i]);
                tmp[i] = true;
                // 剪枝2: i+1就是为了确保不会出现使用自己, 但是可以使用别人
                dfs(candidates,i+1,target-candidates[i],tmp);
                tmp[i] = false;
                ret.remove(ret.size()-1);
            }
            
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    第五题: 剑指 Offer II 083. 没有重复元素集合的全排列

    LeetCode: 剑指 Offer II 083. 没有重复元素集合的全排列
    描述:
    给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
    在这里插入图片描述

    解题思路:

    经典回溯
    注意剪枝

    • 剪枝1: 不能重复使用当前元素

    代码实现:

    class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] tmp = new boolean[nums.length];
        dfs(nums,tmp);
        return result;
    }
    public void dfs(int[] nums, boolean[] tmp) {
        if (ret.size() == nums.length) {
            result.add(new ArrayList<>(ret));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 剪枝1: 使用boolean数组来标记, 如果当前下标是false就是没用过
            if (!tmp[i]) {
                tmp[i] = true;
                ret.add(nums[i]);
                dfs(nums,tmp);
                tmp[i] = false;
                ret.remove(ret.size()-1);
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    第六题: 剑指 Offer II 084. 含有重复元素集合的全排列

    LeetCode: 剑指 Offer II 084. 含有重复元素集合的全排列
    描述:
    给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
    在这里插入图片描述

    解题思路:

    经典回溯
    注意剪枝

    • 剪枝1: 不能重复使用当前元素
    • 剪枝2: 注意数组中重复的元素

    代码实现:

    class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] tmp = new boolean[nums.length];
        dfs(nums,tmp);
        return result;
    }
    public void dfs(int[] nums, boolean[] tmp) {
        if (ret.size() == nums.length) {
            result.add(new ArrayList<>(ret));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
       		// 剪枝2: 从第二个元素开始, 如果当前元素和前一个元素是一样的,且前一个元素没有使用, 直接跳过
            if(i > 0 && nums[i] == nums[i-1] && !tmp[i-1]){
                continue;
            }
            // 剪枝1: 使用boolean数组来标记, 如果当前下标是false就是没用过
            if(!tmp[i]){
                tmp[i] = true;
                ret.add(nums[i]);
                dfs(nums,tmp);
                tmp[i] = false;
                ret.remove(ret.size()-1);
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    第七题: 剑指 Offer II 085. 生成匹配的括号

    LeetCode: 剑指 Offer II 085. 生成匹配的括号
    描述:
    正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
    在这里插入图片描述

    解题思路:

    这里left表示左括号数, right表示右括号数
    剪枝1: right或left<0
    剪枝2: right<left (确保了先使用左括号,排除了不合法情况)

    代码实现:

    class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backstrack(result,"",n,n);
        return result;
    }
    public void backstrack(List<String> result,String str,int left, int right) {
    	// 剪枝1
        if(left < 0 || right <0) return;
        // 剪枝2
        if(left > right) return;
        if(left == 0 && right == 0 ) {
            result.add(str);
            return;
        }
        backstrack(result,str+"(",left-1,right);
        backstrack(result,str+")",left,right-1);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    第八题: 剑指 Offer II 086. 分割回文子字符串

    LeetCode: 剑指 Offer II 086. 分割回文子字符串

    描述:
    给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。

    回文串 是正着读和反着读都一样的字符串。
    在这里插入图片描述

    解题思路

    经典回溯
    注意剪枝
    剪枝1: 不能重复使用当前元素
    剪枝2: 不能出现重复组合
    剪枝3: 必须是回文

    代码实现:

    class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> ret = new ArrayList<>();
    public String[][] partition(String s) {
        bfs(s,0);
        String[][] str = new String[result.size()][];
        int i = 0;
        for(List<String> list : result){
            str[i++] = list.toArray(new String[list.size()]);
        }
        return str;
    }
    public void dfs(String s,int start) {
        if(s.length() == start) {
            result.add(new ArrayList<>(ret));
            return;
        }
        // 剪枝1: 不能出现重复组合
        for(int i = start; i < s.length(); i++) {
       		// 剪枝3: 必须是回文
            if(isHui(s,start,i)) {
            	// 剪枝2: 不能重复使用同一个元素
                ret.add(s.substring(start,i+1));
                bfs(s,i+1);
                ret.remove(ret.size()-1);
            }
        }
    }
    public boolean isHui(String s,int left, int right) {
        while(left<right) {
            if(s.charAt(left) == s.charAt(right)){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
  • 相关阅读:
    Uniapp中textarea中输入完会触发上一段代码的click事件
    机器学习实战——训练模型
    山东大学项目实训十——Android开发环境搭建
    用nginx作反向代理时，请求头中含波浪线无法转发请求的解决方法
    查找已注册的 Spring Security 过滤器
    Linux常用命令
    AI生成PPT：如何轻松制作专业的答辩PPT？
    Go：TernarySearch三元搜索(附完整源码)
    awk入门教程
    备战2024秋招面试题（1）
  • 原文地址：https://blog.csdn.net/wwzzzzzzzzzzzzz/article/details/125478218