十五周算法训练营——回溯算法

十五周算法训练营——回溯算法

今天是十五周算法训练营的第十周,主要讲回溯算法专题。

解决一个回溯问题,实际上就是一个决策树的遍历过程,只需要思考三个问题:

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

全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。

function permute(nums) {
    const result = [];

    /**
     * 路径:记录到track中
     * 选择列表:不存在与nums中的哪些数
     * 结束条件:当nums中的元素全部在track中出现
     */
    const backtrack = (track, nums) => {
        // 结束条件
        if (track.length === nums.length) {
            result.push([...track]);
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (track.includes(nums[i])) {
                continue;
            }

            // 做选择
            track.push(nums[i]);
            // 进入下一层
            backtrack(track, nums);
            // 取消选择
            track.pop();
        }
    };

    const track = [];

    backtrack(track, nums);

    return result;
}

const nums = [1, 2, 3];
console.log(permute(nums));

全排列II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例 1:

输入:nums = [1,1,2] 输出: [[1,1,2], [1,2,1], [2,1,1]]。

function permuteUnique(nums) {
    const result = [];

    /**
     * 路径:记录到track中
     * 选择列表:当前没有被访问过,且前一个值若为相通知,且被访问过
     * 结束条件:全部值都被访问了一遍
     */
    const backtrack = (sortNums, track, visits) => {
        if (track.length === sortNums.length) {
            result.push([...track]);
            return;
        }

        for (let i = 0; i < sortNums.length; i++) {
            // i > 0 && nums[i] === nums[i - 1] && !visits[i - 1]
            // 上述一行的判断是当前值和前一个值相等,但是前一个值没有被访问过,表示前一个值不在该值路径的上几层,表示在同一层前面出现过,所以该值要跳过
            if (visits[i] || (i > 0 && sortNums[i] === sortNums[i - 1] && !visits[i - 1])) {
                continue;
            }

            // 做选择
            track.push(sortNums[i]);
            visits[i] = 1;

            // 选择下一层
            backtrack(sortNums, track, visits);

            // 取消选择
            track.pop();
            visits[i] = 0;
        }
    };

    const track = [];

    nums.sort((a, b) => a - b);

    const visits = (new Array(nums.length)).fill(0);

    backtrack(nums, track, visits);

    return result;
}

const nums = [1, 1, 2];
console.log(permuteUnique(nums));

N皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1:

十五周算法训练营——回溯算法

输入:n = 4 输出:[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]] 解释:如上图所示,4 皇后问题存在两个不同的解法。

// 该问题本质上和全排列问题差不多,决策树上的每一层表示棋盘上的每一行,每个节点可以做出的选择是在该行的任意一列放置一个皇后
function solveNQueens(n) {
    const result = [];

    // 判断是否可以在[row, col]放置皇后
    const isValid = (board, row, col) => {
        // 判断该列是否存在皇后
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') {
                return false;
            }
        }

        // 判断左上方是否存在皇后冲突
        let leftRow = row - 1;
        let leftCol = col - 1;
        while (leftRow >= 0 && leftCol >= 0) {
            if (board[leftRow][leftCol] === 'Q') {
                return false;
            }
            leftRow--;
            leftCol--;
        }

        // 判断右上是否存在皇后冲突
        let rightRow = row - 1;
        let rightCol = col + 1;
        while (rightRow >= 0 && rightCol < n) {
            if (board[rightRow][rightCol] === 'Q') {
                return false;
            }
            rightRow--;
            rightCol++;
        }

        return true;
    };
    /**
     * 路径:board中小于row的那些行都已经成功放置了皇后
     * 选择列表:第row行的所有列都是放置皇后的选择
     * 结束条件:row超过board的最后一行
     */

    const backtrack = (board, row) => {
        // 触发结束条件
        if (row === board.length) {
            result.push(board.map(item => {
                return item.join('');
            }));
            return;
        }

        for (let col = 0; col < n; col++) {
            // 排除不合法的选择
            if (!isValid(board, row, col)) {
                continue;
            }

            // 做选择
            board[row][col] = 'Q';

            // 进行下一层
            backtrack(board, row + 1);

            // 取消选择
            board[row][col] = '.';
        }
    };

    const board = new Array(n);
    for (let i = 0; i < n; i++) {
        board[i] = (new Array(n)).fill('.');
    }

    backtrack(board, 0);

    return result;
}

const n = 4;
console.log(solveNQueens(n));

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:

输入:candidates = [2,3,6,7], target = 7 输出:[[2,2,3],[7]] 解释: 2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选, 7 = 7 。 仅有这两种组合。

function combinationSum(candidates, target) {
    const result = [];

    /**
     * 路径:记录在track中
     * 选择列表:index及其之后的元素
     * 结束条件:其和为target,则进行存储,超过,则不存储结束
     */
    const backtrack = (sortNums, track, trackNum, index) => {
        if (trackNum === target) {
            result.push([...track]);
            return;
        } else if (trackNum > target) {
            return;
        }

        for (let i = index; i < sortNums.length; i++) {
            // 做选择
            track.push(sortNums[i]);
            trackNum += sortNums[i];

            // 进入下一层
            backtrack(sortNums, track, trackNum, i);

            // 取消选择
            track.pop();
            trackNum -= sortNums[i];
        }
    };

    const track = [];
    let trackNum = 0;

    candidates.sort((a, b) => a - b);

    backtrack(candidates, track, trackNum, 0);

    return result;
}

const candidates = [2,3,6,7];
const target = 7;
console.log(combinationSum(candidates, target));

子集II

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

示例 1:

输入:nums = [1,2,2] 输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]。

function subsetsWithDup(nums) {
    const result = [];

    /**
     * 路径:记录在track中
     * 选择列表:index及其之后的元素
     * 结束条件:将结果进行存储
     */
    const backtrack = (sortNums, track = [], index = 0) => {
        result.push([...track]);

        for (let i = index; i < sortNums.length; i++) {
            // 对于排序后相同的元素应该跳过
            if (i > index && sortNums[i] === sortNums[i - 1]) {
                continue;
            }
            // 做选择
            track.push(sortNums[i]);
            // 进入下一层
            backtrack(sortNums, track, i + 1);
            // 取消选择
            track.pop();
        }
    };

    const track = [];
    nums.sort((a, b) => a - b);
    backtrack(nums, track, 0);

    return result;
}

const nums = [1, 2, 2];
console.log(subsetsWithDup(nums));

递增子序列

给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。

示例 1:

输入:nums = [4,6,7,7] 输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]。

function findSubsequences(nums) {
    const result = [];

    const backtrack = (track, start) => {
        // 如果其长度大于等于2,则算一个子序列
        if (track.length >= 2) {
            result.push([...track]);
        }

        const map = new Map();
        for (let i = start; i < nums.length; i++) {
            // 判断是否合法
            // 同一层只能用一次
            if (map.has(nums[i])) {
                continue;
            }
            // 后一层比前一层大
            if (nums[i] < track[track.length - 1]) {
                continue;
            }
            map.set(nums[i], true);
            // 做选择
            track.push(nums[i]);
            // 进入下一层
            backtrack(track, i + 1);
            // 取消选择
            track.pop();
        }
    };

    const track = [];
    backtrack(track, 0);

    return result;
}

const nums = [1, 2, 3 ,1,1,1,1];
console.log(findSubsequences(nums));

文章版权声明

 1 原创文章作者:8294,如若转载,请注明出处: https://www.52hwl.com/30058.html

 2 温馨提示:软件侵权请联系469472785#qq.com(三天内删除相关链接)资源失效请留言反馈

 3 下载提示:如遇蓝奏云无法访问,请修改lanzous(把s修改成x)

 免责声明:本站为个人博客,所有软件信息均来自网络 修改版软件,加群广告提示为修改者自留,非本站信息,注意鉴别

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年7月14日 上午12:00
下一篇 2023年7月15日