文章

[LeetCode] 每日一题 2595. 奇偶位数

题目链接

https://leetcode.cn/problems/number-of-even-and-odd-bits

题目描述

给你一个 整数 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

解题思路

今天的题目比较简单,核心思路是将给定的整数 n 展开成二进制形式,并逐位判断其中奇偶位上值为 1 的个数。题目要求我们分别统计在偶数下标和奇数下标上值为 1 的位数

具体来说,关键点是:我们不需要精确知道每一位的值,只需要判断当前是偶数位还是奇数位,因此我们可以用 异或运算 来交替判断偶数位和奇数位。对于数字的逐位判断,我们通过与运算 (n & 1) 来获取当前位的值,而右移操作 (n >>= 1) 让我们可以快速处理下一位。这种方式不仅简洁,而且提高了运算效率,因为除2操作实际上就是二进制右移一位

代码实现

class Solution {
    public int[] evenOddBit(int n) {
        int[] ans = new int[2];
        for (int i = 0; n > 0; i ^= 1) { // 通过 i 异或操作交替处理奇偶位
            ans[i] += n & 1; // 获取当前位是否为 1
            n >>= 1; // 右移处理下一位
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度O(log n),因为我们对 n 进行右移操作,直到它变为 0。每次右移一位,相当于操作了 n 的每一位,因此时间复杂度为 O(log n),其中 log nn 的二进制位数

  • 空间复杂度O(1),我们只使用了一个常数空间来存储结果数组 ans

总结

这道题目通过对整数 n 的二进制位进行逐位操作,统计在偶数和奇数下标上值为 1 的位数。尽管题目本身较为简单,但我们在具体实现上做了一些优化。通过使用异或操作 (^) 来交替判断奇偶位,通过与运算 (n & 1) 直接获取当前位的值,并使用右移操作 (n >>= 1)) 提高了运算效率。这些操作使得代码更加简洁和高效。

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0