布尔值数组的状态压缩

今天做一个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)，省空间了。