blog
blog copied to clipboard
[LeetCode] 全排列
n 皇后 https://leetcode.com/problems/n-queens/
特别简单的一个问题, 就是直接暴力解法就好了, 这是一个决策树问题, 因此, 我们只需要通过递归的形式, 找出所有的决策. 可能存在的决策方式, 也就是皇后在棋盘中的摆放方式.
- 遍历每一列
- 遍历每一行
- 通过这种方式递归出N*N种摆放方式.
- 校验每种情况是否合法, 使用
isValid
函数做这件事- 检验横向是否有皇后
- 检验纵向是否有皇后
- 检验↖️↘️向是否有皇后
- 检验↙↗向是否有皇后
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
}