请老师帮忙看一下关于 N 皇后的一个问题

来源:11-1 结语

Osuribaba

2020-12-03

老师您好,我在做 leetcode 第 51 号 N 皇后 问题的时候,我的递归思路如下:

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const res = [];
    // 创建一个棋盘 初始值全是点儿
    const checkerBoard = new Array(n).fill(undefined).map(i => new Array(n).fill('.'));
    const _solveNQueens = (tmp, x, y, target, current) => {
        if (current > target) {
            // 如果当前下棋的数量已经超过 target 就直接 return
            return;
        } else if (current === target) {
            // 如果当前下的棋子数正好等于目标的 n 那就找到了一个结果
            res.push(tmp.map(i => i.join('')));
        } else {
            // 如果还没有下够 n 颗皇后

            for (let j = 0; j < y; j++) {
                // 第 0 到当前的行数 扫描第 x 列 如果某个棋盘有 Q 说明不能放这儿 直接 return
                if (tmp[j][x] === 'Q') return;
            }

            let _x = x, _y = y;
            while(true) {
                // 扫描当前坐标的左上对角线
                _x--;
                _y--;
                // 如果 _x 或者 _y 越界就 break
                if (_x < 0 || _y < 0) break;
                if (tmp[_y][_x] === 'Q') return;
            }
            _x = x, _y = y;
            while(true) {
                // 扫描当前坐标的右上对角线
                _x++;
                _y--;
                // 如果 _x 或者 _y 越界就 break
                if (_x >= n || _y < 0) break;
                if (tmp[_y][_x] === 'Q') return;
            }

            // 复制一份儿棋盘 因为 array 是引类型 也是为了回溯时候能保证棋盘还是上一次的状态
            const _tmp = tmp.map(item => [...item]);
            // 暂时把皇后下到当前坐标
            _tmp[y][x] = 'Q';
            for (let i = 0; i < n; i++) {
                // 从下一行的第 0 位开始挨个儿试
                _solveNQueens(_tmp, i, y + 1, target, current + 1);
            }
        }
    }
    for (let i = 0; i < n; i++) {
        // 第一次可能下在从左往右数第 i 个位置 下一步要下在第 0 行 目标是下 n 颗皇后, 当前已经下了 0 颗
        _solveNQueens(checkerBoard, i, 0, n, 0);
    }
    
    console.log(res);
};

按照这个思路,我可以得到所有的正确答案,但是在 res 中每个答案都会有大量的重复,有点想不明为啥会有重复的。
能否麻烦老师帮忙分析一下?
谢谢老师~

写回答

1回答

liuyubobobo

2020-12-04

当你成功在最后一行摆上了妻子周后,还会运行一遍:

for (let i = 0; i < n; i++) {
    // 从下一行的第 0 位开始挨个儿试
    _solveNQueens(_tmp, i, y + 1, target, current + 1);
}


这一遍调用 solve 都会执行:

if (current === target) {
    // 如果当前下的棋子数正好等于目标的 n 那就找到了一个结果
    res.push(tmp.map(i => i.join('')));
}


所以这个解会被放进去 n 次。


代码遇到 bug,不要想,要去调试。去实际看为什么会发生这个错误。自己的思维哪里错了。debug 非常非常重要,进步就发生在这个过程中。


加油!:)

0
4
Osuribaba
回复
liuyubobobo
好的,受教了,谢谢老师
2020-12-05
共4条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程