力扣每日一题37：解数独

2024-05-11 00:20
文章标签 力扣 一题 每日 37 解数

本文主要是介绍力扣每日一题37：解数独，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

题目

大致思路

方法一：回溯剪枝（正常人能想出来的）

方法二：位运算优化剪枝

需要使用的位运算技巧

代码

位运算怎么就优化了呢？

方法三：枚举优化。

官解代码

方法四：舞蹈链算法

题目

困难

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

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

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

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

示例 1：

输入：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"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

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

面试中遇到过这道题?

1/5

是

否

通过次数

248.8K

提交次数

367.3K

通过率

67.7%

大致思路

使用一个数据记录每个每一行，每一列，每一个3*3宫格中数组1-9出现的情况。

对所有空格（也就是需要填数的地方）进行遍历填数，判断这个位置能填1-9中的哪个数字，如果数字num在空格所在的行、列、3*3宫格都没出现过，那就可以把num放进去，然后填写下一个空格。当填写完最后一个空格的时候，就代表解完了。

方法一：回溯剪枝（正常人能想出来的）

对于每一行、每一列、每个3*3宫格中1-9出现的情况，我们都用一个哈希表表示。

这样在对某个空格进行填数num时，我们只需要判断这个空格所在行、所在列、所在3*3宫格有没有出现过num即可。

class Solution {
public://判断九行、九列、九个格中数字1-9有无出现的哈希表int rows[9][9];int columns[9][9];int boxes[3][3][9];vector<pair<int,int>> blanks;//需要填写的空格bool flag;//用来剪枝void solveSudoku(vector<vector<char>>& board) {//初始化哈希表memset(rows,0,sizeof(rows));memset(columns,0,sizeof(columns));memset(boxes,0,sizeof(boxes));flag=false;//遍历一次9*9宫，寻找空格并更新哈希表int i,j;for(i=0;i<9;i++){for(j=0;j<9;j++){char c=board[i][j];if(c=='.'){blanks.emplace_back(i,j);//blanks.emplace_back({i,j});会有语法错误}else{int digit=c-'0';rows[i][digit-1]=columns[j][digit-1]=boxes[i/3][j/3][digit-1]=1;}}}backtrack(board,0);}void backtrack(vector<vector<char>>& board,int index){//填完了最后一个空格，if(index==blanks.size()){flag=true;return;}//1-9遍历int x=blanks[index].first;int y=blanks[index].second;for(int num=1;num<=9&&flag==false;num++){if(rows[x][num-1]==0&&columns[y][num-1]==0&&boxes[x/3][y/3][num-1]==0){rows[x][num-1]=columns[y][num-1]=boxes[x/3][y/3][num-1]=1;board[x][y]=num+'0';backtrack(board,index+1);rows[x][num-1]=columns[y][num-1]=boxes[x/3][y/3][num-1]=0;}}}
};

方法二：位运算优化剪枝

看了题解我才知道这也能优化…………

在方法一中，我们使用了长度为 9 的数组表示每个数字是否出现过（1为出现过，0为没有出现）。我们同样也可以借助位运算，仅使用一个整数表示每个数字是否出现过。

具体的做法是：一个二进制数的第i位数（最低为是第0位）是1，就表示 i+1 已经出现过。例如：

二进制数 (011010100) 代表数字 3、5、7、8已经出现过。

也就是说我们用一个二进制数来表示一个哈希表。

在方法一中，每在一个空格出现一个数字num，或者是填写一个数字num，都要将这个空格对于行、列、3*3宫格的哈希表的num值由0变成1，也就是 简单的[num-1]=1，填写完num发现数字不对后，又要将哈希表num的值由1变成0。也就是说，在用数组当作哈希表时，哈希表的更新就是将数组对应的值简单的0，1互换。

在此方法中，哈希表的更新就变成了二进制数对应某一位上的0，1互换。要使用一些位运算的技巧，

需要使用的位运算技巧

（1）、将二进制数的第i位由i变成0，或由0变成1.

1<<i 的第i+1位二进制数是1，其余的二进制数是0。x和1<<i按位异或后，x=x^(1<<i)后，x的第i+1位就实现了0，1的互换。

（2）、遍历一个二进制数上的所有0。

方法一中，空格所在的行、列、3*3宫格的哈希表[num-1]==0就代表这个空格可以填数字num，而在二进制的哈希表中，我们要找二进制数对应的0。二进制数的0不太好取，我们就把0，1互换，互换后的1就是先前的0，而二进制的1是好取的（随后会讲）。

一个二进制数按位取反得到的1就是先前的0，但是我们只需要前9位的1，所以取反后的数还要和 （111111111）进行按位与操作，这样就能只留下前九位数。

（3）、取得二进制数最低位的1（包括后面的0）

x=~x&(111111111) 后，x中第i（从最低为第0位开始）位的1就代表数字 i+1可以填在空格里。

low_one=x&(-x)。因为-x在计算器用的是补码，所以-x和x的二进制数的最低为1和右边的0都相等，其余为都不想等，按位与刚好可以留下这一部分。留下这一部分后，low_one的位数就是可以填入空格的数字。

（4）、将二进制数的最低为1变成0。

在某个空格blanks中填入某个数后不一定对，这时候要填下一个数。我们只需要将最低位的1变成0，然后再取最低位的1，这样就取到了下一个数。

x&=(x-1);

代码

class Solution {
private:int rows[9];int cols[9];int boxes[3][3];vector<pair<int, int>> blanks;bool valid;
public://将指定数位1变0，0变1void func(int i, int j, int digit) {rows[i] ^= (1 << digit);cols[j] ^= (1 << digit);boxes[i / 3][j / 3] ^= (1 << digit);}void backtrack(vector<vector<char>>& board, int index) {if (index == blanks.size()) {valid = true;return;}int x = blanks[index].first;int y = blanks[index].second;//创建掩码来遍历int mask = ~(rows[x] | cols[y] | boxes[x / 3][y / 3]);mask = mask & 0x1ff;            //和（111111111）按位取和，去除第九位之前的1while (mask && !valid) {//取最低位的1包括后面的0,然后转换成对应的数字int lowdigit = mask & (-mask);int digit = 0;while (lowdigit) {lowdigit >>= 1;digit++;}func(x, y, digit - 1);board[x][y] = '0' + digit;backtrack(board, index + 1);func(x, y, digit - 1);//去除掉最低位的1mask &= (mask - 1);}}void solveSudoku(vector<vector<char>>& board) {memset(rows, 0, sizeof(rows));memset(cols, 0, sizeof(cols));memset(boxes, 0, sizeof(boxes));valid = false;for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] == '.') {blanks.emplace_back(i, j);}else {int digit = board[i][j] - '0' - 1;func(i, j, digit);}}}backtrack(board, 0);}
};

位运算怎么就优化了呢？

对比一下方法一和方法二的代码。区别就是哈希表的更新和在遍历空格时，对于填充数字的遍历。

先说哈希表的更新，方法一的代码是

rows[i][digit-1]=columns[j][digit-1]=boxes[i/3][j/3][digit-1]=1;
或
rows[i][digit-1]=columns[j][digit-1]=boxes[i/3][j/3][digit-1]=0;

而方法二是对下面函数的一次调用。

void func(int i, int j, int digit) {rows[i] ^= (1 << digit);cols[j] ^= (1 << digit);boxes[i / 3][j / 3] ^= (1 << digit);}

光看这一部分来说，方法二反而要更复杂。

但是考虑到对空格填充数字的遍历时，那就不一样了。

方法一是对数字1-9都有一次判断，一共有九次。

for(int num=1;num<=9&&flag==false;num++){if(rows[x][num-1]==0&&columns[y][num-1]==0&&boxes[x/3][y/3][num-1]==0){//填充数字}
}

而方法二是在创建掩码后，每次只取对应二进制数位上有1的数。

//创建掩码来遍历int mask = ~(rows[x] | cols[y] | boxes[x / 3][y / 3]);mask = mask & 0x1ff;            //和（111111111）按位取和，去除第九位之前的1while (mask && !valid) {//填充数字mask &= (mask - 1);}

假设某个空格所在行、列、3*3宫格都只有一个数9可以填的时候，方法一需要循环9次，而方法二在创建掩码后，只需要循环1次。也就是说，方法二自动过滤掉了空格所在行、列、3*3宫格中已经出现的数。这大大缩短了代码运行时间。

方法三：枚举优化。

看了题解还知道，位运算的方法还能优化………………

想一下，我们在手作数独游戏的时候，都是先将能确定数字的位置先填上。

就比如在刚开始给出的矩阵中，有一个空格所在行出现过1、2、3，所在列出现过4、5、6，所在九宫格出现过7，8。那么毫无疑问，这个位置就是填9，不用等其他位置填完也能确认。

这样一来，我们可以不断地对整个数独进行遍历，将可以唯一确定的空白格全部填入对应的数。随后我们再使用与方法二相同的方法对剩余无法唯一确定的空白格进行递归 + 回溯。

官解代码

class Solution {
private:int line[9];int column[9];int block[3][3];bool valid;vector<pair<int, int>> spaces;public:void flip(int i, int j, int digit) {line[i] ^= (1 << digit);column[j] ^= (1 << digit);block[i / 3][j / 3] ^= (1 << digit);}void dfs(vector<vector<char>>& board, int pos) {if (pos == spaces.size()) {valid = true;return;}auto [i, j] = spaces[pos];int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;for (; mask && !valid; mask &= (mask - 1)) {int digitMask = mask & (-mask);int digit = __builtin_ctz(digitMask);flip(i, j, digit);board[i][j] = digit + '0' + 1;dfs(board, pos + 1);flip(i, j, digit);}}void solveSudoku(vector<vector<char>>& board) {memset(line, 0, sizeof(line));memset(column, 0, sizeof(column));memset(block, 0, sizeof(block));valid = false;for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) {if (board[i][j] != '.') {int digit = board[i][j] - '0' - 1;flip(i, j, digit);}}}while (true) {int modified = false;for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) {if (board[i][j] == '.') {int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;if (!(mask & (mask - 1))) {int digit = __builtin_ctz(mask);flip(i, j, digit);board[i][j] = digit + '0' + 1;modified = true;}}}}if (!modified) {break;}}for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) {if (board[i][j] == '.') {spaces.emplace_back(i, j);}}}dfs(board, 0);}
};

方法四：舞蹈链算法

我以为吕布已经天下无敌了，没想到有人比他还要勇猛…………

我翻看评论的时候，看到有个大佬发的一种算法，叫做舞蹈链算法，自称是解数独最快的算法，没有之一。这算法我也不会，直接把代码贴上来吧。

/*
最快的是舞蹈链算法
然后是贪心加回溯算法
最慢的是正常的回溯算法
*/
#include <bits/stdc++.h>using namespace std;const int N = 9 * 9 * 9 * 4;class node {
public:int u{}, d{}, l{}, r{}; //上下左右int row{}, col{};   //具体坐标int s{};          //col节点数量int h{};          //row头节点int ans{};        //选了那些rownode() = default;
};class DLX {
public:vector<vector<int>> a;const int n = 9 * 9 * 9, m = 9 * 9 * 4;int num{};vector<node> nodes;explicit DLX(vector<vector<int>> &B) {a = B;dance();B = a;}void dance() {init();for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {for (int k = 1; k <= 9; k++) {if (a[i][j] != k && a[i][j] != 0) {continue;}int id = i * 9 * 9 + j * 9 + k;Link(id, i * 9 + j + 1);Link(id, i * 9 + k + 81);Link(id, j * 9 + k + 162);Link(id, (i / 3 * 3 + j / 3) * 9 + k + 243);}}}Dance(0);}void init() {num = m + 1;nodes.assign(N, node());for (int i = 0; i <= m; i++) {node &it = nodes[i];it.l = i - 1;it.r = i + 1;it.u = it.d = i;}nodes[0].l = m;nodes[m].r = 0;}void Link(int r, int c) {num++;node &row = nodes[r];node &col = nodes[c];node &nums = nodes[num];nums.row = r;nums.col = c;col.s++;// node[col.u] <-> nums <-> colnums.u = col.u;nodes[col.u].d = num;col.u = num;nums.d = c;if (row.h == 0) {row.h = nums.l = nums.r = num;} else {node &head = nodes[row.h];//node[head.l] <-> nums <-> headnums.l = head.l;nodes[head.l].r = num;head.l = num;nums.r = row.h;}}void Remove(int c) {node &col = nodes[c];// node[col.l] <-> node[col.r]nodes[col.l].r = col.r;nodes[col.r].l = col.l;//下右for (int i = col.d; i != c; i = nodes[i].d) {for (int j = nodes[i].r; j != i; j = nodes[j].r) {node &it = nodes[j];//node[it.u] <-> node[it.d]nodes[it.d].u = it.u;nodes[it.u].d = it.d;nodes[it.col].s--;}}}void Resume(int c) {// node[col.l] -> node[c] <- node[col.r]node &col = nodes[c];nodes[col.r].l = c;nodes[col.l].r = c;//上左for (int i = nodes[c].u; i != c; i = nodes[i].u) {for (int j = nodes[i].l; j != i; j = nodes[j].l) {node &it = nodes[j];//node[it.u] -> node[j] <- node[it.d]nodes[it.d].u = j;nodes[it.u].d = j;nodes[it.col].s++;}}}int Dance(int dep) { // NOLINT(*-no-recursion)if (nodes[0].r == 0) {for (int i = 0; i < dep; i++) {node &it = nodes[i];int x = (it.ans - 1) / 9 / 9;int y = (it.ans - 1) / 9 % 9;int val = (it.ans - 1) % 9 + 1;a[x][y] = val;}return 1;}int c = nodes[0].r;for (int i = nodes[0].r; i != 0; i = nodes[i].r) {if (nodes[i].s == 0 || nodes[c].s == 0) {return 0;}if (nodes[i].s < nodes[c].s) {c = i;}}Remove(c);for (int i = nodes[c].d; i != c; i = nodes[i].d) {node &it = nodes[i];nodes[dep].ans = it.row;for (int j = nodes[i].r; j != i; j = nodes[j].r) {Remove(nodes[j].col);}if (Dance(dep + 1) == 1) {return 1;}for (int j = nodes[i].l; j != i; j = nodes[j].l) {Resume(nodes[j].col);}}Resume(c);return 0;}
};class Solution {
public:static void solveSudoku(vector<vector<char>> &b) {vector<vector<int>> a(9, vector<int>(9));for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {int val = b[i][j] == '.' ? 0 : int(b[i][j] - '0');a[i][j] = val;}}DLX o(a);for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {b[i][j] = char(a[i][j] + '0');}}}
};

这篇关于力扣每日一题37：解数独的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/977982。

相关文章

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
阅读更多...
每日一练7：简写单词（含链接）

每日一练7：简写单词（含链接）

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1（错误经验） #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=
阅读更多...
两数之和--力扣1

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求，元素不能重复且不需要排序，我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中，使用目标值减去当前循环的nums[i]，得到差值，如果我们在map中能够找到这个差值，就说明存在两个整数的和为目标值。 如果没有找到，就将当前循环的nums[i]以及下标i放入map中，以便后续查
阅读更多...
【每日刷题】Day113

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页：开敲🍉 🔥所属专栏：每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣（LeetCode） 2. LCR 098. 不同路径 - 力扣（LeetCode） 3. 63. 不同路径 II - 力扣（LeetCode） 1. 91. 解码方法 - 力扣（LeetCode） //思路：动态规划。 cl
阅读更多...
力扣第347题 前K个高频元素

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目： 分析 我们首先使用哈希表来统计数字出现的频率，然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组，对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢？假如说总共有三个数字都为1，那么我们需要把这个1放在数组下标为3的位置，假如说数组长度为n，对于这个例子就是长度为3，那么它的
阅读更多...
【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82， 237

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82， 237

总结，删除链表节点问题使用到列表，哈希表，递归比较容易超时，我觉得使用计数排序比较稳，处理起来也不是很难。 1. 力扣3217：从链表中移除在数组中的节点 1.1 题目： 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。 示例 1： 输入： nums = [1,2,3], head = [1,2,3,
阅读更多...
力扣 739. 每日温度【经典单调栈题目】

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意： 1.1. 给一个温度集合， 要返回一个对应长度的结果集合， 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差， 若是当前元素不存在下一个更高温度的元素， 则这个位置用0代替； 2. 思路 本题用单调栈来求解；单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素；【单调栈：让栈中的元素保持单调
阅读更多...
力扣接雨水

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 输入：height
阅读更多...
每日一题——第八十一题

每日一题——第八十一题

打印如下图案: #include<stdio.h>int main() {int i, j;char ch = 'A';for (i = 1; i < 5; i++, ch++){for (j = 0; j < 5 - i; j++){printf(" ");//控制空格输出}for (j = 1; j < 2 * i; j++)//条件j < 2 * i{printf("%c", ch
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2