今天做一個LeetCode題發(fā)現(xiàn)一個小技巧，特來與你們分享一下。
做的LeetCode題是關(guān)于二維矩陣的圖論建模，像下面這樣的：
二維矩陣可以不產(chǎn)生一個圖結(jié)構(gòu)，直接在二維矩陣上計算。相應(yīng)地，會設(shè)定一個布爾值數(shù)組visited[ i ] [ j ]，表示某一個位置是否被遍歷，true表示被遍歷，false表示未被遍歷。
我們首先看看圖論建模是如何建模的， 二維數(shù)組會有兩個索引下標(biāo)i和j，分別對陣為行和列。我們會設(shè)定一個常量C，而這個常量正是列的長度，即nums[i].length。
對二維矩陣每一個位置都可以用 i * C + j 表示，如下圖：
如果圖結(jié)構(gòu)想轉(zhuǎn)換成二維矩陣也可以這樣表示，假設(shè)圖結(jié)構(gòu)的一個節(jié)點的鍵為g，位于二維矩陣的，第幾行用 g / C 表示，第幾列用 g % C 表示。
i = g / C; // 獲得第幾行
j = g % C; // 獲得第幾列
三維矩陣也是通過這樣的方式進行圖論建模，會設(shè)定兩個常量，一個是 j 的長度，另一個是 i 和 j 的面積。這里就不進行多介紹了，因為本篇介紹布爾值數(shù)組壓縮狀態(tài)的小技巧，再講三維矩陣的圖論建模就偏了，了解二維矩陣就好了。
在進行二維矩陣的圖論建模中，如果不轉(zhuǎn)成圖形結(jié)構(gòu)，直接在二維矩陣上計算，我們會設(shè)定一個布爾類型的二維數(shù)組visited，數(shù)組的值表示圖的某個節(jié)點是否遍歷過。
接著我們可以把true看作是1，false看作是0，然后轉(zhuǎn)成一維數(shù)組，如下表示：
[
0 0 0 0 0
0 0 0 0 0 => [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
0 0 0 0 0
]
然后可以把這看作是二進制，將一維數(shù)組直接轉(zhuǎn)成一個數(shù)字。
最重要的是，轉(zhuǎn)成了一個數(shù)字，如何查看某個節(jié)點是否被遍歷過，又如何將某個節(jié)點設(shè)成0和1。
我們可以這樣做，假設(shè)visited一維數(shù)組為[0 0 0 1 0]，表示第3位已經(jīng)遍歷過，轉(zhuǎn)成二進制表示為0b01000，轉(zhuǎn)成十進制表示為8。
我們看第0位是否是0，將visited與0b00001進行與運算，返回結(jié)果，如果結(jié)果為0說明沒有遍歷過；如果結(jié)果不為0遍歷過。
0b01000
& 0b00001
---------- => 8 & (2^0) = 0
0b00000
我們看第3位是否是0，將visited與0b01000進行與運算，返回結(jié)果。
0b01000
& 0b01000
---------- => 8 & (2^3) = 8
0b01000
可以總結(jié)為：
visited & (2^i) == 0 ? 未遍歷過 : 遍歷過; // visited表示一個數(shù)字，i 表示第幾位
2^i 也可以用 1<<i 表示
即:
visited & (1<<i) == 0 ? 未遍歷過 : 遍歷過;
那如何將某個節(jié)點設(shè)成1或0呢？
我們將第1位設(shè)為1，表示第1位剛遍歷過，
0b01000
+ 0b00010
---------- => 8 + (2^1) = 10
0b01010
注意：要提前判斷第1位是否為1，如果不是可以設(shè)為1，如果是則忽略。
將第2位設(shè)為1，表示第2位剛遍歷過，
0b01010
+ 0b00100
---------- => 10 + (2^2) = 14
0b01110
可以總結(jié)為：
// 如果第i位為0，設(shè)為1:
if(visited & (2^i) == 0) // visited表示一個數(shù)字，i 表示第幾位
visited += 2^i;
// 2^i 也可以用 1<<i 表示
if(visited & (1<<i) == 0)
visited += 1<<i;
同理，將第i為設(shè)為0，可以總結(jié)為：
// 如果第i位為1，設(shè)為0:
if(visited & (2^i) != 0) // visited表示一個數(shù)字，i 表示第幾位
visited -= 2^i;
// 2^i 也可以用 1<<i 表示
if(visited & (1<<i) != 0)
visited -= 1<<i;
舉一反三，學(xué)會了二進制數(shù)組壓縮成一個數(shù)字的狀態(tài)，多進制數(shù)組也同樣可以壓縮狀態(tài)，只需要找到最大的那個數(shù)就可以了。
如果找到最大的數(shù)為5，那就成六進制；如果找到最大的數(shù)為25，那就成二十六進制。如果數(shù)字確實比較大，也可以考慮最小的數(shù)，進行一一映射。
通過這樣的狀態(tài)壓縮，很多指數(shù)級別的空間復(fù)雜度直接降為O(1)，省空間了。
關(guān)注「算法無遺策」，一起領(lǐng)悟算法的魅力，大家加油 (●'?'●)
喜歡本文的朋友，微信搜索「算法無遺策」公眾號，收看更多精彩的算法動畫文章
