LeetCode 693. 交替位二进制数（详细解析 + 多解法实现）

LeetCode 693. 交替位二进制数详细解析 多解法实现前言LeetCode 693. 交替位二进制数是一道简单难度的位运算题目核心考察对二进制表示、位运算操作的理解与运用。本题看似简单但存在多种解题思路从直观的字符串判断到高效的位运算优化能充分体现“简单题多思路、多优化”的刷题思维。本文将从题目解析、思路推导、多解法代码实现严格遵循指定类结构、复杂度对比、常见坑点等方面全面拆解这道题适配CSDN技术博客实战风格附完整可运行代码和测试案例帮你吃透解题逻辑举一反三。适用人群算法入门者、位运算初学者、LeetCode刷题爱好者适合巩固二进制表示和位运算基础培养多思路解题能力。核心目录题目核心解析题干拆解 示例分析解题思路推导3种思路从直观到高效代码实现Python严格遵循指定类结构多解法对比复杂度分析时间 空间清晰对比常见坑点与避坑技巧拓展思考位运算同类题目延伸一、题目核心解析1.1 题干拆解题目给定一个正整数 n要求判断其二进制表示是否满足以下条件相邻两位的数字永不相同即呈现“0、1交替”的形式如101、1010而非111、1011。关键补充正整数的二进制表示不含前导0首位一定是1如5的二进制是101而非0101判断核心是“相邻两位不同”只需遍历二进制的每一位对比相邻两位即可题干提示 n 的范围是 1 ≤ n ≤ 2³¹ - 1无需考虑0和负数的情况避免边界处理冗余。1.2 示例深度分析示例1输入 n 5输出 true5 的二进制表示为101相邻两位分别是1和0不同、0和1不同满足交替条件返回true。示例2输入 n 7输出 false7 的二进制表示为111相邻两位分别是1和1相同、1和1相同不满足交替条件返回false。示例3输入 n 11输出 false11 的二进制表示为1011相邻两位分别是1和0不同、0和1不同、1和1相同存在相同相邻位返回false。1.3 题干隐含规律通过示例可提炼两个核心规律为后续优化思路提供支撑若二进制数交替则“当前位”与“下一位”一定不同可通过“逐位对比”或“位运算”快速判断交替位二进制数的一个重要特性将其右移1位后与原数进行异或XOR结果的二进制表示一定全为1如5→101右移1位→010异或结果→111若存在相邻相同位异或结果会出现0如7→111右移1位→011异或结果→100。二、解题思路推导3种思路从直观到高效本题有3种主流解题思路难度由浅入深从直观的字符串操作到高效的位运算优化适合不同基础的学习者下面逐一推导思路逻辑。2.1 思路1二进制字符串逐位对比最直观易理解核心逻辑将正整数 n 转换为二进制字符串遍历字符串的每一位对比当前位与下一位是否相同若存在任意一组相同返回false全部不同则返回true。具体步骤将 n 转换为二进制字符串Python中用 bin() 函数返回格式为 ‘0bxxxx’需截取[2:]去掉前缀遍历字符串从索引0到len(s)-2避免越界对比 s[i] 和 s[i1]若相等直接返回false遍历结束后若未发现相同相邻位返回true。优势与不足优势思路直观代码简洁无需掌握复杂位运算适合入门者不足需要转换为字符串存在一定的类型转换开销空间复杂度略高。2.2 思路2位运算逐位对比无字符串转换更高效核心逻辑不转换为字符串直接通过位运算获取二进制的每一位对比当前位与上一位是否相同。核心是用“与运算”获取当前位用“右移”依次获取每一位。具体步骤用变量 prev 记录上一位的二进制值初始为 n 的最低位即 n 1将 n 右移1位n n 1去掉最低位循环执行用 current n 1 获取当前最低位对比 current 与 prev若 current prev返回false否则更新 prev 为 current继续右移 n直到 n 变为0所有位都对比完毕返回true。优势与不足优势无字符串转换减少开销时间和空间复杂度更优不足需要掌握基础位运算、适合有一定位运算基础的学习者。2.3 思路3位运算优化一行代码最高效核心逻辑利用前文提炼的规律若 n 是交替位二进制数那么 n 与 n1 的异或结果x二进制表示全为1而全为1的二进制数 x满足 x (x1) 0如111 1000 0。反之若不满足该条件则 n 不是交替位二进制数。具体步骤极简计算 x n ^ (n 1)异或相同为0不同为1判断 x (x 1) 是否等于0等于则返回true否则返回false。逻辑验证结合示例1n 5二进制101n1 2二进制010x 101 ^ 010 111二进制x1 1000二进制111 1000 0 → 返回true。n 7二进制111n1 3二进制011x 111 ^ 011 100二进制x1 101100 101 100 ≠ 0 → 返回false。优势与不足优势代码极简一行核心逻辑时间复杂度O(1)位运算操作仅需固定几步与n的位数无关空间复杂度O(1)是最优解法不足思路较抽象需要理解异或的特性和全1二进制数的规律适合位运算进阶学习者。三、代码实现Python严格遵循指定类结构严格按照题干要求的类和方法格式实现上述3种思路附详细注释可直接复制到LeetCode提交均能通过所有测试用例。3.1 解法1二进制字符串逐位对比直观版核心转换为二进制字符串遍历对比相邻位易理解适合入门。classSolution:defhasAlternatingBits(self,n:int)-bool:# 将n转换为二进制字符串去掉前缀0bbinarybin(n)[2:]# 遍历字符串对比当前位与下一位foriinrange(len(binary)-1):# 若相邻两位相同直接返回falseifbinary[i]binary[i1]:returnFalse# 所有相邻位均不同返回truereturnTrue3.2 解法2位运算逐位对比高效版核心无字符串转换用位运算获取每一位对比相邻位性能优于解法1。classSolution:defhasAlternatingBits(self,n:int)-bool:# 特殊情况n1二进制为1无相邻位返回trueifn1:returnTrue# 记录上一位的二进制值最低位prevn1# 右移1位去掉最低位开始遍历剩余位nn1whilen0:# 获取当前最低位currentn1# 对比当前位与上一位相同则返回falseifcurrentprev:returnFalse# 更新上一位为当前位继续右移prevcurrent nn1# 所有位对比完毕无相同相邻位返回truereturnTrue3.3 解法3位运算优化极简版最优解核心利用异或特性和全1二进制数的规律一行核心代码最高效。classSolution:defhasAlternatingBits(self,n:int)-bool:# 核心逻辑n与n1异或若结果全为1则x(x1)0xn^(n1)return(x(x1))03.4 测试案例验证将题目示例和额外测试用例代入验证3种解法的正确性所有解法输出均一致# 测试示例1n15print(Solution().hasAlternatingBits(n1))# 输出True二进制101# 测试示例2n27print(Solution().hasAlternatingBits(n2))# 输出False二进制111# 测试示例3n311print(Solution().hasAlternatingBits(n3))# 输出False二进制1011# 额外测试用例n41# 二进制1print(Solution().hasAlternatingBits(n4))# 输出Truen52# 二进制10print(Solution().hasAlternatingBits(n5))# 输出Truen63# 二进制11print(Solution().hasAlternatingBits(n6))# 输出Falsen710# 二进制1010print(Solution().hasAlternatingBits(n7))# 输出True四、复杂度分析3种解法对比明确对比3种解法的时间和空间复杂度帮助选择适合自己的实现方式结合题干n的范围≤2³¹-1所有解法均能高效运行。解法时间复杂度空间复杂度核心说明解法1字符串对比O(log n)O(log n)n的二进制位数为log₂n字符串长度为log₂n遍历和存储均需O(log n)开销解法2位运算逐位对比O(log n)O(1)需遍历n的二进制每一位log₂n位仅用常数个变量无额外空间开销解法3位运算优化O(1)O(1)仅需3次位运算右移、异或、与运算与n的位数无关最优解补充说明题干中n的最大值为2³¹-1二进制位数仅31位因此即使是O(log n)的解法实际运算量也极小三种解法在LeetCode上的执行用时几乎无差异但解法3的理论性能最优。五、常见坑点与避坑技巧坑点1忽略n1的特殊情况导致循环不执行但返回错误结果。避坑n1的二进制是“1”无相邻位属于满足条件的情况需单独判断解法2已处理解法1和3无需单独处理因字符串长度为1遍历不执行直接返回true。坑点2转换二进制字符串时忘记去掉前缀“0b”导致遍历对比时出现错误。避坑Python的bin()函数返回格式为“0bxxxx”必须截取[2:]部分才能得到正确的二进制字符串解法1已处理。坑点3位运算时右移操作后未判断n是否为0导致死循环。避坑解法2中循环条件设为n0右移后n会逐渐变为0循环正常终止。坑点4误解“交替位”的含义认为“开头可以是0”导致判断错误。避坑正整数的二进制表示首位一定是1不存在开头为0的情况无需考虑此类场景。坑点5解法3中遗漏括号导致运算优先级错误如x x 1先执行再执行导致结果错误。避坑必须给(x 1)加括号确保先执行加法再执行与运算解法3已处理。六、拓展思考6.1 同类题目延伸本题的位运算思路可迁移到以下同类题目核心都是“二进制位判断”和“位运算运用”LeetCode 461. 汉明距离计算两个整数二进制表示中不同位的个数核心用异或统计1的个数LeetCode 191. 位1的个数统计一个整数二进制表示中1的个数核心用与运算右移LeetCode 67. 二进制求和实现两个二进制字符串的加法可结合本题的二进制遍历思路。6.2 思路拓展解法3的核心是“利用二进制特性简化计算”这种思路在位运算题目中非常常用。例如判断一个数是否为2的幂n (n-1) 0与本题解法3的思路异曲同工判断一个数是否为4的幂(n (n-1) 0) and (n 0x55555555 ! 0)结合二进制特性。掌握这类“二进制特性位运算”的思路能快速解决大量位运算相关的简单/中等难度题目。七、总结LeetCode 693. 交替位二进制数虽然是简单题但包含多种解题思路从直观的字符串对比到位运算优化能充分锻炼多思路解题能力。核心总结入门首选解法1字符串对比思路直观无需掌握位运算进阶首选解法2位运算逐位对比无字符串转换性能更优巩固位运算基础最优解选解法3位运算优化代码极简时间空间复杂度均为O(1)体现位运算的精髓。本题的关键是理解“交替位”的核心的是“相邻两位不同”无论是字符串遍历还是位运算都是围绕这一核心展开。刷题时不要满足于一种解法多尝试不同思路能更好地巩固知识点提升解题能力。所有解法均经过LeetCode测试可直接提交通过。如果在刷题过程中遇到问题可结合本文的坑点提示排查也可延伸练习同类位运算题目举一反三。创作不易如果你觉得本文对你有帮助欢迎点赞、收藏、评论你的支持是我持续创作LeetCode解析的动力