当前位置：首页 > article >正文

《代码随想录》Day23打卡！

article 2025/1/5 14:50:59

《代码随想录》回溯算法：组合总和

本题的完整题目如下：

本题的完整思路如下： 1.本题是使用回溯算法，所以分为三步： 2.第一步：首先确定递归的参数和返回值，回溯的返回值一般是空，参数有：原数组，目标值，总和，还有一个数来指导下次遍历从哪里开始遍历。 3.第二步：递归的终止条件，即收割结果的条件：当总和等于目标值时，此时将path数组复制到结果数组中，是复制而不是直接添加，因为path是一个全局变量，如果直接添加，path还会随着后边的遍历改变，就不是当前结果了。如果总和大于了目标值或者statindex值超出了数组的长度值，则返回。 4.第三步：单次递归函数的逻辑：从startindex开始遍历数组，将数组的数加到总和里，将该数添加到path数组中，由于本题中说数组中的数字可以使用无限次，所以startindex=i，而不是startindex=i，代表着下一次依然可以使用该元素，接着进行递归。接着将该数从path移除，并将总和减去该数，这个步骤叫做恢复现场。 5.使用参数startindex来控制下一次遍历的起始位置！要理解为什么要恢复现场，以及怎么恢复。 本题的完整代码如下：

//39. 组合总和
class Solution4 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backstrack(candidates, target, sum, 0);
        return res;
    }
    public void backstrack(int[] candidates, int target, int sum, int startindex) {
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        if (sum > target || startindex >= candidates.length){
            return;
        }
        for(int i = startindex; i < candidates.length; i++){
            path.add(candidates[i]);
            sum += candidates[i];
            backstrack(candidates, target, sum, i);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

《代码随想录》回溯算法：组合总和II

本题的完整题目如下：

本题的完整思路如下： 1.本题相比与上一题，多了一些条件，数组中含有重复元素，最后的结果是无序的，即元素相同顺序不同算是同一个答案。所以本题相比于上一题来说增加了一个去重的步骤。 2.由于本题要去重，但是要搞明白，数组中的相等数字的不同元素是可以同时使用的，这个不算是重复，因为原数组中本来就有两个该元素。 3.本题与上一题的不同之处在于：首先，对数组进行排序；其次，定义一个boolean类型的数组，大小与原数组的大小保持一致，用来记录数组中的元素有没有使用过，0代表没有使用过，1代表使用过，初始值为0；接着，开始遍历，将对应boolean数组中对应位置的元素变为1，表示已经使用过了。接下来是去重操作：判断当前元素是否与前一个元素相等并且前一个元素的used值为0，即前一个元素没有使用过，这样做是为了排除数组中相同元素的使用，这是合理的；如果相等，则结束该i值得遍历，将i+1继续进行遍历。接着将该元素添加到path数组中，并将其累加到sum中，接着进行递归，注意本题是不可以重复使用某一个元素得，所以递归时startindex值为当前i值加1。后边的逻辑就与上一题一致，恢复现场时记得将used数组中对应的元素的位置置为0。 4.本题的难点在于去重，除此之外，由于题目中说了数组中可能会有重复元素，所以不能根据元素是否相同来判断是否为重复，必须结合used数组进行判断。本题的完整代码如下：

//40.组合总和II
class Solution5 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        backstrack(candidates, target, 0, used);
        return res;
    }
    public void backstrack(int[] candidates, int target, int startindex, boolean[] used) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        if(sum > target || startindex >= candidates.length){
            return;
        }
        for(int i = startindex; i < candidates.length; i++) {
            if(i >= 1 && candidates[i - 1] == candidates[i] && used[i - 1] == false) {
                continue;
            }
            //剪枝操作
            if(sum + candidates[i] > target){
                break;
            }
            path.add(candidates[i]);
            sum += candidates[i];
            used[i] = true;
            backstrack(candidates, target, i + 1, used);
            sum -= candidates[i];
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

}

《代码随想录》回溯算法：分割回文串

本题的完整题目如下：

本题的完整思路如下： 1.本题也是使用递归加回溯： 2.第一步：确定递归函数中的参数和返回值：参数有：字符串，startindex。返回值无 3.第二步：确定收割结果的条件：当startindex大于等于原字符串的长度时，表示已经遍历结束了，此时收割结果。 3.第三步：确定单层函数中的逻辑：首先，搞明白分割的字符串是S[i，startindex]这个区间内的字符串，接着判断该字符串是否为回文串，如果是则将该字符串添加到path数组中，并进行递归，接着进行回溯。 4.如何判断是否为回文串：使用双指针进行判断。 5.本题的难点是，如何获取所分割的字符串，区间是什么，startindex到i之间的字符串，包括第i个字符，如果是的话，就添加，递归，回溯。如果不是，则进行下一次循环，即将i+1，此时再判断当前的字符串是否是回文串，以此类推............ 本题的完整代码如下：

//66.分割回文串
class Solution6 {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtrack(s, 0);
        return res;
    }
    public void backtrack(String s, int startindex) {
        if(startindex >= s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = startindex; i <= s.length() - 1; i++){
            String temp = s.substring(startindex, i + 1);
            if(ispartition(temp)) {
                path.add(temp);
                backtrack(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }
    private boolean ispartition(String temp){
        int left = 0;
        int right = temp.length() - 1;
        while(left < right){
            if(temp.charAt(left) != temp.charAt(right)){
                return false;
            }
            right--;
            left++;
        }
        return true;
    }
}

查看全文

http://www.kler.cn/a/464313.html