【算法练习】leetcode算法题合集之回溯篇

本文介绍: 【算法练习】leetcode算法题合集之回溯篇

组合问题

LeetCode39: 组合总和

目标和，除了累加所有的数外还可以用目标值减去所有的数。

添加第i个元素后，可以继续添加第i个元素。可以添加第i个元素，也可以添加索引为candidates.length-1的元素

这类回溯的问题可以想象成多叉数，对于根节点有左右子树，对于组合而言，多叉树的集合是candidates的所有的元素。以及考虑所有子元素的下一层的子元素集合是什么。

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

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, target, 0);
        return res;
    }

    private void backtrack(int[] candidates, int target, int idx) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
        }
        if (target < 0 || idx == candidates.length) {
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i );
            path.pollLast();
        }
    }
}

LeetCode40: 组合总和II

每个数字只能使用一次，并不意味着不允许重复元素。如果原数组中存在两个1，和是2，是可以有[1,1]的组合

进入下一次递归的时候，需要进行索引加1，当前元素不能再用。

i > idx && candidates[i] == candidates[i - 1]，目的是防止数组中有两个1，第一个1和第二个1在与其他元素搭配的时候作用是一样的，需要过滤。因此，数组必须是有序的，保证相等的元素相邻。

class Solution {

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

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, target, 0);
        return res;
    }

    private void backtrack(int[] candidates, int target, int idx) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
        }
        if (target < 0) {
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            if (i > idx && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1);
            path.pollLast();
        }
    }

}

LeetCode17. 电话号码的字母组合

当长度相等满足，则加入结果集

字符’2’转为数字2，digits.charAt(idx) - '0'

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return res;
        }
        dfs(digits, 0);
        return res;
    }

    private void dfs(String digits, int idx) {
        if (sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(idx) - '0'];

        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            dfs(digits, idx + 1);
            sb.deleteCharAt(sb.length() - 1);
        }

    }
}

子集问题

LeetCode78：子集

LeetCode78. 子集

startIndex == nums.length这个校验可有可无。

子集第一层子集合是[0,nums.length-1]，对于选择0的元素，下一层的子集合是[1,nums.length-1]

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

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int idx) {
        res.add(new ArrayList<>(path));
        
        if (startIndex == nums.length) {
            return;
        }
        for (int i = idx; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.pollLast();
        }
    }
}

LeetCode90：子集II

i > idx && nums[i] == nums[i - 1]可以理解为同一层元素不能重复。i==idx的时候，i是第一个元素。

需要对数组进行排序，排序好的数组元素相等的在一起。

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

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int idx) {
        res.add(new ArrayList<>(path));

        for (int i = idx; i < nums.length; i++) {
            if (i > idx && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.pollLast();
        }
    }
}

LeetCode491: 非递减子序列

子序列就是不能改变数组中的元素。

去重：使用boolean数组或者HashMap

递增的判断是获取path中最后一个元素和当前元素比较。

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

    public List<List<Integer>> findSubsequences(int[] nums) {
        
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int idx) {
        if (path.size() > 1) {
            res.add(new ArrayList<>(path));
        }
        if (idx == nums.length) {
            return;
        }
        boolean[] used = new boolean[201];
        for (int i = idx; i < nums.length; i++) {
            if (used[nums[i] + 100] || (!path.isEmpty() && path.peekLast() > nums[i])) {
                continue;
            }
            path.add(nums[i]);
            used[nums[i]+ 100] = true;
            dfs(nums, i + 1);
            path.pollLast();
        }
    }
}

全排列问题

LeetCode46. 全排列

第一层集合是[0,nums.length-1]，第二层集合是[0,nums.length-1]再减去第一层用的元素。

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];

        dfs(nums);
        return res;
    }

    private void dfs(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            dfs(nums);
            used[i] = false;
            path.removeLast();
        }
    }
}

LeetCode47: 全排列II

不能有重复的组合

i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]。连续三个1，第一层使用第一个1，第二层使用第二个1（used[i-1]==true）。等于是1(a),1(b),1(c)只能有一个顺序。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        dfs(nums);
        return result;
    }

    private void dfs(int[] nums) {
        if (nums.length == path.size()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1]) && !used[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            dfs(nums);
            used[i] = false;
            path.pollLast();
        }
    }
}

切割问题

LeetCode93: 复原IP地址（**）

LeetCode93: 复原IP地址

判断某字符串是否为合法字符串，大于等于0，小于等于255的字符串。

要切分为合理的4段，记录start为字符串的起始字符。当符合要求的时候，start == s.length() && split == 4

子树集合，[start,start + 2]，只有3个位置可选。

题目的难点，需要把应用题理解为可以做回溯的题目。

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

    public List<String> restoreIpAddresses(String s) {

        dfs(s, 0, 0);

        return res;
    }

    private void dfs(String s, int start, int split) {
        if (start == s.length() && split == 4) {
            res.add(String.join(".", path));
            return;
        }

        for (int i = start; i < start + 3; i++) {
            if (i >= s.length()) {
                break;
            }
            if ((4 - split) * 3 < s.length() - i) {
                continue;
            }
            if (isValid(s, start, i)) {
                path.add(s.substring(start, i + 1));
                dfs(s, i + 1, split + 1);
                path.removeLast();
            }

        }

    }

    private boolean isValid(String s, int start, int end) {
        if (start != end && s.charAt(start) == '0') {
            return false;
        }
        int res = 0;
        for (int i = start; i <= end; i++) {
            res = res * 10 + (s.charAt(i) - '0');
        }
        return res >= 0 && res <= 255;
    }
}

网格类问题

LeetCode200: 岛屿数量

回溯方法：计数，如果当前点为岛屿，将附近的土地置为0，避免重复计数。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int count = 0;
        int m = grid.length; //行的个数
        int n = grid[0].length; // 列的个数

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;

    }

    private void dfs(char[][] grid, int i, int j) {

        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}

LeetCode695: 岛屿的最大面积

class Solution {
    public int maxAreaOfIsland(int[][] grid) {

        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    ans = Math.max(ans, dfs(grid, i, j));
                }
            }

        }
        return ans;

    }

    private int dfs(int[][] grid, int i, int j) {
        int res = 1;
        if (i >= grid.length || i < 0 || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        res += dfs(grid, i - 1, j);
        res += dfs(grid, i + 1, j);
        res += dfs(grid, i, j - 1);
        res += dfs(grid, i, j + 1);
        return res;

    }
}

LeetCode79. 单词搜索

board[i][j] == '.'设置为该点位已经使用过。

比较索引为index的元素，判断是否相等，相等则继续，不等则返回结果false。比较前后左右的结果。当索引为最后一个元素，判断为相等，则返回结果。

class Solution {

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int index, int i, int j) {

        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || word.charAt(index) != board[i][j]
                || board[i][j] == '.') {
            return false;
        }
        if (index == word.length() - 1) {
            return true;
        }

        char tmp = board[i][j];
        board[i][j] = '.';

        boolean b = dfs(board, word, index + 1, i + 1, j)
                || dfs(board, word, index + 1, i - 1, j)
                || dfs(board, word, index + 1, i, j + 1)
                || dfs(board, word, index + 1, i, j - 1);

        board[i][j] = tmp;
        return b;
    }
}

LeetCode207. N皇后

51. N 皇后

定义一个n*n的数组，插入所有的网格 .。

校验新增的元素是否合理（竖向比较，45度比较，横向比较，135度比较）

将当前board保存到List<String>中，加入结果集

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

    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < board.length; i++) {
            Arrays.fill(board[i], '.');
        }

        dfs(board, 0, n);
        return res;
    }

    private void dfs(char[][] board, int index, int n) {
        if (index == n) {
            res.add(toArray(board));
            return;
        }
        for (int i = 0; i < board[index].length; i++) {
            if (isValid(board, index, i, n)) {
                board[index][i] = 'Q';
                dfs(board, index + 1, n);
                board[index][i] = '.';

            }

        }
    }

    private boolean isValid(char[][] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        for (int i = 0; i < col; i++) {
            if (board[row][i] == 'Q') {
                return false;
            }
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }

        }
        return true;

    }

    public List<String> toArray(char[][] board) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            list.add(new String(board[i]));
        }
        return list;
    }
}

括号问题

LeetCode22. 括号生成

这条题目我看到想过并且看答案已经不止3次了，每次看都像看新的题目一样，感觉很熟悉，就是不会做。

记录左括号的次数和右括号的次数，当左括号的次数和右括号的次数都等于n，满足条件。当左括号的次数小于右括号的次数，进行剪枝，比如())

class Solution {

    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {

        dfs(0, 0, n, "");
        return res;
    }

    private void dfs(int left, int right, int n, String s) {
        if (left == n && right == n) {
            res.add(s);
            return;
        }
        if (left < right) {
            return;
        }
        if (left < n) {
            dfs(left + 1, right, n, s + "(");
        }
        if (right < n) {
            dfs(left, right + 1, n, s + ")");
        }

    }
}

图问题

LeetCode207. 课程表

记录每个课程的先学课程数量，没有先学课程的加入队列。

记录边，边是[先学,后学]

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] prereq : prerequisites) {
            indegree[prereq[0]]++; // 入度,[1,2] 先学2再学1
            edges.get(prereq[1]).add(prereq[0]);

        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int poll = queue.poll();
            numCourses--;
            for (Integer pre : edges.get(poll)) {
                indegree[pre]--;
                if (indegree[pre] == 0) {
                    queue.add(pre);
                }

            }
        }
        return numCourses == 0;

    }
}