代码随想录算法训练营第二十六天|39. 组合总和、 40.组合总和II、 131.分割回文串

发布于:2024-06-17 ⋅ 阅读:(98) ⋅ 点赞:(0)

39. 组合总和

在这里插入图片描述

题目链接:39. 组合总和
文档讲解:代码随想录
状态:卡了一会儿

思路:先排序,方便剪枝。允许数字重复使用,因此递归调用时传入当前索引i。

题解:

public class Solution {
    // 用于存储所有可能的组合
    private List<List<Integer>> res = new ArrayList<>();
    // 当前正在构建的组合
    private LinkedList<Integer> list = new LinkedList<>();
    // 用于存储当前组合的和
    private int sum = 0;

    /**
     * 组合求和函数
     * @param candidates 候选数字数组
     * @param target 目标数字
     * @return 所有可能的组合列表
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 首先对候选数字进行排序
        Arrays.sort(candidates);
        // 调用回溯函数
        backtracking(candidates, target, 0);
        // 返回所有可能的组合
        return res;
    }

    /**
     * 回溯函数,用于递归地搜索所有可能的组合
     * @param candidates 候选数字数组
     * @param target 目标数字
     * @param startIndex 当前搜索的起始索引
     */
    public void backtracking(int[] candidates, int target, int startIndex) {
        // 如果当前和大于目标,则回溯
        if (sum > target) {
            return;
        }
        // 如果当前和等于目标,将当前组合添加到结果列表中
        if (sum == target) {
            res.add(new ArrayList<>(list));
            return;
        }
        // 遍历候选数字,从startIndex开始,直到sum+当前数字大于目标或遍历完所有数字
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            // 将当前数字添加到当前组合中,并更新当前和
            sum += candidates[i];
            list.add(candidates[i]);
            // 递归调用回溯函数,搜索当前数字之后的组合
            backtracking(candidates, target, i); // 注意这里传入i,允许重复使用同一个数字
            // 回溯,移除当前数字,恢复当前和
            sum -= candidates[i];
            list.removeLast();
        }
    }
}

40.组合总和II

在这里插入图片描述

题目链接:40.组合总和II
文档讲解:代码随想录
状态:自己在去重的时候,将集合中的重复元素也去掉了,导致结果缺少。集合(数组candidates)有重复元素,但还不能有重复的组合,这个不会处理。

思路:使用used数组标记树层或树枝中的元素是否使用,从而将集合有重复元素和结果又重复组合区分开。
默认used数组都为false,树层有重复元素和树枝有重复元素的关键区别在于used[i-1]是否为true,树层中元素因为回溯会使used[i-1]恢复成false,树枝中有重复元素则used[i-1]使用过,因此为true。在这里插入图片描述

题解:

    List<List<Integer>> res = new ArrayList<>();  // 结果集
    LinkedList<Integer> list = new LinkedList<>();  // 当前组合
    int sum = 0;  // 当前组合的和

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);  // 排序,方便后续处理
        boolean[] used = new boolean[candidates.length];  // 记录每个元素是否被使用过
        Arrays.fill(used, false);  // 初始化为未使用
        backtracking(candidates, used, target, 0);  // 开始回溯
        return res;  // 返回结果集
    }

    public void backtracking(int[] candidates, boolean[] used, int target, int startIndex) {
        if (sum == target) {  // 当前组合的和等于目标值
            res.add(new ArrayList<>(list));  // 将当前组合加入结果集
            return;
        }
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {  // 去重
                continue;
            }
            sum += candidates[i];  // 做出选择,更新当前组合的和
            list.add(candidates[i]);  // 将当前元素加入当前组合
            used[i] = true;  // 标记当前元素已被使用
            backtracking(candidates, used, target, i + 1);  // 递归,处理下一个元素
            list.removeLast();  // 撤销选择,回溯到上一个状态
            used[i] = false;  // 标记当前元素未被使用
            sum -= candidates[i];  // 更新当前组合的和
        }
    }

131.分割回文串

在这里插入图片描述

题目链接:131.分割回文串
文档讲解:代码随想录
状态:不会,想到分割方法,代码没写出来!

代码没写出来的原因:

  1. 写成了 if (startIndex == chars.length) { res.add(new ArrayList<>(list)); return; }认为 startIndex == chars.length - 1 时将list添加到res中。实际上因为backtracking(chars, i + 1);的存在,res中添加list的操作都是在下次递归中完成的,而这时i+1就导致startIndex每次都比原来的大了1。
  2. 写成了new String(chars, startIndex, i),而实际上第三个参数是长度
    // 存储所有分割方案的列表
    List<List<String>> res = new ArrayList<>();
    // 当前正在构建的分割方案
    LinkedList<String> list = new LinkedList<>();

    /**
     * 将字符串分割成回文子串的方案
     * @param s 输入的字符串
     * @return 分割方案的列表
     */
    public List<List<String>> partition(String s) {
        // 将字符串转换为字符数组
        char[] chars = s.toCharArray();
        // 从索引0开始回溯
        backtracking(chars, 0);
        // 返回所有分割方案
        return res;
    }

    /**
     * 回溯函数,用于递归地搜索所有可能的回文子串分割方案
     * @param chars 字符串转换后的字符数组
     * @param startIndex 当前搜索的起始索引
     */
    public void backtracking(char[] chars, int startIndex) {
        // 如果当前索引等于字符数组的长度,说明已经处理完所有字符,将当前方案添加到结果中
        if (startIndex == chars.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        // 从当前索引开始,尝试所有可能的分割点
        for (int i = startIndex; i < chars.length; i++) {
            // 如果从startIndex到i的子串是回文串,则将其添加到当前方案中
            if (isPalindrome(chars, startIndex, i)) {
                // 添加子串到当前方案
                list.add(new String(chars, startIndex, i - startIndex + 1));
                // 递归调用回溯函数,继续搜索i之后的分割方案
                backtracking(chars, i + 1);
                // 回溯,移除最后一个添加的子串,以便尝试其他分割方案
                list.removeLast();
            }
        }
    }

    /**
     * 判断子串是否为回文串
     * @param chars 字符数组
     * @param start 子串的起始索引
     * @param end 子串的结束索引
     * @return 如果子串是回文串返回true,否则返回false
     */
    public boolean isPalindrome(char[] chars, int start, int end) {
        // 从子串的两端向中间遍历,如果字符不相等则不是回文串
        while (start <= end) {
            if (chars[start] != chars[end]) {
                return false;
            }
            start++;
            end--;
        }
        // 如果遍历完所有字符都相等,则子串是回文串
        return true;
    }

网站公告

今日签到

点亮在社区的每一天
去签到