[数据结构与算法]电信保温杯笔记——代码随想录 刷题攻略 回溯算法

代码随想录 刷题攻略 笔记

电信保温杯笔记——代码随想录 刷题攻略
电信保温杯笔记——代码随想录 刷题攻略 笔记

1.关于回溯算法，你该了解这些！

讲义地址

2.回溯算法：组合问题

讲义地址

第77题. 组合

leetcode地址

public class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k){
        combineHelper(n, k, 1);
        return result;
    }

    public void combineHelper(int n, int k, int startIndex){
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            combineHelper(n, k, i+1);
            path.removeLast();
        }
    }
}

3.回溯算法：组合问题再剪剪枝

讲义地址

4.回溯算法：求组合总和！

讲义地址

216.组合总和III

leetcode地址

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        combineHelper(k, n, 1, 0);
        return res;
    }

    public void combineHelper(int k, int n, int startNum, int sum){
        if (sum > n){
            return;
        }
        if (path.size() == k){
            if (sum == n){
                res.add(new ArrayList<>(path));
                return;
            }
        }
        for (int i = startNum; i <= 9 - (k - path.size()) + 1; i++){
            path.add(i);
            combineHelper(k, n, i + 1, sum + i);
            path.removeLast();
        }
    }

}

5.回溯算法：电话号码的字母组合

讲义地址

17.电话号码的字母组合

leetcode地址

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

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0){
            return res;
        }
        String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        combineHelper(digits, map, 0);

        return res;
    }
    public void combineHelper(String digits, String[] map, int startNum){
        if (path.length() == digits.length()){
            res.add(path.toString());
            return;
        }
        int temp = digits.charAt(startNum) - '0';
        String str = map[temp];
        for(int i = 0; i < str.length(); i++){
            path.append(str.charAt(i));
            combineHelper(digits, map, startNum + 1);
            path.deleteCharAt(path.length() -1);
        }
    }
}

6.本周小结！（回溯算法系列一）

讲义地址

小结

核心代码

class Solution {
    List<String> res = new ArrayList<>(); // 保存结果
    StringBuilder path = new StringBuilder(); //保存满足条件的项

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0){
            res.add(path.toString());
            return res;
        }
        String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        combineHelper(digits, map, 0);

        return res;
    }
    // 递归函数变量：项的最终长度，项取值的集合，项的当前长度
    public void combineHelper(String digits, String[] map, int startNum){
        if (path.length() == digits.length()){ // 保存满足条件的项
            res.add(path.toString());
            return;
        }
        int temp = digits.charAt(startNum) - '0';
        String str = map[temp];
        for(int i = 0; i < str.length(); i++){ // 项某个位置遍历取值
            path.append(str.charAt(i)); //项长度增加
            combineHelper(digits, map, startNum + 1);
            path.deleteCharAt(path.length() -1); //项长度减小
        }
    }
}

7.回溯算法：求组合总和（二）

讲义地址

39. 组合总和

leetcode地址

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0){
            return res;
        }
        Arrays.sort(candidates);
        combineHelper(candidates, target, 0, 0);
        return res;
    }

    public void combineHelper(int[] candidates, int target, int sum, int idx){
		// #
        if (sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++){
            if (sum + candidates[i]> target){
                return; // 这里可以return，可以break，因为candidates是经过排序的，所以没有关系，这个判断也可以写在#号的位置，但那样就多了path的add和removeLast的步骤，效率变低
            }
            path.add(candidates[i]);
            combineHelper(candidates, target, sum + candidates[i], i); // 这个i是与前门题目的区别
            path.removeLast();
        }
    }
}

8.回溯算法：求组合总和（三）

讲义地址

40.组合总和II

leetcode地址

class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        //加标志数组，用来辅助判断同层节点是否已经遍历
        boolean[] flag = new boolean[candidates.length];
        backTracking(candidates, target, 0, 0, flag);
        return lists;
    }

    public void backTracking(int[] candidates, int target, int sum, int index, boolean[] flag) {
        if (sum == target) {
            lists.add(new ArrayList(path));
            return;
        }

        for (int i = index; i < candidates.length; i++) { // i 是从0开始还是index开始，决定了它是否是组合
            if (sum + candidates[i] > target){
                return;
            }
            //出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && !flag[i - 1]) {
                continue;
            }
            flag[i] = true;
            path.add(candidates[i]);
            //每个节点仅能选择一次，所以从下一位开始
            backTracking(candidates, target, sum + candidates[i], i + 1, flag);
            path.removeLast();
            flag[i] = false;
        }
    }
}

9.回溯算法：分割回文串

讲义地址

131.分割回文串

leetcode地址

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;
    }

    public void backTracking (String s, int idx){
        if (idx >= s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = idx; i < s.length(); i++){
            if (!isPalindrome(s, idx, i)){
                continue;
            }
            String str = s.substring(idx, i + 1);
            path.add(str);
            backTracking(s, i + 1);
            path.removeLast();
        }
    }

    public boolean isPalindrome(String str, int left, int right){
        for (int i = left, j = right; i < j; i++, j--){
            if (str.charAt(i) != str.charAt(j)){
                return false;
            }
        }
        return true;
    }
}

10.回溯算法：复原IP地址

讲义地址

93.复原IP地址

leetcode地址

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

    public List<String> restoreIpAddresses(String s) {
        restoreIpAddressesHelper(s, 0, 0);
        return res;
    }

    public void restoreIpAddressesHelper(String s, int start, int number) {
        if (start == s.length() && number == 4) {
            res.add(path.toString());
            return;
        }
        if (start == s.length() || number > 4){
            return;
        }
        for (int i = start; i < start + 3 && i < s.length(); i++){
            if (i - start > 0 && s.charAt(start) == '0'){
                continue;
            }
            int temp  = Integer.parseInt(s.substring(start, i + 1));
            if (temp < 0 || temp > 255){
                continue;
            }
            path.append(s.substring(start, i + 1));
            if (number < 3) {
                path.append(".");
            }
            restoreIpAddressesHelper(s, i + 1, number + 1);
            path.delete(start + number, i + number + 2);
        }
    }
}

11.回溯算法：求子集问题！

讲义地址

78.子集

leetcode地址

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

    public List<List<Integer>> subsets(int[] nums) {
        res.add(new ArrayList<>());
        subsetsHelper(nums, 0);
        return res;
    }
    public void subsetsHelper(int[] nums, int startNum){
        if (startNum == nums.length){
            return;
        }
        for (int i = startNum; i < nums.length; i++){
            path.add(nums[i]);
            res.add(new ArrayList<>(path));
            subsetsHelper(nums, i + 1);
            path.removeLast();

        }
    }
}

12.本周小结！（回溯算法系列二）

讲义地址

13.回溯算法：求子集问题（二）

讲义地址

90.子集II

leetcode地址

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        boolean[] flag = new boolean[nums.length];
        res.add(new ArrayList<>());
        subsetsWithDupHelper(nums, 0, flag);
        return res;
    }
    public void subsetsWithDupHelper(int[] nums, int startNum, boolean[] flag){
        if (startNum == nums.length){
            return;
        }
        for (int i = startNum; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !flag[i-1]){
                continue;
            }
            flag[i] = true;
            path.add(nums[i]);
            res.add(new ArrayList<>(path));
            subsetsWithDupHelper(nums, i + 1, flag);
            path.removeLast();
            flag[i] = false;
        }
    }
}

14.回溯算法：递增子序列

讲义地址

491.递增子序列

leetcode地址

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        findSubsequencesHelper(nums, 0);
        return res;
    }

    public void findSubsequencesHelper(int[] nums, int startNum){
        if (path.size() > 1){
            res.add(new ArrayList<>(path));
        }
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = startNum; i < nums.length; i++){
            if (map.getOrDefault(nums[i], 0) > 0){
                // 已经用过
                continue;
            }
            if (path.size() > 0 && path.getLast() > nums[i]){
                // 不递增
                continue;
            }
            // 没用过
            map.put(nums[i], 1);

            path.add(nums[i]);
            findSubsequencesHelper(nums, i + 1);
            path.removeLast();
        }
    }
}

15.回溯算法：排列问题！

讲义地址

46.全排列

leetcode地址

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] flag = new boolean[nums.length];
        permuteHelper(nums, 0, flag);
        return res;
    }
    public void permuteHelper(int[] nums, int k, boolean[] flag){
        if (k == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (flag[i]){
                continue;
            }
            path.add(nums[i]);
            flag[i] = true;
            permuteHelper(nums, k + 1, flag);
            path.removeLast();
            flag[i] = false;
        }
    }
}

16.回溯算法：排列问题（二）

讲义地址

47.全排列 II

leetcode地址

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] flag = new boolean[nums.length];
        permuteUniqueHelper(nums, 0, flag);
        return res;
    }

    public void permuteUniqueHelper(int[] nums, int k, boolean[] flag){
        if (k == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !flag[i - 1]){
                continue;
            }
            if (!flag[i]){
                flag[i] = true;
                path.add(nums[i]);
                permuteUniqueHelper(nums, k + 1, flag);
                path.removeLast();
                flag[i] = false;
            }
        }
    }
}

17.本周小结！（回溯算法系列三）

讲义地址

18.回溯算法去重问题的另一种写法

讲义地址

19.回溯算法：重新安排行程

讲义地址

332.重新安排行程

[leetcode地址](

1

20.回溯算法：N皇后问题

讲义地址

第51题. N皇后

leetcode地址
左神视频有最高效的做法：位运算，一周刷爆LeetCode，算法da神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解 笔记

方式一：使用数组代替位运算

class Solution {
    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        if (n == 0){
            return res;
        }
        if (n == 1){
            path.add("Q");
            res.add(new ArrayList<>(path));
            return res;
        }
        int[] colLim = new int[n];
        int[] leftLim = new int[n];
        int[] rightLim = new int[n];
        Arrays.fill(colLim, 1);
        Arrays.fill(leftLim, 1);
        Arrays.fill(rightLim, 1);
        solveNQueensHelper(n, colLim, leftLim, rightLim);
        return res;
    }
    public void solveNQueensHelper(int n, int[] colLim, int[] leftLim, int[] rightLim){
        if (path.size() == n){
            res.add(new ArrayList<>(path));
            return;
        }
        int[] newLeftLim = getLeftLim(leftLim);
        int[] newRightLim = getRightLim(rightLim);
        int[] flag = getFlag(colLim, newLeftLim, newRightLim);
        for (int i = 0; i < n; i ++){
            if (flag[i] == 0){
                continue;
            }
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++){
                if (j == i){
                    sb.append('Q');
                }else{
                    sb.append('.');
                }
            }
            path.add(sb.toString());
            colLim[i] = 0;
            newLeftLim[i] = 0;
            newRightLim[i] = 0;
            solveNQueensHelper(n, colLim, newLeftLim, newRightLim);
            colLim[i] = 1;
            newLeftLim[i] = 1;
            newRightLim[i] = 1;
            path.removeLast();
        }
    }
    public int[] getLeftLim(int[] leftLim){
        int len = leftLim.length;
        int[] newLeftLim = new int[len];
        for (int i = 0; i < len - 1; i++){
            newLeftLim[i] = leftLim[i + 1];
        }
        newLeftLim[len - 1] = 1;
        return newLeftLim;
    }
    public int[] getRightLim(int[] rightLim){
        int len = rightLim.length;
        int[] newRightLim = new int[len];
        for (int i = len - 1; i > 0; i--){
            newRightLim[i] = rightLim[i - 1];
        }
        newRightLim[0] = 1;
        return newRightLim;
    }
    public int[] getFlag(int[] colLim, int[] leftLim, int[] rightLim){
        int len = colLim.length;
        int[] flag = new int[len];
        for (int i = 0; i < len; i++){
            flag[i] = colLim[i] * leftLim[i] * rightLim[i];
        }
        return flag;
    }
}

方式二

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

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }


    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            res.add(Array2List(chessboard));
            return;
        }

        for (int col = 0;col < n; ++col) {
            if (isValid (row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row+1, chessboard);
                chessboard[row][col] = '.';
            }
        }

    }


    public List Array2List(char[][] chessboard) {
        List<String> path = new ArrayList<>();

        for (char[] c : chessboard) {
            path.add(String.valueOf(c));
        }
        return path;
    }


    public boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i=0; i<row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

21.回溯算法：解数独

讲义地址

37. 解数独

leetcode地址

class Solution {
    boolean find = false;
    char[] set = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board, 0);
    }
    public void solveSudokuHelper(char[][] board, int num){
        if (num == 81){
            find = true;
            return;
        }

        int row = num / 9;
        int col = num % 9;

        if(board[row][col] == '.'){
            for (int i = 1; i < 10; i++){
                if (isValid(board, set[i], row, col)){
                    board[row][col] = set[i];
                    solveSudokuHelper(board, num + 1);
                    if (!find){
                        board[row][col] = '.';
                    }
                }else{
                    continue;
                }
            }
        }else{
            solveSudokuHelper(board, num + 1);
        }
    }

    public boolean isValid(char[][] board, char c, int row, int col){
        for (int i = 0; i < 9; i++){
            if (board[row][i] == c || board[i][col] == c){
                return false;
            }
        }
        int baseRow = (row / 3) * 3;
        int baseCol = (col / 3) * 3;
        for (int i = baseRow; i < baseRow + 3; i++){
            for (int j = baseCol; j < baseCol + 3; j++){
                if (board[i][j] == c){
                    return false;
                }
            }
        }
        return true;
    }
}

22.一篇总结带你彻底搞透回溯算法！

讲义地址