网站推广设计做哪些,设置自动删除的wordpress,检察门户网站 建设意义,网站开发培训流程❓693. 交替位二进制数
难度#xff1a;简单
给定一个正整数#xff0c;检查它的二进制表示是否总是 0、1 交替出现#xff1a;换句话说#xff0c;就是二进制表示中相邻两位的数字永不相同。
示例 1#xff1a; 输入#xff1a;n 5 输出#xff1a;true 解释#…❓693. 交替位二进制数
难度简单
给定一个正整数检查它的二进制表示是否总是 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 1 n 2^{31} - 1 1n231−1
思路
基础知识必知一篇文章搞懂位运算
法一数学
将n转换成二进制以10结尾的数然后使用数学除法除以 4判断余数的二进制是否为10对应的十进制为 2如果不是则不是交替位二进制数返回false。
法二位运算 对于 1010 这种位级表示的数把它向右移动 1 位得到 101这两个数每个位都不同因此异或得到的结果为 1111。 对输入 n 的二进制表示右移一位后得到的数字再与 n 按位异或得到 a。 当且仅当输入 n 为交替位二进制数时a 的二进制表示全为 111不包括前导 000。 将 a 与 a1 按位与当且仅当 a 的二进制表示全为 1 时结果为 0。
结合上述两步可以判断输入是否为交替位二进制数。
代码(Java、C)
法一数学 Java
class Solution {public boolean hasAlternatingBits(int n) {if((n (-n)) 1) n 1;while(n 0){if(n % 4 ! 2) return false;n / 4;}return true;}
}C
class Solution {
public:bool hasAlternatingBits(int n) {if((n (-n)) 1) n 1;while(n 0){if(n % 4 ! 2) return false;n / 4;}return true;}
};法二位运算 Java
class Solution {public boolean hasAlternatingBits(int n) {int a (n ^ (n 1));return (a (a 1)) 0;}
}C
class Solution {
public:bool hasAlternatingBits(int n) {long a (n ^ (n 1));return (a (a 1)) 0;}
};运行结果 复杂度分析
时间复杂度 O ( 1 ) O(1) O(1)仅使用了常数时间来计算。空间复杂度 O ( 1 ) O(1) O(1)使用了常数空间来存储中间变量。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我 leetCode专栏每日更新 注 如有不足欢迎指正
