[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
解题思路
今天的题目比较简单,核心思路是将给定的整数 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 n
是n
的二进制位数空间复杂度:
O(1)
,我们只使用了一个常数空间来存储结果数组ans
总结
这道题目通过对整数 n
的二进制位进行逐位操作,统计在偶数和奇数下标上值为 1 的位数。尽管题目本身较为简单,但我们在具体实现上做了一些优化。通过使用异或操作 (^
) 来交替判断奇偶位,通过与运算 (n & 1
) 直接获取当前位的值,并使用右移操作 (n >>= 1)
) 提高了运算效率。这些操作使得代码更加简洁和高效。
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。