LC 2568. 最小无法得到的或值
https://leetcode.cn/problems/minimum-impossible-or/
这题几乎完全没有思路,我觉得 题解 说的非常透彻:
- 如果1不在里面的话,那么就是1
- 如果2不在里面的话,那么就是2
- 此时有1,2,那么肯定有3. 如果4不在里面的话,那么就是4
- 此时5,6,7,就也都有了,接着就是8
这么来说就是第一个 `1<<i` 的数如果不出现的其中的话,那么就是它了。
然后题解里面还给了一个更牛的办法,就是只考虑 `1<<i` 的数,然后取最低位没有使用的bit `x & ~x`
class Solution: def minImpossibleOR(self, nums: List[int]) -> int: mask = 0 for x in nums: if (x & (x - 1)) == 0: # x 是 2 的幂次 mask |= x mask = ~mask # 没有使用的bit return mask & -mask # lowbit