【刷题日记】693. 交替位二进制数

本次刷题日记的第 16 篇，力扣题为：67. 二进制求和 ，简单

一、题目描述：

下班回来瞅一眼力扣题，咱们顺手给他写了吧，保持良好的习惯，毕竟现在已经算是在赶作业了

看这个题要求还是非常明确的，又是一个处理二进制的题目，我们一起来看看吧

二、思路分析：

1、这道题考察了什么思想？你的思路是什么？

这道题给出了哪些重点信息呢：

• 题目给出的数据是一个正整数， 咱们处理起来就不需要考虑负数的情况
• 我们需要知道如何将整数转换成二进制，才能更好的处理这个题，如果是负数的话，我们还要处理高位补 1 的事情，不过这道题不需要

关于进制的题，我们都要想到辗转相除法，这是咱们小学的时候就学过的数学方法，现在来做编程题，很多都是数学思想，学好数学走遍天下

用题目中给出的示例，推演一下： n=11 的时候

• 11 除以 2 ，商 5 ， 余数为 1
• 5 除以 2 ，商 2 ，余数为 1
• 2 除以 2 ，商 1 ，余数为 0
• 1 除以 2 ，商 0 ，余数为 1
• 则 11 的二进制就是 1011

根据题中示意，需要二进制数，相邻两个数字不能是相等的，非  0 即 1 ，

则我们不仅要能算出二进制数，还需要筛选，那么问题咱们就可以转化成辗转相除法每一次的余数，是否和上一次的余数相等，

若相等，则不符合题意，若辗转到商 0 的时候，余数也与上一次余数不相等，则该数是符合题意的

接下来咱们就可以来翻译成代码了

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码如下：

func hasAlternatingBits(n int) bool {
 // 将入参给到临时变量，我们的编码原则是不能改变入参
 tmp := n
// 默认上一次余数为 2 ，因为咱们第一次辗转相除的时候，余数一定不可能是 2 ，所以第一次肯定不会等于 2 ，或者可以将 pre 赋值给大于 2 的数字也是可以的
 for pre := 2; tmp != 0; tmp /= 2 {
        yushu := tmp % 2
     // 校验本次的余数和上一次的余数是否相等
        if yushu == pre {
            return false
        }
     // 对上一次的余数进行赋值
        pre = yushu
    }
    return true
}

看了上述编码后就知道这个题还是非常简单的，但是思想也是相当重要的，无论做什么事情，基础要牢固

四、总结：

该题的时间复杂度，可不是 O(n) 哦，他是 O(logn) ， 因为我们的循环次数是整数转成二进制数的位数， 空间复杂度是 O(1)

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~