[LeetCode] 全排列

[plh97]

n 皇后 https://leetcode.com/problems/n-queens/

特别简单的一个问题, 就是直接暴力解法就好了, 这是一个决策树问题, 因此, 我们只需要通过递归的形式, 找出所有的决策. 可能存在的决策方式, 也就是皇后在棋盘中的摆放方式.

1. 遍历每一列
2. 遍历每一行
3. 通过这种方式递归出N*N种摆放方式.
4. 校验每种情况是否合法, 使用 isValid 函数做这件事
   1. 检验横向是否有皇后
   2. 检验纵向是否有皇后
   3. 检验↖️↘️向是否有皇后
   4. 检验↙↗向是否有皇后

var solveNQueens = function(n) {
    const temp = (new Array(n)).fill('.'.repeat(n).split(''))
    const res = []
    function help(temp, col) {
        // 遍历每一列, 当前如果是最后一列, 直接输出结果
        if (col==n) {
            res.push(temp)
            return
        }
        // 遍历每一行
        for (let i=0;i<n;i++) {
            const newTemp = JSON.parse(JSON.stringify(temp))
            if (isValid(newTemp, col, i)) {
                newTemp[col][i] = 'Q'
                help(newTemp, col+1)    // 如果当前行遍历完, 可以遍历下一列了
            }
        }
    }
    help(temp, 0)
    return res.map(e=>e.map(col=>col.join('')))
};

function isValid(temp, col, row) {
    // 在过程中就进行校验, 当前点 temp[col][row] 在上下左右, 斜边方向是否有 `Q`.
    // 检验竖向, 因为横向不用检验
    for(let i=0;i<temp[0].length;i++)
        if (temp[i][row] === 'Q') return false
    // 检验↖ , 因为 ↘ 不符合情况, 因为我们是过程中就进行检验了, 因此只要检查之前的是否有`Q`
    for(let i=col,j=row;i>=0&&j>=0;){
        if (temp[i][j] === 'Q') return false
        i--;
        j--;
    }
    // 检验↗, 同理, 不用检验 ↙, 原因在于我们是过程中检验的.
    for(let i=col,j=row;j<temp.length&&i>=0;){
        if (temp[i][j] === 'Q') return false
        i--;
        j++;
    }
    return true
}

数独题目, https://leetcode.com/problems/sudoku-solver/

前面的n皇后差不多, 都是搜索题, 不过这个是找出唯一解, 貌似 dfs 更优. 但就难度来说, 比n皇后大多了. 以全排列形式枚举所有可能, 然后在过程中剪支(排除不符合条件的答案).

var solveSudoku = function(board) {
    const temp  ='123456789'.split('')
  let res = []
  function help(row, col, resolve) {
    if (res.length>0) return
    resolve = JSON.parse(JSON.stringify(resolve))
    if (row>8) {
      res = resolve
      return
    }
    let currRow = resolve[row]
    if (currRow[col]=='.') {
      // 无值才填入
      const newCol = temp.filter(e => !(
        // 检查行是否重复
        currRow.includes(e)
        // 检查列是否重复
        || resolve.map(row => row[col]).includes(e)
        // 检查单元格是否重复
        || isBlockRepeat(e, row, col, resolve)
      ))
      newCol.forEach(e=>{
        if (col===8) {
          resolve[row][col] = String(e)
          help(row+1, 0, resolve)
        }else{
          resolve[row][col] = String(e)
          help(row, col+1, resolve)
        }
      })
    } else {
      if (col===8) {
        help(row+1, 0, resolve)
      } else {
        help(row, col+1, resolve)
      }
    }
  }
  help(0,0, board)
    res.forEach((col,i) => {
        col.forEach((e,j)=>{
            board[i][j] = res[i][j]
        })
    })
};

function isBlockRepeat(e,row, col, resolve) {
  for(let i=0;i<3;i++) {
    for(let j=0;j<3;j++) {
      if (i*3<=col && col<(i+1)*3 && j*3<=row && row<(j+1)*3) {
        if (isRepeat2(e,resolve.slice(j*3, (j+1)*3).map(col => col.slice(i*3,(i+1)*3)))) {
          return true
        }
      }
    }
  }
  return false
}

function isRepeat2(e, arr, isConsole) {
  for(let col of arr) {
    for(let ee of col) {
      if (e==ee) {
        return true
      }
    }
  }
  return false
}