【LeetCode 137. 只出现一次的数字 II】

这题有两个思路：

1）逐位考虑；

2）状态机；

先来看逐位考虑的思路：

如果对于 nums 中的每个数只观察某一位，因为除了一个数（后用 a 来代称）只出现了一次，其余的数都出现了三次，一位上的数字只有 0 或 1 ，对该位求和。该位上为 0 的数对和没有影响，该位上为 1 的数，会使得 1 加三次，那么如果不算 a 的该位，求出的和应该是 3 的倍数。那么怎么得到 a 的该位呢？显然就是考虑上 a 的该位进行求和，该和 % 3 的值就是 a 该位的值。

接下来考虑一些实现细节。因为逐位考虑，一定会用到移位。题目给出的条件（提示里）说明 a 至多三十二位，初始化为 0 ，这样只需要让是 1 的位变成 1 即可。每一位的处理分两步，先让 x （auto x : nums）右移 i 位（ i 从 0 开始递增），每次右移一位，只看从左往右最后一位的数字的累加情况（ 也就是移位操作后与上 1 ）。每次累加得到的数字对 3 取模，左移 i 位（对应原先在 a 中的位置），与初始化后的 a（ 三十二位全 0 ）相或，这样逐位将 a 中为 1 的位置赋为 1 。

代码实现：

初始化只出现了一次的数字每一位为 0 ；

        int res = 0;

每位处理时，初始化和为 0 ，累加；

            cnt = 0;for (auto x : nums) {cnt += (x >> i) & 1;}

还原原先在 res 中的位置（之前右移几位，现在就左移几位）；

            res |= (cnt % 3) << i;

完整循环展示：

        for (int i = 0, cnt; i < 32; i++) {cnt = 0;for (auto x : nums) {cnt += (x >> i) & 1;}res |= (cnt % 3) << i;}

返回 32 位处理结束后的 res；

        return res;

提交总览：

至此，逐位考虑法结束。

接下来，来看一看状态机是怎么实现的！

首先，这个状态机是干什么的？在逐位考虑这种方法里面，res 一开始被初始化为 0 ，从本质上而言，只需要找到 res 中为 1 的位就可以了，而逐位考虑法将 0 也考虑了，其实是冗余的。设计状态机的目的就是可不可以只考虑什么情况下可以筛出 res 该位为 1 ，其余无需考虑。

显然，对于这个状态机的每个状态有两种输入：0 和 1 。对于这个状态机的所有状态而言，输入 0 都不会发生状态转移，因为无需考虑 0 的影响；而对于输入 1 ，状态转移就很有意思了。初态 0 输入 1 ，说明有一个新的数字 x 来了，状态转移至状态一（诞生新状态）；状态一 又输入 1 ，连续输入的两个 1 说明这是一个出现三次的数字 x 出现的第二次，状态转移至 状态二（诞生新状态）；状态二又输入 1 ，连续输入的三个 1 说明这是一个出现三次的数字 x 出现的第三次，状态转移至状态三（诞生新状态）；状态三又输入 1 ，同一个数字 x 至多出现三次，这个新到的 1 说明是一个新的数字 y 来了，状态转移至状态一（无新状态产生）；结束。

不难发现找到新数字的总是状态一，而状态二和状态三得到的数字一定是出现三次的数字。是不是有思路了？先等一等，刚刚分析出的这个状态机的状态 0 和状态三是可以合并的，先化简一下。

前面说到状态 1 会找到每个新出现的数字，出现在状态 2 的数字则都是会出现三次的数字，状态机某一时刻只会出现在一种状态，需要考虑的就是怎么用表达式更新状态 1 和状态 2 的值。

处在状态 1 有两种方式和一个前提：

方式： 1）状态 0 状态输入 1 转移过来的（当前状态机不在状态 1 ）；2）状态 1 输入 0 回到状态 1

这两种方式总结一下，即状态 1 异或输入值为 1 ；

前提： 状态机不可能到达状态 2 ，即非状态 2 ；

处在状态 2 同样有两种方式和一个前提：

方式： 1）状态 1 状态输入 1 转移过来的（当前状态机不在状态 2 ）；2）状态 2 输入 0 回到状态 2

这两种方式总结一下，即状态 2 异或输入值为 1 ；

前提： 状态机虽然可能出现在状态 1 ，但是当转移到状态 2 后，状态机就不在状态 1 了，即非状态 1；

最终应该返回状态 1 的数字，因为新发现且不在状态 2 中。

代码实现：

申请状态 1 和状态 2 ，都初始化为 0 ；

        int once = 0, twice = 0;

按上述思路写出表达式；

        for (auto x : nums) {once = (x ^ once) & (~twice);twice = (x ^ twice) & (~once);}

返回遍历结束后状态 1 的数字；

        return once;

提交总览：

至此，状态机的方法结束。

【LeetCode 672. 灯泡开关 Ⅱ】

思路：

这道题虽然给出了四种操作，但是每种操作都是规律性地针对某类位置进行反转，也就是说同个操作进行两次等于无效操作。如果给出的操作次数大于等于四次，有效操作最多四次。

第一种操作的周期是一；第二种和第三种操作的周期是二；第四种操作的周期是三。

所以这四种操作的所有搭配方式用长度为六的周期足以展示。也就是说目前将分析的范围缩小到了 n 在一到六之间，presses 在零到四之间。

假设有效操作是四个，观察列举出来的情况。

可以发现前三个状态确定了，后面三个状态也就确定了，分析范围进一步缩小。此时，只需分析，n 在一到三之间，presses 在零到四之间。

枚举计算：

• 如果 presses = 0 ，那么就只有 1 种状态（灯都开着）。
• 否则如果 n = 1，那么有 2 种状态。
• 否则如果 n = 2 ，若 presses = 1，就有 3 种状态；若 presses >= 2，就有 4 种状态。
• 否则如果 n >= 3，若 m = 1，就有 4 种状态；若 m = 2，就有 7 种状态；若 m >= 3，就有 种 8 状态。

代码实现：

依照枚举结果写即可：

        if (presses == 0) return 1;if (n == 1) return 2;presses = min(presses , 3);if (n == 2) return vector<int>{3, 4, 4}[presses - 1];return vector<int>{4, 7, 8}[presses - 1];

提交总览：

【LeetCode 810. 黑板异或游戏】

首先，假设现在有 n 个互相不同的数：

1）如果 n 是偶数，alice必胜；

2）如果 n 是奇数，alice必输；

现在考虑含有相同数字的情况：

切片观察，对于某 m 个相同的值，如果 m 为偶数，就都留在存在相同数的阵营里；如果 m 为奇数，就选出一个数去 n 个互相不同的数的阵营里，其余留下。

对于存在相同数的阵营，bob 的最优选择就是不断拿走不重复的数字，因为两个人是回合制的，所以每次 bob 拿完都会剩下偶数个数字或者刚好拿完直接输掉；对于 alice 而言，最优选择就是让剩下的偶数个数字越来越接近偶数个互相不同的数字，这样拿下去，要么首次出现偶数个互相不同的数字，要么 bob 刚好拿完直接获胜；偶数个互相不同的数字前面分析过，alice 必胜。所以存在相同数阵营不可能导致 alice 输掉。

那么 alice 是否获胜取决于整体的 n 是否是偶数，或者考虑一种边界情况，所有的数一开始异或的结果就为 0 ，alice 开局就获胜。

代码实现：

判断整体的数字个数是否是偶数；

        if (!(nums.size() & 1)) return true;

边界情况；（这里初始化 i 为 0 是因为， 0 遇到 1 变成 1 ，0 遇到 0 还是 0 ，第一次可以加载数组的首个数字，同时后续维持异或逻辑）

        int i = 0;for (auto x : nums) i ^= x;return !i;

提交总览：

【LeetCode 861. 翻转矩阵后的得分】

思路：

每一行、每一列要么不翻转，要么翻转一次，再多是等价的，没有意义。

用贪心的思想：

要想最终和最大，第一列必须全为 1 。

证明很简单，对于任意一行，如果它的第一位是 1，那么这一位的二进制数值就是 2 的 n - 1 次方。反之如果这一位是 0 ，那么即使后面所有位全为 1，总数值也只能达到 2 的 n - 1 次方 - 1。所以第一位是一定要为 1 的。

这样就很简单了，每一行的翻转情况其实是确定的。如果第一位是 1，就不翻转，否则就翻转。

然后每一列还是看不翻转的 1 多，还是翻转后 1 多。

那么为啥不把每行第一位全翻转为 0 ，然后翻转第一列使得每行第一位全 1 呢？其实这样是等价的，相当于第一位是 1 翻转该行，第一位是 0 不翻转，每一列还是看不翻转的 1 多，还是翻转后 1 多。

代码实现：

记录矩阵列高和行宽；

        int height = grid.size(), width = grid[0].size();

对第一列进行遍历，遇到 0 ，翻转 0 所在的一整行；（这里翻转一行采用的是逐位异或 1）

        for (int i = 0; i < height; i++) {if (!grid[i][0]) {for (int j = 0; j < width; j++) {grid[i][j] ^= 1;}}}

计算第一列转十进制的数值，从每一行的角度来看最高位对应的数量级就是 width - 1 ，因为最低位对应的 2 的 0 次方。乘以 height 是因为按照上述思路第一列应该满 1 。

        int res = (1 << (width - 1)) * height;

初始化每列的 1 的个数为 0 ，计算每列的 1 的个数（其实就是每列求和，0 不影响）。

            cnt = 0;for (int h = 0; h < height; h++) {cnt += grid[h][k];}

如果 1 的个数少于翻转后的个数，取翻转后的个数进行转十进制的数值计算；

            cnt = max(cnt , height - cnt);res += (1 << (width - 1 - k)) * cnt;

循环整体如下：

        for (int k = 1, cnt; k < width; k++) {cnt = 0;for (int h = 0; h < height; h++) {cnt += grid[h][k];}cnt = max(cnt , height - cnt);res += (1 << (width - 1 - k)) * cnt;}

返回遍历结束后的 res；

        return res;

提交总览：

【LeetCode Offer 65. 不用加减乘除做加法】

思路：

因为不允许采用四则运算，所以只能考虑位运算了。

其实就是用二进制来模拟加法操作。首先将两个数最低位相加，如果都是 1 ，那么就得到 0 ，并且进位 1，然后接着算下一位。

但是这样一位一位模拟不方便实现，更简单的实现方法是直接把两个数对应位相加，不管进位。然后进位单独计算，如果某一位两个数都是 1 ，那么进位就会对下一位产生影响。然后接着算不进位求和加上进位的值，再计算新的进位，依次重复下去，直到进位为 0 为止。

用一个实际的例子来演示一下，计算 3 + 7 的值，其中 s 表示每一步不考虑进位的求和，c 表示每一步的进位，最后得到结果 1010 ，也就是十进制的 10 ：

因为是二进制，所以不考虑进位求和的话，可以直接采用异或运算。而计算进位的话，直接用位与和左移一位就行了。

代码实现：

当进位不为 0 时，先于异或计算进位的值，因为异或的值会赋给 a ，如果在异或之后计算进位，此时的 a 已经改变了；

int carry = (unsigned int) (a & b) << 1;

计算异或，并将之前计算的进位值赋给 b ，进入下一轮运算；

            a ^= b;b = carry;

完整循环如下：

        while(b) {int carry = (unsigned int) (a & b) << 1;a ^= b;b = carry;}

返回进位为 0 后（即运算终止后）的 a 值；

        return a;

提交总览：

至此，位运算系列结束！！