乐趣区

关于算法:算法训练LeetCode-39-组合总和-40组合总和II-131分割回文串

jiezi

欢送关注集体公众号：爱喝可可牛奶

LeetCode 39. 组合总和 40. 组合总和 II 131. 宰割回文串

LeetCode 39. 组合总和

剖析

回溯可看成对二叉树节点进行组合枚举，分为横向和纵向

每次往 sum 增加新元素时，必须明确从 can 哪个地位开始，定义变量 pos

返回条件 sum == target 或 sum > target; 横向完结条件 没有新元素能够增加了即 pos<can.length;

bt(can, sum, tar, pos){if(sum == tar) add return;
    if(sum > tar) pos++ return;
    for(int i = pos; i < can.len;i++){sum+=can[pos];
        bt(can, sum, tar, i);
        sum-=can[pos];
    }
}

这个回溯思考 sum > tar 时，pos++ 不应该写在第 3 行，这样导致回溯减掉的元素值与递归增加的不一样。而应该放在第 4 行 for()中，只有当纵向回溯完结时 (也就是很多个 sum+=can[i] 导致 return 后)，横向遍历才会往右挪动；回溯第 n 个 can[i] 回溯第 n - 1 个 can[i];

剪枝

一次回溯只能对消一层递归；每次 return 只是从曾经增加进 sum 的泛滥 can[i]中减掉一个

举个栗子：

sum+= n 个 can[i]，回溯一次还剩 n - 1 个 can[i]; 这时要 i ++ 了；然而剩下的 sum 和这个 i ++ 后的新 can[i]加起来可能也会超过 tar，这步操作能够剪枝，防止进入新 can[i]的递归；

for (int i = pos; i < candidates.size() && sum + candidates[i] <= target; i++)

代码

class Solution {List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates); // 先进行排序
        backtracking(candidates, target, 0, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target, int sum, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {// 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i);
            path.removeLast(); // 回溯，移除门路 path 最初一个元素}
    }
}

LeetCode 40. 组合总和 II

剖析

在原有根底上设限每个数字在每个组合中只能应用 一次 且不蕴含反复的组合

Arrays 升序；纵向遍历时就要 i ++；Set 去重

Set 去重超时了！！！ 要在增加汇合的时候就判断是否反复，取 res 中最初一个 path 和以后满足条件的 path 比拟 也不行

纵向递归不须要去重，横向递归时采纳去重

代码

class Solution {List<List<Integer>> res = new LinkedList();
    LinkedList<Integer> path = new LinkedList();
    int sum = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates); // 先进行排序
        backtracking(candidates, target, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {res.add(new LinkedList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length && sum + candidates[i] <= target; i++) {
            // 要对横向遍历时应用过的元素进行跳过 因为一样的元素在深度递归时曾经把蕴含此元素的所有可能后果全副枚举过了
            if (i > idx && candidates[i] == candidates[i - 1]) {continue;}
            path.add(candidates[i]);
            sum += candidates[i];
            //System.out.println("sum="+sum);
            //i++;
            backtracking(candidates, target, i+1);
            //i--;
            //sum -= candidates[i];
            sum-=path.getLast();
            path.removeLast(); // 回溯，移除门路 path 最初一个元素}
    }
}

LeetCode 131. 宰割回文串

剖析

切割子串，保障 <u> 每个子串都是 回文串</u>

找到所有的子串组合，判断子串是否是回文串，依据 索引 切割 startIndex endIndex if(start-end) is ; res.add

代码

class Solution {List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {backTracking(s, 0);
        return res;
    }

    private void backTracking(String s, int startIndex) {
        // 如果起始地位大于 s 的大小，阐明找到了一组宰割计划
        if (startIndex >= s.length()) {res.add(new ArrayList(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            // 如果是回文子串，则记录
            if (isPalindrome(s, startIndex, i)) {String str = s.substring(startIndex, i + 1);
                path.add(str);
            } else {continue;}
            // 起始地位后移，保障不反复
            backTracking(s, i + 1);
            // 肯定要有回溯 开始下一种宰割
            path.removeLast();}
    }
    // 判断是否是回文串
    private boolean isPalindrome(String s, int startIndex, int end) {for (int i = startIndex, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) {return false;}
        }
        return true;
    }
}

总结

  1. 题目给定的数据集如果应用数组的形式，要判断是否有序，没有阐明有序最好视情排序
  2. 回溯横向挪动的机会肯定是某个纵向递归完结
  3. 看清题目要求，将串的所有子串都宰割成回文子串
  4. 横向遍历逻辑 纵向递归 startIndex++ 逻辑 回溯逻辑
退出移动版