代码随想录算法训练营第27天

今日任务

● 39. 组合总和 ● 40.组合总和II ● 131.分割回文串

链接：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY (opens in a new tab)

39. 组合总和

自己想法+题解想法

注：本题题目说明集合没有重复元素，但是可以重复使用

题解：可以先排序，再利用有序性进行剪枝

class Solution {
    public LinkedList<Integer> path = new LinkedList<>();
    public int now_sum = 0;
    public List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // 先进行排序
        backtrack(candidates, target, 0, candidates.length - 1);
        return ans;
    }
    public void backtrack(int[] candidates, int target, int start, int end) {
        if(now_sum == target) ans.add(new ArrayList(path));
        else if(now_sum > target) return;
        else {
            for(int i = start; i <= end; i++) {
                path.add(candidates[i]);
                now_sum += candidates[i];
                if(now_sum > target) { // 剪枝
                    path.removeLast();
                    now_sum -= candidates[i];
                    break;
                }
                backtrack(candidates, target, i, end); // i不变，因为可以重复使用
                path.removeLast();
                now_sum -= candidates[i];
            }
        }
    }
}

40.组合总和II

自己想法

注：本题集合中的元素有重复，并且每个元素只能使用一次，并且最后的结果集合中不能有重复的组合

题解：那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

自己：因此，去重应该放在for末尾，而不是backtrack前面

class Solution {
    public LinkedList<Integer> path = new LinkedList<>();
    public int now_sum = 0;
    public List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 先进行排序
        backtrack(candidates, target, 0, candidates.length - 1);
        return ans;
    }
    public void backtrack(int[] candidates, int target, int start, int end) {
        if(now_sum == target) ans.add(new ArrayList(path));
        else if(now_sum > target) return;
        else {
            for(int i = start; i <= end; i++) {
                path.add(candidates[i]);
                now_sum += candidates[i];
                if(now_sum > target) { // 剪枝
                    path.removeLast();
                    now_sum -= candidates[i];
                    break;
                }
                backtrack(candidates, target, i + 1, end);
                path.removeLast();
                now_sum -= candidates[i];                
                while((i + 1) <= end && candidates[i] == candidates[i + 1]) { // 去重
                    i++;
                    // System.out.println("skip: " + i);
                }
            }
        }
    }
}

131.分割回文串

自己想法+题解想法

切割问题可以抽象为组合问题
如何模拟那些切割线
切割问题中递归如何终止
可选优化：使用动态规划，高效地事先一次性计算出任意字串是不是回文串

class Solution {
    public List<List<String>> ans = new ArrayList<>();
    public List<String> tmp = new ArrayList<>();
    boolean[][] dp;
    public List<List<String>> partition(String s) {
        palindromeCheck2(s);
        backtrack(s, 0, s.length());
        return ans;
    }
    // [start, end)
    public void backtrack(String s, int start, int end) {
        // 不能再切的时候得到一个答案
        if(start == end) ans.add(new ArrayList<String>(tmp));
        else {
            for(int i = start; i < end; i++) {
                // for的i决定字串在哪里切第一刀
                String front = s.substring(start, i + 1);
                if(dp[start][i]) {
                // if(palindromeCheck(front)) {
                    tmp.add(front);
                    // 递归回溯决定切完第一刀后的字串继续怎么切
                    backtrack(s, i + 1, end);
                    tmp.remove(tmp.size() - 1);
                }
            }
        }
    }
    // 直接判断传入的字串是否回文
    public boolean palindromeCheck(String s) {
        for(int i = 0; i < s.length() / 2; i++) {
            if(s.charAt(i) != s.charAt(s.length() - i - 1)) return false;
        }
        return true;
    }
    // 动态规划判断“任意字串is回文串？”
    public void palindromeCheck2(String s) {
        int n = s.length();
        dp = new boolean[n][n];
        for(int i = 0; i < n; i++) dp[i][i] = true;
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i + 1; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(j - i == 1) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                }
            }
        }
    }
}