检查按位或是否存在尾随零

难度: Easy

给你一个 正整数 数组 nums 。

你需要检查是否可以从数组中选出 两个或更多 元素，满足这些元素的按位或运算（ OR）结果的二进制表示中至少存在一个尾随零。

例如，数字 5 的二进制表示是 "101"，不存在尾随零，而数字 4 的二进制表示是 "100"，存在两个尾随零。

如果可以选择两个或更多元素，其按位或运算结果存在尾随零，返回 true；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110" ，存在一个尾随零。

示例 2：

输入：nums = [2,4,8,16]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110"，存在一个尾随零。
其他按位或运算结果存在尾随零的可能选择方案包括：(2, 8), (2, 16), (4, 8), (4, 16), (8, 16), (2, 4, 8), (2, 4, 16), (2, 8, 16), (4, 8, 16), 以及 (2, 4, 8, 16) 。

示例 3：

输入：nums = [1,3,5,7,9]
输出：false
解释：不存在按位或运算结果存在尾随零的选择方案。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 100

Submission

运行时间: 20 ms

内存: 16.5 MB

class Solution:
    def hasTrailingZeros(self, nums: List[int]) -> bool:
        l00=[]
        l10=[]
        for i in nums :
            if i&1==0 : 
                if i>>1&1==0 :
                    l00.append(i)
                else : l10.append(i)
        return len(l10)>1 or len(l00)*len(l10)!=0 or len(l00)>1

Explain

题解首先区分了输入数组中的数的最低两位二进制的情况。将数分为两类：l00（最低两位都是0，例如 '100'）和 l10（最低位是0，次低位是1，例如 '010'）。这种分类是因为两个数的按位或操作中，如果任一数在某一位上是0，这一位的结果将由另一数决定；如果两个数在某一位都是1，则结果在该位也是1。因此，如果想要在结果中得到尾随零，至少需要一个数在最低位是0。具体来说， 1. 如果至少有两个数属于l10，它们的按位或结果的最低位肯定是0（因为两者最低位都是0）。 2. 任何一个l00和一个l10组合的按位或结果也必定在最低位有0（同样，因为这些数的最低位都是0）。 3. 如果l00中至少有两个元素，它们的按位或结果也至少有一个尾随零。因此，只要以上三种情形中的任意一种成立，就可以返回true，否则返回false。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def hasTrailingZeros(self, nums: List[int]) -> bool:
        l00=[]  # 存储最低两位都是0的数
        l10=[]  # 存储最低位是0但次低位是1的数
        for i in nums:  # 遍历数组
            if i & 1 == 0:  # 如果最低位是0
                if i >> 1 & 1 == 0:  # 检查次低位是否也是0
                    l00.append(i)  # 是的话，加入l00
                else:  # 否则只有最低位是0，次低位是1
                    l10.append(i)  # 加入l10
        # 判断是否存在尾随零的按位或结果的情况
        return len(l10) > 1 or len(l00) * len(l10) != 0 or len(l00) > 1

Explore

题解中的分类方法基于二进制运算的原则，尤其关注按位或操作的特性。按位或操作（|）对于任意两个数的同一位来说，只要其中至少有一个为1，结果就为1。反之，如果两个数在某一位上都是0，结果在该位上也是0。最后两位的分类是因为题目关注尾随零，即结果的最低位是否为0。通过判断数字的最低两位，可以有效预测按位或操作后的最低位和次低位的结果，从而判断是否能够产生尾随零。

题解主要分类为l00和l10，这两类都保证了最低位是0，这是判断尾随零的关键条件。实际上，如果一个数字最低位是0，无论次低位是1还是0，都有可能贡献尾随零。题解中没有特别提到次低位不是1的其他数字是因为，这些数字（次低位为0）已经被包含在l00中。因此，不需要额外分类，已经覆盖了所有可能的情况，不会影响最终的输出。

如果有超过一个数字属于l10类（最低位是0，次低位是1），这意味着至少有两个数字的最低位都是0。在进行按位或操作时，只要参与运算的两个数在某一位都是0，则结果在该位也是0。因此，如果有两个或更多的l10数字，它们的按位或操作在最低位的结果必然是0（即存在尾随零），因为所有l10数字的最低位都是0。

这个条件检查是否至少有一个数字属于l00（最低两位都是0）和至少一个数字属于l10（最低位是0，次低位是1）。只要存在至少一个l00和一个l10，无论l10的次低位状态如何，与l00的按位或操作都会在最低位产生0（因为l00的最低两位都是0，确保了与任何其他数的按位或在最低位为0）。因此，这种组合保证了按位或的结果至少有一个尾随零。