Java&C++题解与拓展——leetcode868.二进制间距【模拟么的新知识】

• 题目要求
• 思路：模拟
• • 从前向后遍历
  • • Java
    • C++
  • 从后向前遍历
  • • Java
    • C++
• 总结

简单题就没有什么好说的模拟，找每一个 1 1 1算距离记录最大值即可。

数据范围是 1 0 9 10^9 109，转成二进制就是30位，就从前往后逐位遍历找 1 1 1。

class Solution {
    public int binaryGap(int n) {
        int res = 0;
        for(int i = 29, j = -1; i >= 0; i--) { // 逐位遍历
            if(((n >> i) & 1) == 1) { // 是1
                if(j != -1)  // 上一个1的位置
                    res = Math.max(res, j - i);
                j = i;
            }
        }
        return res;
    }
}

• 时间复杂度： O ( log ⁡ n ) O(log n) O(logn)，遍历 n n n二进制的每一位
• 空间复杂度： O ( 1 ) O(1) O(1)

class Solution {
public:
    int binaryGap(int n) {
        int res = 0;
        for(int i = 29, j = -1; i >= 0; i--) {
            if(((n >> i) & 1) == 1) { // 是1
                if(j != -1) // 上一个1的位置
                    res = max(res, j - i);
                j = i;
            }
        }
        return res;
    }
};

• 时间复杂度： O ( log ⁡ n ) O(log n) O(logn)，遍历 n n n二进制的每一位
• 空间复杂度： O ( 1 ) O(1) O(1)

从末位开始取，逐位移动遍历，直至 n n n变为0。

class Solution {
    public int binaryGap(int n) {
        int res = 0, pre = -1, i = 0;
        while(n > 0) {
            if((n & 1) == 1) { // 是1
                if(pre != -1)  // 上一个1的位置
                    res = Math.max(res, i - pre);
                pre = i;
            }
            n >>= 1;
            i += 1;
        }
        return res;
    }
}

• 时间复杂度： O ( log ⁡ n ) O(log n) O(logn)，遍历 n n n二进制的每一位
• 空间复杂度： O ( 1 ) O(1) O(1)

class Solution {
public:
    int binaryGap(int n) {
        int res = 0, pre = -1, i = 0;
        while(n > 0) {
            if((n & 1) == 1) { // 是1
                if(pre != -1)  // 上一个1的位置
                    res = max(res, i - pre);
                pre = i;
            }
            n >>= 1;
            i += 1;
        }
        return res;
    }
};

• 时间复杂度： O ( log ⁡ n ) O(log n) O(logn)，遍历 n n n二进制的每一位
• 空间复杂度： O ( 1 ) O(1) O(1)

简单模拟题，光速解决，两种语言代码也基本没区别。

刚好可以去还了昨天的债，昨天的凸包还没有学好，太浪了太浪了……