專(zhuān)欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專(zhuān)欄：50多種經(jīng)典圖論算法全部掌握

一網(wǎng)友在網(wǎng)上發(fā)問(wèn)：為什么拼多多不裁員？實(shí)際上拼多多不可能不裁員，互聯(lián)網(wǎng)公司都出現(xiàn)過(guò)裁員，只不過(guò)裁員的規(guī)模大小不同，比如2022年和2024年拼多多曾因增速放緩、成本控制等原因被曝出裁員事件，但其裁員規(guī)模相對(duì)其他互聯(lián)網(wǎng)公司較小。

拼多多裁員低的原因有多方面的，比如跨境電商Temu的崛起。高薪留人，拼多多以高于同行業(yè)的薪資吸引員工。嚴(yán)苛的考勤與工作制度，比如“11-11-6”工作制，高強(qiáng)度工作環(huán)境下，部分員工因難以承受壓力主動(dòng)離職，降低裁員比例，公司無(wú)需頻繁啟動(dòng)大規(guī)模裁員計(jì)劃，還有一個(gè)就是強(qiáng)勁的盈利能力。

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

來(lái)看下今天的算法題，這題是LeetCode的第36題：有效的數(shù)獨(dú)。

問(wèn)題描述

來(lái)源：LeetCode第36題

難度：中等

請(qǐng)你判斷一個(gè) 9 x 9 的數(shù)獨(dú)是否有效。只需要根據(jù)以下規(guī)則 ，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

1，數(shù)字 1-9 在每一行只能出現(xiàn)一次。

2，數(shù)字 1-9 在每一列只能出現(xiàn)一次。

3，數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。（請(qǐng)參考示例圖）

注意：

1，一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的。

2，只需要根據(jù)以上規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

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] 是一位數(shù)字（1-9）或者 '.'

問(wèn)題分析

這題不是解數(shù)獨(dú)，而是判斷數(shù)獨(dú)是否有效。數(shù)獨(dú)大家應(yīng)該都玩過(guò)，就是 每行每列以及每個(gè)9宮格內(nèi)都不能有重復(fù)的數(shù)字 ，因?yàn)槊啃忻苛幸约懊總€(gè)9宮格最多只能有9個(gè)數(shù)字，所以我們可以使用 位運(yùn)算 來(lái)解決。

比如line[i]就表示第 i 行的狀態(tài)，如果第 i 行有一個(gè) 3 我們就在數(shù)字line[i]的二進(jìn)制中第 3 位標(biāo)記為 1 ，如果第 i 行有一個(gè) 5 我們就在數(shù)字line[i]的二進(jìn)制中第 5 位標(biāo)記為 1 ，如下圖所示。

如果我們?cè)跇?biāo)記某個(gè)位置之前，該位置已經(jīng)被標(biāo)記過(guò)，說(shuō)明出現(xiàn)了重復(fù)數(shù)字，那么這個(gè)數(shù)獨(dú)就是無(wú)效的，代碼如下。

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++) {             // 如果當(dāng)前位置沒(méi)有數(shù)字，不用判斷。             if (board[i][j] == '.')                 continue;             int shift = 1 << (board[i][j] - '0');// 確定第幾位             int k = (i / 3) * 3 + j / 3;// 9宮格的第幾個(gè)。             // 如果對(duì)應(yīng)的位置只要有一個(gè)被標(biāo)記過(guò)，說(shuō)明有沖突，直接返回false。             if ((col[i] & shift) > 0 || (line[j] & shift) > 0                     || (cell[k] & shift) > 0)                 return false;             // 把當(dāng)前位置所在的行，列以及9宮格都標(biāo)記為該數(shù)字已經(jīng)存在。             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++) {                 // 如果當(dāng)前位置沒(méi)有數(shù)字，不用判斷。                 if (board[i][j] == '.')                     continue;                 int shift = 1 << (board[i][j] - '0');// 確定第幾位                 int k = (i / 3) * 3 + j / 3;// 9宮格的第幾個(gè)。                 // 如果對(duì)應(yīng)的位置只要有一個(gè)被標(biāo)記過(guò)，說(shuō)明有沖突，直接返回false。                 if ((col[i] & shift) > 0 || (line[j] & shift) > 0                         || (cell[k] & shift) > 0)                     return false;                 // 把當(dāng)前位置所在的行，列以及9宮格都標(biāo)記為該數(shù)字已經(jīng)存在。                 col[i] |= shift;                 line[j] |= shift;                 cell[k] |= shift;             }         }         return true;     }

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專(zhuān)注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫(xiě)算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁(yè)的PDF算法文檔 。