【每日一题】Leetcode 2595. 奇偶位数

【每日一题】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

思路 1：（时间复杂度$O(log(n))$）

1. 位运算：判断当前值是否能余 2 为 0，能的话说明二进制当前位为 1 ，需要被统计。
2. 首先记录当前是奇数位还是偶数位的值，并每次右移当前值，同时判断余 2 。

代码 1：（时间复杂度$O(log(n))$）

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        even = 0
        odd = 0
        bit = 1

        while n:
            if n % 2 != 0:
                if bit % 2 != 0:
                    even += 1
                else:
                    odd += 1
            bit += 1
            n >>= 1

        return [even, odd]

代码 2：（和代码 1 的思路一致，只是优化了记录当前奇偶位的方法，时间复杂度$O(log(n))$）

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        res = [0, 0]
        i = 0
        while n:
            res[i] += n & 1 # 判断 n 是否是偶数，例如 2 & 1 = 0, 3 & 1 = 1
            n >>= 1
            i = i ^ 1 # 使用异或记录当前奇偶位
        return res

感谢浏览，欢迎关注祁彧w博客！