LeetCode:回溯算法

2021-03-03 01:28

阅读:458

标签:transform   else   uniq   ali   can   star   lin   解答   解法   

回溯算法

这部分主要是学习了 labuladong 公众号中对于回溯算法的讲解

刷了些 leetcode 题,在此做一些记录,不然没几天就忘光光了

总结

概述

回溯是 DFS 中的一种技巧。回溯法采用 试错 的思想,尝试分步的去解决一个问题,在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案

通俗上讲,回溯是一种走不通就回头的算法。

摘录自:https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/backtrack

在进行回溯时,需要考虑3个问题

  1. 路径:也就是已经做出的选择。
  2. 选择列表:也就是你当前可以做的选择。
  3. 结束条件:也就是到达决策树底层,无法再做选择的条件。

算法框架如下:

List> res = new LinkedList();
// List<...> res = new LinkedList();

void backtrack(路径, 选择列表){
	if(满足结束条件){
        res.add(路径);
        return;
    }

    for(选择 :选择列表){
        // 做选择
        backtrack(路径, 选择列表)
        // 撤销选择
    }
}

特殊说明

在撤销选择时,若是如下定义:List> res = new LinkedList();List类若要移除最后一个元素:

  • 方式1:track.remove(track.size() - 1);,推荐,因为选择列表出现重复的元素时,方式2就会有问题!
  • 方式2:track.remove(Integer.valueOf(nums[i]));,直接remove(i)是不对的,因为 i 为 index 而不是添加的元素

经典问题

全排列问题

问题描述:有n个不重复的数,能排列出多少种n位数的可能,其中用过的数字是不能再用的

List> res = new LinkedList();

/* 主函数,输入一组不重复的数字,返回它们的全排列 */
List> permute(int[] nums) {
    // 记录「路径」
    LinkedList track = new LinkedList();
    // 输入:选择列表, 路径
    backtrack(nums, track);
    return res;
}

// 路径:记录在 track 中
// 选择列表:nums 中不存在于 track 的那些元素
// 结束条件:nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }

    for (int i = 0; i 
public static void main(String[] args) {
 int[] nums = {1,2,3};
 Demo demo = new Demo();
 demo.permute(nums);

 System.out.println(demo.res.toString());
 // [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
}

八皇后问题

题目描述:51. N 皇后

输入:4

输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

List> res = new LinkedList();

/* 输入棋盘边长 n,返回所有合法的放置 */
public List> solveNQueens(int n) {
    // ‘.‘ 表示空,‘Q‘ 表示皇后,初始化空棋盘。
    List board = new LinkedList();
	
    // 初始化路径
    for(int i=0; i board, int row){
    // 触发结束条件
    if(board.size() == row){
        res.add(transform(board));
        return;
    }
	
    // 第 row 行的所有列都是放置皇后的选择
    int n = board.get(row).length;
    for(int col=0; col board, int row, int col) {
    int n = board.size();

    // 遍历所有行,固定列:检查列是否有皇后互相冲突
    for(int i = 0; i = 0 && j = 0 && j >= 0; i--, j--){
        if(board.get(i)[j] == ‘Q‘){
            return false;
        }
    }
    return true;
}


private List transform(List board){
    List newBoard = new LinkedList();
    for(char[] row : board){
        newBoard.add(new String(row));
    }
    return newBoard;
}

子集问题

题目描述:78. 子集

// 数学归纳思想
public List> subsets(int[] nums) {
    List> res = new LinkedList();
    // 先加入[]的情况
    res.add(new LinkedList());

    for(int i=0; i sub = new LinkedList(res.get(j));
            sub.add(nums[i]);
            res.add(sub);
        }
    }
    return res;
}

// 回溯解法
List> res = new LinkedList();

public List> subsets(int[] nums) {

    List track = new LinkedList();;
    backtrack(nums, 0, track);

    return res;
}

private void backtrack(int[] nums, int start, List track){
    res.add(new LinkedList(track));
    // 这里的i=start做了可选集和的限定
    for(int i=start; i

组合问题

题目描述:77. 组合

List> res = new LinkedList();
public List> combine(int n, int k) {

    List track = new LinkedList();
	// k限定了尺寸,start限定了选择列表
    backtrack(n, k, 1, track);

    return res;
}

private void backtrack(int n, int k, int start, List track){
    
    // 剪枝:可有可无,加上后效率提升很多
    if(track.size() + n-start + 1 

排列问题

问题描述:46. 全排列,和之前的全排列一样,再贴一个代码吧

List> res = new LinkedList();

public List> permute(int[] nums) {

    List track = new LinkedList();
    backtrack(nums, track);
    return res;
}

private void backtrack(int[] nums, List track){
    if(nums.length == track.size()){
        res.add(new LinkedList(track));
        return;
    }

    for(int i=0; i

数独问题

问题描述:37. 解数独

public void solveSudoku(char[][] board) {

    backtrack(board, 0, 0);
}

private boolean backtrack(char[][] board, int r, int c){

    int m=9, n=9;

    if(c == n){
        // 穷举到最后一列的话就换到下一行重新开始
        return backtrack(board, r+1, 0);
    }

    if(r == m){
        // 找到一个可行解,触发 base case
        return true;
    }

    // 对棋盘的每个位置进行穷举
    for(int i=r; i

括号生成

题目描述:22. 括号生成

List res = new LinkedList();
public List generateParenthesis(int n) {

    if(n == 0){
        return res;
    }

    // 回溯过程中的路径
    char[] track = new char[n*2];
    Arrays.fill(track, ‘.‘);
    backtrack(n, n, 0, track);

    return res;

}

// 可用的左括号数量为 left 个,可用的右括号数量为 rgiht 个,已经放的个数index
private void backtrack(int left, int right, int index, char[] track){

    // 若左括号剩下的多,说明不合法
    if(left > right){
        return;
    }
    // 数量小于 0 肯定是不合法的
    if(left 

回溯算法VS动态规划

题目描述:494. 目标和

// 回溯算法:
int res = 0;
public int findTargetSumWays(int[] nums, int S) {

    backbarck(nums, S, 0, 0);
    return res;
}

private void backbarck(int[] nums, int target, int start, int sum){

    if(start == nums.length){
        if(sum == target){
            res+=1;
        }
        return;
    }

    sum += nums[start];
    backbarck(nums, target, start+1, sum);
    sum -= nums[start];

    sum -= nums[start];
    backbarck(nums, target, start+1, sum);
    sum += nums[start];
}


// 存在子问题:加备忘录的优化
// + + +/- +/- +/-  和  + - +/- +/- +/- 后面的计算就是重复的
Map cache = new HashMap();
public int findTargetSumWays(int[] nums, int S) {
    
    return dp(nums, S, 0, 0);
}

private int dp(int[] nums, int target, int start, int sum){

    if(start == nums.length){
        if(sum == target){
            return 1;
        }
        return 0;
    }

    // 把它俩转成字符串才能作为哈希表的键
    // 即:前面的计算相同,只有后面不同,前面的就不用再算一遍了
    String key = start + "," + sum;

    // 避免重复计算
    if (cache.containsKey(key)) {
        return cache.get(key);
    }

    // 还是穷举
    int res = dp(nums, target, start+1, sum+nums[start]) + dp(nums, target, start+1, sum-nums[start]);
    cache.put(key, res);

    return res;
}

// 动态规划:把 nums 划分成两个子集A和B,分别代表分配+的数和分配-的数
// sum(A) - sum(B) = target
// sum(A) = target + sum(B)
// sum(A) + sum(A) = target + sum(B) + sum(A)
// 2 * sum(A) = target + sum(nums)
// sum(A) = (target + sum(nums)) / 2
// 把原问题转化成:nums中存在几个子集A,使得A中元素的和为 (target + sum(nums)) / 2
// 这不就是背包问题了嘛
public int findTargetSumWays(int[] nums, int S) {

    int n = nums.length;
    int sum = 0;

    for(int i=0; i j){
                // 东西放不进背包,继承之前的状态
                dp[i][j] = dp[i-1][j];
            }else{
                // 能放进去的情况
                dp[i][j] = dp[i-1][j-nums[i-1]] + dp[i-1][j];
            }
        }  
    }

    return dp[n][sum];
}

题目

索引

39. 组合总和

40. 组合总和 II

216. 组合总和 III

47. 全排列 II

90. 子集 II

131. 分割回文串

解题

39. 组合总和

List> res = new LinkedList();
public List> combinationSum(int[] candidates, int target) {

    List track = new LinkedList();
    Arrays.sort(candidates);
    backtrack(candidates, target, 0, 0, track);

    return res;
}

// param1:可选的数组
// param2: 目标值
// param3: 当前的总和
// param4: 开始的索引,为了避免重复的组合出现多次
// param5:路径
private void backtrack(int[] candidates, int target, int sum, int start, List track){

    if(sum >= target){
        if(sum == target){
            res.add(new LinkedList(track));
        }
        return;
    }

    // 剪枝:可有可无,有了效率高
    if(sum+candidates[start] > target){
        return;
    }

    for(int i=start; i

40. 组合总和 II

// 耗时 917ms
List> res = new LinkedList();
// 用于去重,虽然效率很低,但能实现去重的效果
Set visited = new HashSet();
public List> combinationSum2(int[] candidates, int target) {

    List track = new LinkedList();

    Arrays.sort(candidates);

    backtrack(candidates, target, 0, 0, track);

    return res;
}

private void backtrack(int[] candidates, int target, int sum, int start, List track){

    if(sum >= target){
        if(sum == target && !visited.contains(track.toString())){
            res.add(new LinkedList(track));
            visited.add(track.toString());
        }
        return;
    }

    for(int i=start; i> res = new LinkedList();
boolean[] visited;
public List> combinationSum2(int[] candidates, int target) {

    List track = new LinkedList();
    visited = new boolean[candidates.length];

    Arrays.sort(candidates);
    backtrack(candidates, target, 0, 0, track);

    return res;
}

private void backtrack(int[] candidates, int target, int sum, int start, List track){

    if(sum >= target){
        if(sum == target){
            res.add(new LinkedList(track));
        }
        return;
    }

    // 剪枝1:
    if(start target){
        return;
    }

    for(int i=start; i 0 && candidates[i] == candidates[i - 1] && !visited[i - 1])) {
            continue;
        }

        sum += candidates[i];
        track.add(candidates[i]);
        visited[i] = true;
        backtrack(candidates, target, sum, i+1, track);
        sum -= candidates[i];
        track.remove(Integer.valueOf(candidates[i]));
        visited[i] = false;
    }
}

216. 组合总和 III

List> res = new LinkedList();

public List> combinationSum3(int k, int n) {

    List track = new LinkedList();

    backtrack(k, n, 1, 0, track);

    return res;
}

private void backtrack(int k, int n, int start, int sum, List track){

    if(track.size() == k && sum == n){
        res.add(new LinkedList(track));
        return;
    }
    
    // 剪枝: 可有可无,有了提高效率
    if(start>9 || sum > n || sum+start > n){
        return;
    }

    for(int i=start; i

47. 全排列 II

// 方法1:有误 但是我找不出来问题,[2,2,1,1] 少了一个可能的情况
// 通过visited记录出现的排列情况  
// 通过indexs记录已经递归下去的index,下次这个index不能再用了
List> res = new LinkedList();
Set visited = new HashSet();
boolean[] indexs;
public List> permuteUnique(int[] nums) {

    Arrays.sort(nums);
    indexs = new boolean[nums.length];

    List track = new LinkedList();
    backtrack(nums, track);

    return res;
}

private void backtrack(int[] nums, List track){

    if(track.size() == nums.length && !visited.contains(track.toString())){
        res.add(new LinkedList(track));
        visited.add(track.toString());
        return;
    }

    for(int i=0; i> res = new LinkedList();
Set visited = new HashSet();  // 记录已经出现过的情况
public List> permuteUnique(int[] nums) {

    List track = new LinkedList();

    // 建立新数组,其值对应原数组的索引
    int[] new_nums = new int[nums.length];
    for(int i=0; i track){

    if(track.size() == nums.length){
     
        List tmp = new LinkedList();
        // 根据索引回到原数组
        for(int index: track){
            tmp.add(nums[index]);
        }
        // 判断是否已经出现过这种情况
        if(!visited.contains(tmp.toString())){
            res.add(tmp);
            visited.add(tmp.toString());
        }
        return;
    }

    for(int i=0; i 99%
boolean[] visited;
public List> permuteUnique(int[] nums) {
    List> res = new ArrayList>();
    List track = new ArrayList();
    visited = new boolean[nums.length];

    Arrays.sort(nums);
    backtrack(nums, res, 0, track);

    return res;
}

private void backtrack(int[] nums, List> ans, int idx, List track) {
    if (idx == nums.length) {
        ans.add(new ArrayList(track));
        return;
    }
    for (int i = 0; i  0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
            continue;
        }
        track.add(nums[i]);
        visited[i] = true;
        backtrack(nums, ans, idx + 1, track);
        visited[i] = false;
        track.remove(idx);
    }
}

90. 子集 II

// 回溯解法:正常的模版解题
List> res = new LinkedList();
Set visited = new HashSet();

public List> subsetsWithDup(int[] nums) {

    List track = new LinkedList();
    // 因为集和具有无序性,因此需要排序来排除顺序造成的重复子集
    // 即:两个子集如果只是元素的排列顺序不一样,则认为重复
    Arrays.sort(nums);
    backtrack(nums, 0, track);

    return res;
}

private void backtrack(int[] nums, int start, List track){

    if(!visited.contains(track.toString())){
        visited.add(track.toString());
        res.add(new LinkedList(track));
    }else{
        return;
    }

    for(int i=start; i> res = new LinkedList();
boolean[] visited;

public List> subsetsWithDup(int[] nums) {

    visited = new boolean[nums.length];
    List track = new LinkedList();
    // 因为集和具有无序性,因此需要排序来排除顺序造成的重复子集
    // 即:两个子集如果只是元素的排列顺序不一样,则认为重复
    Arrays.sort(nums);
    backtrack(nums, 0, track);

    return res;
}

private void backtrack(int[] nums, int start, List track){

    res.add(new LinkedList(track));

    for(int i=start; i 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
            continue;
        }

        // 做选择
        track.add(nums[i]);
        visited[i] = true;
        // 回溯
        backtrack(nums, i+1, track);
        // 撤销选择
        track.remove(track.size() - 1);
        visited[i] = false;
    }
}

131. 分割回文串

List> res = new LinkedList();

public List> partition(String s) {
    List track = new LinkedList();

    backtrack(s, 0, track);

    return res;
}

private void backtrack(String s, int start, List track){
    if(start == s.length()){
        res.add(new LinkedList(track));
        return;
    }

    for(int i=start; i

LeetCode:回溯算法

标签:transform   else   uniq   ali   can   star   lin   解答   解法   

原文地址:https://www.cnblogs.com/zhuchengchao/p/14399164.html


评论


亲,登录后才可以留言!