LC 2595.Number of Even and Odd Bits

题目描述

这是 LeetCode 上的 2595. 奇偶位数 ，难度为简单。

给你一个 正 整数 n 。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。

返回整数数组 answer ，其中 answer = [even, odd] 。

示例 1：

输入：n = 17
输出：[2,0]
解释：17 的二进制形式是 10001 。 
下标 0 和 下标 4 对应的值为 1 。 
共有 2 个偶数下标，0 个奇数下标。

示例 2：

输入：n = 2
输出：[0,1]
解释：2 的二进制形式是 10 。 
下标 1 对应的值为 1 。 
共有 0 个偶数下标，1 个奇数下标。

提示：

• 1 <= n <= 1000

解答

方法一：模拟

根据题意按位判断，最后统计奇偶的个数。

class Solution {
    public int[] evenOddBit(int n) {
        int i = 1, odd = 0, even = 0;
        while (i != 0) {
            if ((n & i) != 0) {
                ++even;
            }
            i <<= 2;
        }
        i = 2;
        while (i != 0) {
            if ((n & i) != 0) {
                ++odd;
            }
            i <<= 2;
        }
        return new int[]{even, odd};
    }
}

• 时间复杂度：\(O(N)\)，其中 N 为 n 的位数。

• 空间复杂度：\(O(1)\)。

方法二：模拟改进

可以改进模拟的写法，使其更加简洁。

class Solution {
    public int[] evenOddBit(int n) {
        var ans = new int[2];
        for (int i = 0; n > 0; i ^= 1, n >>= 1)
        {
            ans[i] += n & 1;
        }
        return ans;
    }
}

• 时间复杂度：\(O(\log N)\)，其中 N 为 n 的位数。

• 空间复杂度：\(O(1)\)。

方法三：位掩码 + 库函数

@Source:题解来源

利用位掩码 0x55555555（二进制的 010101⋯），取出偶数下标比特和奇数下标比特，分别用库函数统计 1 的个数。

本题由于 n 范围比较小，取 0x5555 作为位掩码。

class Solution {
    public int[] evenOddBit(int n) {
        final int MASK = 0x5555;
        return new int[]{Integer.bitCount(n & MASK), Integer.bitCount(n & (MASK >> 1))};
    }
}

• 时间复杂度：\(O(1)\)。

• 空间复杂度：\(O(1)\)。

每题一图