LeetCode 137 有限状态自动机解法原理详解
LeetCode 137 有限状态自动机解法原理详解
在LeetCode 137题中，有限状态自动机解法通过巧妙的位运算实现了对"只出现一次的数字"的高效查找。下面从状态定义、状态转移、数学原理三个层面详细解析：
一、状态机的核心定义
ones：记录出现1次的二进制位集合。
twos：记录出现2次的二进制位集合。
状态转移目标：
当数字第一次出现时，将对应位存入ones。
当数字第二次出现时，将对应位从ones移至twos。
当数字第三次出现时，将对应位从twos清零（即消除该数字的影响）。
二、状态转移方程解析
- ones = (ones ^ num) & ~twos
ones ^ num：
对ones和num进行异或运算，相当于：
若num的某一位为1且该位在ones中为0，则ones的该位变为1（数字第一次出现）。
若num的某一位为1且该位在ones中为1，则ones的该位变为0（数字第二次出现，准备移至twos）。
& ~twos：
用twos的按位取反进行与运算，确保：
若twos的某一位为1（数字已出现2次），则ones的该位强制置为0（避免重复记录）。
总结：
该操作实现了"数字第一次出现时记录到ones，第二次出现时从ones移除"的逻辑。 - twos = (twos ^ num) & ~ones
twos ^ num：
对twos和num进行异或运算，相当于：
若num的某一位为1且该位在twos中为0，则twos的该位变为1（数字第二次出现，从ones移至此）。
若num的某一位为1且该位在twos中为1，则twos的该位变为0（数字第三次出现，准备清零）。
& ~ones：
用ones的按位取反进行与运算，确保：
若ones的某一位为1（数字刚出现1次），则twos的该位强制置为0（防止提前记录）。
总结：
该操作实现了"数字第二次出现时记录到twos，第三次出现时从twos移除"的逻辑。
三、状态转移示例：数字出现三次
以数字x为例，分析其三位状态变化： - 第一次出现x
ones：0 ^ x = x，& ~twos（此时twos=0）→ ones = x
twos：0 ^ x = x，& ~ones（此时ones=x）→ twos = x & ~x = 0
状态：ones=x, twos=0（记录x出现1次） - 第二次出现x
ones：x ^ x = 0，& ~twos（twos=0）→ ones = 0
twos：0 ^ x = x，& ~ones（ones=0）→ twos = x
状态：ones=0, twos=x（记录x出现2次） - 第三次出现x
ones：0 ^ x = x，& ~twos（twos=x）→ x & ~x = 0
twos：x ^ x = 0，& ~ones（ones=0）→ 0 & ~0 = 0
状态：ones=0, twos=0（x的影响被消除）
四、数学原理：三进制计数器
该状态机本质上是一个三进制计数器，每一位的状态转移如下：
00（初始状态）→ 出现1次 → 01（ones=1）
01 → 出现1次 → 10（twos=1）
10 → 出现1次 → 00（清零）
用二进制位表示三进制状态：
ones：最低位（1的权值）
twos：次低位（3的权值）
每次出现数字时，对应位的三进制值加1，逢3进0。
五、位运算的逻辑等价性
状态转移方程可等价表示为：
cpp
运行
// 三进制计数器的数学表达
ones = (ones + num) % 3;
twos = (twos + num) % 3;
// 但位运算实现更高效，且等价于：
ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
证明：
当twos=0时：
ones = (ones ^ num) & ~0 = ones ^ num，等价于ones = (ones + num) % 3（当num=1时，0→1，1→0）。
当ones=0且twos=1时：
ones = (0 ^ num) & ~1 = num & 0 = 0，twos = (1 ^ num) & ~0 = 1 ^ num，等价于twos = (1 + num) % 3（num=1时，1→0）。
六、为什么最终结果是ones？
对于出现三次的数字：其所有二进制位在ones和twos中经历三次翻转后最终为0，不影响结果。
对于只出现一次的数字：其所有二进制位仅在ones中记录为1，twos中为0，因此ones即为该数字。
七、示例验证：nums = [2,2,3,2]
数字2出现三次，数字3出现一次。
二进制位分析（以最低两位为例）：
数字2：10
数字3：11
遍历过程：
处理2：ones=10, twos=00
处理2：ones=00, twos=10
处理2：ones=00, twos=00（2的影响消除）
处理3：ones=11, twos=00
最终ones=11，即数字3。
总结
该解法通过位运算模拟了三进制计数器的状态转移，实现了：
对每个数字的出现次数进行模3计数。
只保留出现一次的数字的二进制位。
时间复杂度O(n)，空间复杂度O(1)，是最优解法。
理解这种状态机思想，有助于解决类似的"出现k次"问题（如出现四次、五次等，只需扩展状态位）。