今天做一个LeetCode题发现一个小技巧，特来与你们分享一下。
做的LeetCode题是关于二维矩阵的图论建模，像下面这样的：
二维矩阵可以不产生一个图结构，直接在二维矩阵上计算。相应地，会设定一个布尔值数组visited[ i ] [ j ]，表示某一个位置是否被遍历，true表示被遍历，false表示未被遍历。
我们首先看看图论建模是如何建模的， 二维数组会有两个索引下标i和j，分别对阵为行和列。我们会设定一个常量C，而这个常量正是列的长度，即nums[i].length。
对二维矩阵每一个位置都可以用 i * C + j 表示，如下图：
如果图结构想转换成二维矩阵也可以这样表示，假设图结构的一个节点的键为g，位于二维矩阵的，第几行用 g / C 表示，第几列用 g % C 表示。
i = g / C; // 获得第几行
j = g % C; // 获得第几列
三维矩阵也是通过这样的方式进行图论建模，会设定两个常量，一个是 j 的长度，另一个是 i 和 j 的面积。这里就不进行多介绍了，因为本篇介绍布尔值数组压缩状态的小技巧，再讲三维矩阵的图论建模就偏了，了解二维矩阵就好了。
在进行二维矩阵的图论建模中，如果不转成图形结构，直接在二维矩阵上计算，我们会设定一个布尔类型的二维数组visited，数组的值表示图的某个节点是否遍历过。
接着我们可以把true看作是1，false看作是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 0
]
然后可以把这看作是二进制，将一维数组直接转成一个数字。
最重要的是，转成了一个数字，如何查看某个节点是否被遍历过，又如何将某个节点设成0和1。
我们可以这样做，假设visited一维数组为[0 0 0 1 0]，表示第3位已经遍历过，转成二进制表示为0b01000，转成十进制表示为8。
我们看第0位是否是0，将visited与0b00001进行与运算，返回结果，如果结果为0说明没有遍历过；如果结果不为0遍历过。
0b01000
& 0b00001
---------- => 8 & (2^0) = 0
0b00000
我们看第3位是否是0，将visited与0b01000进行与运算，返回结果。
0b01000
& 0b01000
---------- => 8 & (2^3) = 8
0b01000
可以总结为：
visited & (2^i) == 0 ? 未遍历过 : 遍历过; // visited表示一个数字，i 表示第几位
2^i 也可以用 1<<i 表示
即:
visited & (1<<i) == 0 ? 未遍历过 : 遍历过;
那如何将某个节点设成1或0呢？
我们将第1位设为1，表示第1位刚遍历过，
0b01000
+ 0b00010
---------- => 8 + (2^1) = 10
0b01010
注意：要提前判断第1位是否为1，如果不是可以设为1，如果是则忽略。
将第2位设为1，表示第2位刚遍历过，
0b01010
+ 0b00100
---------- => 10 + (2^2) = 14
0b01110
可以总结为：
// 如果第i位为0，设为1:
if(visited & (2^i) == 0) // visited表示一个数字，i 表示第几位
visited += 2^i;
// 2^i 也可以用 1<<i 表示
if(visited & (1<<i) == 0)
visited += 1<<i;
同理，将第i为设为0，可以总结为：
// 如果第i位为1，设为0:
if(visited & (2^i) != 0) // visited表示一个数字，i 表示第几位
visited -= 2^i;
// 2^i 也可以用 1<<i 表示
if(visited & (1<<i) != 0)
visited -= 1<<i;
举一反三，学会了二进制数组压缩成一个数字的状态，多进制数组也同样可以压缩状态，只需要找到最大的那个数就可以了。
如果找到最大的数为5，那就成六进制；如果找到最大的数为25，那就成二十六进制。如果数字确实比较大，也可以考虑最小的数，进行一一映射。
通过这样的状态压缩，很多指数级别的空间复杂度直接降为O(1)，省空间了。
关注「算法无遗策」，一起领悟算法的魅力，大家加油 (●'◡'●)
喜欢本文的朋友，微信搜索「算法无遗策」公众号，收看更多精彩的算法动画文章
