经典算法实例应用：交替位二进制数（一）

我们先来看题目描述：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= n <= 231 - 1

解决方案

方法一：模拟

思路

从最低位至最高位，我们用对 2 取模再除以 2 的方法，依次求出输入的二进制表示的每一位，并与前一位进行比较。如果相同，则不符合条件；如果每次比较都不相同，则符合条件。

代码

Python3

class Solution: def hasAlternatingBits(self, n: int) -> bool: prev = 2 while n: cur = n % 2 if cur == prev: return False prev = cur n //= 2 return True

Java

class Solution { public boolean hasAlternatingBits(int n) { int prev = 2; while (n != 0) { int cur = n % 2; if (cur == prev) { return false; } prev = cur; n /= 2; } return true; }

C++

class Solution { public: bool hasAlternatingBits(int n) { int prev = 2; while (n != 0) { int cur = n % 2; if (cur == prev) { return false; } prev = cur; n /= 2; } return true; } };

C

#define MAX(a, b) ((a) > (b) ? (a) : (b)) int maxConsecutiveChar(const char * answerKey, int k, char ch) { int n = strlen(answerKey); int ans = 0; for (int left = 0, right = 0, sum = 0; right < n; right++) { sum += answerKey[right] != ch; while (sum > k) { sum -= answerKey[left++] != ch; } ans = MAX(ans, right - left + 1); } return ans; } int maxConsecutiveAnswers(char * answerKey, int k) { int cnt1 = maxConsecutiveChar(answerKey, k, 'T'); int cnt2 = maxConsecutiveChar(answerKey, k, 'F'); return MAX(cnt1, cnt2); }

复杂度分析

时间复杂度：O(logn) 。输入 n 的二进制表示最多有 O(logn) 位。

空间复杂度：O(1) 。使用了常数空间来存储中间变量。