专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

一网友在网上发问：为什么拼多多不裁员？实际上拼多多不可能不裁员，互联网公司都出现过裁员，只不过裁员的规模大小不同，比如2022年和2024年拼多多曾因增速放缓、成本控制等原因被曝出裁员事件，但其裁员规模相对其他互联网公司较小。

拼多多裁员低的原因有多方面的，比如跨境电商Temu的崛起。高薪留人，拼多多以高于同行业的薪资吸引员工。严苛的考勤与工作制度，比如“11-11-6”工作制，高强度工作环境下，部分员工因难以承受压力主动离职，降低裁员比例，公司无需频繁启动大规模裁员计划，还有一个就是强劲的盈利能力。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第36题：有效的数独。

问题描述

来源：LeetCode第36题

难度：中等

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则 ，验证已经填入的数字是否有效即可。

1，数字 1-9 在每一行只能出现一次。

2，数字 1-9 在每一列只能出现一次。

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

注意：

1，一个有效的数独（部分已被填充）不一定是可解的。

2，只需要根据以上规则，验证已经填入的数字是否有效即可。

3，空白格用 '.' 表示。

示例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"]] 输出：true

  • board.length == 9

  • board[i].length == 9

  • board[i][j] 是一位数字（1-9）或者 '.'

问题分析

这题不是解数独，而是判断数独是否有效。数独大家应该都玩过，就是 每行每列以及每个9宫格内都不能有重复的数字 ，因为每行每列以及每个9宫格最多只能有9个数字，所以我们可以使用 位运算 来解决。

比如line[i]就表示第 i 行的状态，如果第 i 行有一个 3 我们就在数字line[i]的二进制中第 3 位标记为 1 ，如果第 i 行有一个 5 我们就在数字line[i]的二进制中第 5 位标记为 1 ，如下图所示。

如果我们在标记某个位置之前，该位置已经被标记过，说明出现了重复数字，那么这个数独就是无效的，代码如下。

JAVA：

public boolean isValidSudoku(char[][] board) {     int[] line = new int[9];// 行     int[] col = new int[9];// 列     int[] cell = new int[9];// 9宫格     for (int i = 0; i < 9; i++) {         for (int j = 0; j < 9; j++) {             // 如果当前位置没有数字，不用判断。             if (board[i][j] == '.')                 continue;             int shift = 1 << (board[i][j] - '0');// 确定第几位             int k = (i / 3) * 3 + j / 3;// 9宫格的第几个。             // 如果对应的位置只要有一个被标记过，说明有冲突，直接返回false。             if ((col[i] & shift) > 0 || (line[j] & shift) > 0                     || (cell[k] & shift) > 0)                 return false;             // 把当前位置所在的行，列以及9宫格都标记为该数字已经存在。             col[i] |= shift;             line[j] |= shift;             cell[k] |= shift;         }     }     return true; }

C++：

public:     bool isValidSudoku(vector char >>& board) {         int line[9]= {0}; // 行         int col[9] = {0}; // 列         int cell[9] = {0}; // 9宫格         for (int i = 0; i < 9; i++) {             for (int j = 0; j < 9; j++) {                 // 如果当前位置没有数字，不用判断。                 if (board[i][j] == '.')                     continue;                 int shift = 1 << (board[i][j] - '0');// 确定第几位                 int k = (i / 3) * 3 + j / 3;// 9宫格的第几个。                 // 如果对应的位置只要有一个被标记过，说明有冲突，直接返回false。                 if ((col[i] & shift) > 0 || (line[j] & shift) > 0                         || (cell[k] & shift) > 0)                     return false;                 // 把当前位置所在的行，列以及9宫格都标记为该数字已经存在。                 col[i] |= shift;                 line[j] |= shift;                 cell[k] |= shift;             }         }         return true;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。