前端刷题路-Day15|刷题打卡

我心飞翔 分类:javascript

掘金团队号上线,助你 Offer 临门! 点击 查看详情

解数独(题号37)

题目

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则:

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3宫内只能出现一次。(请参考示例图)

数独部分空格内已填入了数字,空白格用 '.'表示。

示例:

img

输入:board = [
	["5","3",".",".","7",".",".",".","."],
	["6",".",".","1","9","5",".",".","."],
	[".","9","8",".",".",".",".","6","."],
	["8",".",".",".","6",".",".",".","3"],
	["4",".",".","8",".","3",".",".","1"],
	["7",".",".",".","2",".",".",".","6"],
	[".","6",".",".",".",".","2","8","."],
	[".",".",".","4","1","9",".",".","5"],
	[".",".",".",".","8",".",".","7","9"]
]
输出:[
	["5","3","4","6","7","8","9","1","2"],
	["6","7","2","1","9","5","3","4","8"],
	["1","9","8","3","4","2","5","6","7"],
	["8","5","9","7","6","1","4","2","3"],
	["4","2","6","8","5","3","7","9","1"],
	["7","1","3","9","2","4","8","5","6"],
	["9","6","1","5","3","7","2","8","4"],
	["2","8","7","4","1","9","6","3","5"],
	["3","4","5","2","8","6","1","7","9"]
]
 

解释:输入的数独如上图所示,唯一有效的解决方案如下所示:

img

提示:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

链接

leetcode-cn.com/problems/su…

解释

着实有点难,自己写的时候GG了,但不知道是哪里GG,有可能是性能吃的太多,也有可能是递归写GG了,写得很复杂,不清楚,感觉还是没有理清楚,下次需要注意

整体的逻辑是这样的,在递归的时候不用传递board,直接修改全局board即可。

递归的函数会返回true或者false,在递归前修改board中的数据,之后判断下一次递归是否成功,如果不成功,回溯一下,将board中的数据改回去,就这样一直一直改就好了,干到最后board就是修改完成后的。

重点就在于回溯的理解,有两点需要注意:

  1. 回到上一步,如果这一步错了就往上一步继续走
  2. 不要同时开始所有可能性的计算,要一种一种的计算,否则会有超时问题

自己的答案

更好的方法(暴力解法)

var solveSudoku = (board) => {
  function isInside(row, col, val) {
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === val || board[i][col] === val) {
        return true
      }
    }
    var startI = parseInt(row /3) * 3
        startJ = parseInt(col / 3) * 3
    for (let i = startI; i < startI + 3; i++) {
      for (let j = startJ; j < startJ + 3; j++) {
        if (board[i][j] === val) return true
      }      
    }
    return false
  }
  function fill(row, col) {
    if (col === 9) {
      row++
      col = 0
      if (row === 9) return true
    }
    if (board[row][col] !== '.') return fill(row, col + 1);
    for (let i = 1; i < 10; i++) {
      if (!isInside(row, col, `${i}`)) {
        board[row][col] = `${i}`
        if (fill(row, col + 1)) {
          return true
        } else {
          board[row][col] = '.'
        }
      }
    }
    return false
  }
  fill(0, 0)
  return board
};
 

这段代码是看了答案之后写出来的,其实还是比较简单的。

首先看看isInside方法,该方法根据当前传入的坐标值来对board进行查找,判断出当前行、当前列和当前块都没有重复的数字,如此证明这个数字可以被填在当前的格子里,如果不通过则该数字不能填在当前格子里,跳过即可,继续进行下一步填写操作。

这个方法确实比较简单,缺点就是每次都要重新查询下,有点耗费性能,下面这种方法会存储一些数据,减少查询时间。

更好的方法(存储数据)

var solveSudoku = (board) => {
  function getBlockIndex(i, j) {
    return parseInt(i / 3) * 3 + parseInt(j / 3)
  }
  var rowArr = new Array(9)
      colArr = new Array(9)
      blockArr = new Array(9)
      defaultSetting = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
  for (let i = 0; i < 9; i++) {
    rowArr[i] = new Set(defaultSetting) 
    colArr[i] = new Set(defaultSetting) 
    blockArr[i] = new Set(defaultSetting) 
  }
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      var val = board[i][j]
      if (val !== '.') {
        rowArr[i].delete(val)
        colArr[j].delete(val) 
        blockArr[getBlockIndex(i, j)].delete(val)
      }      
    }
  }
  function fill(row, col) {
    if (col === 9) {
      row++
      col = 0
      if (row === 9) return true
    }
    if (board[row][col] !== '.') return fill(row, col + 1);
    for (let i = 1; i < 10; i++) {
      var strNum = `${i}`
      if (rowArr[row].has(strNum) && colArr[col].has(strNum) && blockArr[getBlockIndex(row, col)].has(strNum)) {
        board[row][col] = strNum
        rowArr[row].delete(strNum)
        colArr[col].delete(strNum)
        blockArr[getBlockIndex(row, col)].delete(strNum)
        if (fill(row, col + 1)) {
          return true
        } else {
          board[row][col] = '.'
          rowArr[row].add(strNum)
          colArr[col].add(strNum)
          blockArr[getBlockIndex(row, col)].add(strNum)
        }
      }
    }
    return false
  }
  fill(0, 0)
  return board
};
 

这里主去掉了isInside方法,直接将9行、9列、9块中没有出现的数字填到三个数组中去,每次需要添加新数字的时候,判断这三个数组中是否有这个数字,如果都有,则可以添加,否则就不能添加。添加完成后不仅仅要修改board,也要修改三个数组。

之后判断下个空格有没有数字可填,如果没有,则回溯一下,撤销对board和三个数组的修改,进行下一次循环,以此类推。

但笔者感觉这里稍微有点复杂,其实默认传个空Set,之后往里面插入已经存在的数据。循环的时候判断当前Set是否有无也行,为了实践一下,笔者用数组也实现了一手👇:

var solveSudoku = function(board) {
  var rowArr = Array.from({length: 9}, () => ([]))
      colArr = Array.from({length: 9}, () => ([]))
      blockArr = Array.from({length: 9}, () => ([]))
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] !== '.') {
        rowArr[i].push(board[i][j])
        colArr[j].push(board[i][j])
        var block = ~~(i / 3) * 3 + ~~(j / 3)
        blockArr[block].push(board[i][j])
      }      
    }    
  }
  function fill(row, col) {
    if (col === 9) {
      row++
      col = 0
      if (row === 9) return true
    }
    if (board[row][col] !== '.') return fill(row, col + 1)
    var block = ~~(row / 3) * 3 + ~~(col / 3)
    for (let i = 1; i < 10; i++) {
      if (rowArr[row].includes(`${i}`)) continue
      if (colArr[col].includes(`${i}`)) continue
      if (blockArr[block].includes(`${i}`)) continue
      board[row][col] = `${i}`
      rowArr[row].push(`${i}`)
      colArr[col].push(`${i}`)
      blockArr[block].push(`${i}`)
      if (fill(row, col + 1)) {
        return true
      } else {
        board[row][col] = '.'
        rowArr[row].pop()
        colArr[col].pop()
        blockArr[block].pop()
      }
    }
    return false
  }
  fill(0, 0)
  return board
};
 

PS:想查看往期文章和题目可以点击下面的链接:

这里是按照日期分类的👇

前端刷题路-目录(日期分类)

经过有些朋友的提醒,感觉也应该按照题型分类
这里是按照题型分类的👇

前端刷题路-目录(题型分类)

有兴趣的也可以看看我的个人主页👇

Here is RZ

回复

我来回复
  • 暂无回复内容