奇偶位数

难度:

标签:

题目描述

You are given a positive integer n.

Let even denote the number of even indices in the binary representation of n (0-indexed) with value 1.

Let odd denote the number of odd indices in the binary representation of n (0-indexed) with value 1.

Return an integer array answer where answer = [even, odd].

Example 1:

Input: n = 17
Output: [2,0]
Explanation: The binary representation of 17 is 10001. 
It contains 1 on the 0^th and 4^th indices. 
There are 2 even and 0 odd indices.

Example 2:

Input: n = 2
Output: [0,1]
Explanation: The binary representation of 2 is 10.
It contains 1 on the 1^st index. 
There are 0 even and 1 odd indices.

Constraints:

1 <= n <= 1000

代码结果

运行时间: 20 ms, 内存: 16.1 MB

/*
 * 思路：
 * 1. 将正整数 n 转换为二进制字符串。
 * 2. 使用 Java Stream 处理字符串并统计偶数下标和奇数下标的 '1' 的个数。
 * 3. 将统计结果以数组形式返回。
 */
import java.util.stream.IntStream;

public class Solution {
    public int[] evenOddCount(int n) {
        String binaryString = Integer.toBinaryString(n);
        int even = (int) IntStream.range(0, binaryString.length())
                .filter(i -> i % 2 == 0 && binaryString.charAt(i) == '1')
                .count();
        int odd = (int) IntStream.range(0, binaryString.length())
                .filter(i -> i % 2 != 0 && binaryString.charAt(i) == '1')
                .count();
        return new int[]{even, odd};
    }
}

解释

方法:

该题解通过遍历整数 n 的二进制位来统计奇数位和偶数位上值为 1 的位的数量。使用一个循环，每次迭代检查 n 的最低位（n & 1），根据当前位的下标是奇数还是偶数（通过计数器 cnt 实现），更新奇数位或偶数位的计数器。每次迭代后，n 右移一位（n >>= 1），即去掉已经检查过的最低位，同时计数器 cnt 自增1，直到 n 为 0。

时间复杂度:

O(log n)

空间复杂度:

O(1)

代码细节讲解

🦆

在实现过程中，为什么选择使用位运算（n & 1）来检查最低位的值？

▷

位运算（n & 1）用来检查整数 n 的最低位是否为 1 是因为这种操作非常高效和直接。这个运算符会与二进制的 1 进行 AND 操作，这样仅当 n 的最低位是 1 时，结果才为 1（即真），如果是 0 则结果为 0（即假）。这种方法直接对应到二进制位的检查，无需进行其他转换或复杂计算，因此是处理二进制数据的常用技巧。

🦆

题解中提到每次迭代后将 n 右移一位（n >>= 1），这种操作是否可能导致某些情况下遗漏检查某些位的值？

▷

在这种实现中，每次迭代将 n 右移一位（n >>= 1）不会导致遗漏检查某些位的值。右移操作使得 n 的当前最低位被丢弃，而下一位变为新的最低位。这个过程会持续进行，直到 n 变为 0。每次迭代中，都会检查当时的最低位，然后移除它，因此所有位都会依次被检查一次，不会有遗漏。

🦆

变量 cnt 的初始值为0，这样设置的原因是什么？对于二进制位的计数来说，从0开始和从1开始有何区别？

▷

变量 cnt 的初始值设为 0 是因为在二进制计数中，最低位（最右边的位）通常被认为是第 0 位。这种从 0 开始的索引方式是在编程中常见的，它使得位的索引与数组和其他数据结构的索引方式保持一致。从 0 开始和从 1 开始的主要区别在于位的编号方式，前者使得偶数位的索引为偶数（例如第 0 位、第 2 位等），而后者则会使得偶数位的索引为奇数（例如第 1 位、第 3 位等），这会影响如何判断当前位是奇数位还是偶数位。

🦆

在题解的代码中没有特别处理 n=0 的情况，这样处理是否适当？

▷

在题解的代码中不需要特别处理 n=0 的情况，因为当 n=0 时，循环条件 `while n:` 不成立，循环体不会被执行。这意味着如果 n 的初始值为 0，函数将直接返回偶数位和奇数位计数器的初始值 [0, 0]。这种处理是适当的，因为如果 n 为 0，则它没有任何为 1 的位，因此偶数位和奇数位的计数都应该是 0。

奇偶位数

题目描述

代码结果

解释

代码细节讲解

相关问题