專欄：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算法文檔 。