693.交替位二进制数

LeetCode LeetCode 位运算

发布时间 : 2000-01-10 06:09

字数:1.4k 阅读 :

评论:

693.交替位二进制数

693.交替位二进制数

693.1 题目

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：

输入：n = 5
输出：true
解释：5 的二进制表示是：101

示例 2：

输入：n = 7
输出：false
解释：7 的二进制表示是：111

示例 3：

输入：n = 11
输出：false
解释：11 的二进制表示是：1011

提示：

1 <= n <= 2^31 - 1

693.2 题解

方法一：位运算判断相邻位是否相同

思路

如果 n 的二进制位交替出现，则 n ^ (n >> 1) 的结果全为 1。全 1 的数加 1 后变成 2 的幂（只有一个 1），与原数相与结果为 0。利用这个性质判断。

核心思想：交替二进制数异或右移后全为1，加1后与原数相与为0。

具体步骤：

计算 a = n ^ (n >> 1)。
判断 (a & (a + 1)) == 0。

举例：对于 n = 5（二进制 101）：

n >> 1 = 10（二进制 010）
n ^ (n >> 1) = 101 ^ 010 = 111
a + 1 = 1000
a & (a + 1) = 111 & 1000 = 0
返回 true

复杂度分析

时间复杂度：O(1)，常数次位运算。
空间复杂度：O(1)，无额外空间。

代码

// 方法一：位运算判断相邻位是否相同
static bool HasAlternatingBits1(int n)
{
    // 使用异或运算判断相邻位是否相同
    // 如果 n 和 n 右移一位的结果进行异或运算得到的结果，再加一，结果为2的幂，则返回 true，否则返回 false
    // n 如果相邻为是交替的 n ^ (n >> 1)得到的是全是1   比如 101  010 异或后变成111
    // 全是1的数+1 得首位为1 后面都是0 111 + 1  1000
    // 在做与全是1的数与 应该是0  000
    int a = n ^ (n >> 1);
    return (a & (a + 1)) == 0;
}

方法二：遍历检查相邻位是否相同

思路

将 n 转换为二进制字符串，遍历检查相邻字符是否相同。如果发现相邻位相同，则不是交替二进制数。

核心思想：遍历二进制字符串，检查相邻位是否相同。

具体步骤：

将 n 转换为二进制字符串。
遍历字符串，检查相邻字符是否相同。
如果发现相同，返回 false。

举例：对于 n = 7（二进制 111）：

i=1：binary[1] = '1' == binary[0] = '1'
返回 false

复杂度分析

时间复杂度：O(log n)，二进制字符串长度。
空间复杂度：O(log n)，存储二进制字符串。

代码

// 方法二：遍历检查相邻位是否相同
static bool HasAlternatingBits2(int n)
{
    // 将 n 转换为二进制字符串
    string binary = Convert.ToString(n, 2);

    // 遍历二进制字符串，检查相邻位是否相同
    for (int i = 1; i < binary.Length; i++)
    {
        // 如果相邻位相同，则返回 false
        if (binary[i] == binary[i - 1])
        {
            return false;
        }
    }

    // 如果所有相邻位都不相同，则返回 true
    return true;
}

693.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

        // 示例 1：
        // 输入：n = 5
        // 输出：true
        // 解释：5 的二进制表示是：101

        // 示例 2：
        // 输入：n = 7
        // 输出：false
        // 解释：7 的二进制表示是：111

        // 示例 3：
        // 输入：n = 11
        // 输出：false
        // 解释：11 的二进制表示是：1011

        // 提示：
        // 1 <= n <= 2^31 - 1

        #endregion

        #region 测试

        // 示例 1
        int n1 = 5;
        bool result1_1 = HasAlternatingBits1(n1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        bool result1_2 = HasAlternatingBits2(n1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int n2 = 7;
        bool result2_1 = HasAlternatingBits1(n2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        bool result2_2 = HasAlternatingBits2(n2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        int n3 = 11;
        bool result3_1 = HasAlternatingBits1(n3);
        Console.WriteLine($"示例3 方法1 输出：{result3_1}");
        bool result3_2 = HasAlternatingBits2(n3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：位运算判断相邻位是否相同
    static bool HasAlternatingBits1(int n)
    {
        // 使用异或运算判断相邻位是否相同
        // 如果 n 和 n 右移一位的结果进行异或运算得到的结果，再加一，结果为2的幂，则返回 true，否则返回 false
        // n 如果相邻为是交替的 n ^ (n >> 1)得到的是全是1   比如 101  010 异或后变成111
        // 全是1的数+1 得首位为1 后面都是0 111 + 1  1000
        // 在做与全是1的数与 应该是0  000
        int a = n ^ (n >> 1);
        return (a & (a + 1)) == 0;
    }

    // 方法二：遍历检查相邻位是否相同
    static bool HasAlternatingBits2(int n)
    {
        // 将 n 转换为二进制字符串
        string binary = Convert.ToString(n, 2);

        // 遍历二进制字符串，检查相邻位是否相同
        for (int i = 1; i < binary.Length; i++)
        {
            // 如果相邻位相同，则返回 false
            if (binary[i] == binary[i - 1])
            {
                return false;
            }
        }

        // 如果所有相邻位都不相同，则返回 true
        return true;
    }

    #endregion
}

693.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
示例3 方法1 输出：False
示例3 方法2 输出：False

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com