N 皇后


N 皇后

const solveNQueens = function (n) {
  // 已摆放皇后的列下标
  const cols = new Set();

  // 已摆放皇后的左斜线 右上→左下
  // 计算某个坐标是否在这个左斜线的方式是「行下标 + 列下标」是否相等
  const left = new Set();

  // 已摆放皇后的右斜线 左上→右下
  // 计算某个坐标是否在这个右斜线的方式是「行下标 - 列下标」是否相等
  const right = new Set();

  // 解法结果数组
  const result = [];

  valid(0, n, cols, left, right, result, []);

  // 解法数组绘制成目标数组
  return draw(result, n);
};

const valid = function (row, n, cols, left, right, result, temp) {
  // 终止条件,最后一行都走完了,说明找到了一组,把它加入到集合result中
  if (row === n) {
    result.push([...temp]);
    temp = [];
  }
  for (let i = 0; i < n; i++) {
    if (!cols.has(i) && !right.has(row - i) && !left.has(row + i)) {
      // 在列上不冲突、在左斜线上不冲突、在右斜线上不冲突,先记录当前已选位置,进入下一轮递归
      cols.add(i);
      left.add(row + i);
      right.add(row - i);
      temp[row] = i;
      valid(row + 1, n, cols, left, right, result, temp);

      // 递归出栈后,在状态中清除这个位置的记录,下一轮循环应该是一个全新的开始。
      cols.delete(i);
      left.delete(row + i);
      right.delete(row - i);
    }
  }
};

function draw(arr, n) {
  let res = [];
  arr.forEach((item) => {
    let sub = [];
    item.forEach((i) => {
      let temp = Array(n).fill(".");
      temp[i] = "Q";
      sub.push(temp.join(""));
    });
    res.push(sub);
  });
  return res;
}

 上一篇
节流和防抖 节流和防抖
节流和防抖防抖防抖的原理就是:你尽管触发事件,但是我一定在事件触发 n 秒后才执行,如果你在一个事件触发的 n 秒内又触发了这个事件,那我就以新的事件的时间为准,n 秒后才执行,总之,就是要等你触发完事件 n 秒内不再触发事件,我才执行。
下一篇 
JavaScript 实现Promise 及相关API JavaScript 实现Promise 及相关API
/** * 1. new Promise时,需要传递一个 executor 执行器,执行器立刻执行 * 2. executor 接受两个参数,分别是 resolve 和 reject, resolve 和 reject 是 Promis
  目录