4092. 二进制位得分

难度简单

题目描述

给你两个整数 a 和 b。

设 s1 和 s2 分别为 a 和 b 的二进制表示中置位的数量。

这两个整数的得分定义如下：

如果 s1 >= s2，则得分为 s1 * s2。
否则，得分为 s2 / s1，其中除法采用整数除法。

返回一个整数，表示 a 和 b 的得分。

置位是指数的二进制表示中值为 1 的位。

示例 1：

输入： a = 14, b = 6

输出： 6

解释：

a = 14 的二进制表示为 "1110"，因此 s1 = 3。
b = 6 的二进制表示为 "110"，因此 s2 = 2。
由于 s1 > s2，a 和 b 的得分为 s1 * s2 = 3 * 2 = 6。

示例 2：

输入： a = 5, b = 15

输出： 2

解释：

a = 5 的二进制表示为 "101"，因此 s1 = 2。
b = 15 的二进制表示为 "1111"，因此 s2 = 4。
由于 s1 < s2，a 和 b 的得分为 s2 / s1 = 4 / 2 = 2。

示例 3：

输入： a = 10, b = 12

输出： 4

解释：

a = 10 的二进制表示为 "1010"，因此 s1 = 2。
b = 12 的二进制表示为 "1100"，因此 s2 = 2。
由于 s1 == s2，a 和 b 的得分为 s1 * s2 = 2 * 2 = 4。

提示：

1 <= a, b <= 100

解法

方法一：位计数

思考

\(a\) 和 \(b\) 都不超过 \(100\)，二进制里 \(1\) 的个数可以直接数出来。得分只由两个置位数的大小关系决定。

\(s_1\ge s_2\) 时得分是乘积，否则是 \(s_2\) 对 \(s_1\) 的整数商。两个数都至少为 \(1\)，\(s_1\) 不会是 \(0\)。

分别做一次位计数，再按这个大小关系返回即可。

记 \(s_1\)、\(s_2\) 分别为 \(a\)、\(b\) 的二进制表示中 \(1\) 的个数。若 \(s_1\ge s_2\)，得分为 \(s_1\cdot s_2\)；否则得分为 \(s_2/s_1\) 的整数商。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def calculateScore(self, a: int, b: int) -> int:
        s1 = a.bit_count()
        s2 = b.bit_count()
        return s1 * s2 if s1 >= s2 else s2 // s1

class Solution {
    public int calculateScore(int a, int b) {
        int s1 = Integer.bitCount(a);
        int s2 = Integer.bitCount(b);
        return s1 >= s2 ? s1 * s2 : s2 / s1;
    }
}

class Solution {
public:
    int calculateScore(int a, int b) {
        int s1 = __builtin_popcount(a);
        int s2 = __builtin_popcount(b);
        return s1 >= s2 ? s1 * s2 : s2 / s1;
    }
};

func calculateScore(a int, b int) int {
    s1 := bits.OnesCount(uint(a))
    s2 := bits.OnesCount(uint(b))
    if s1 >= s2 {
        return s1 * s2
    }
    return s2 / s1
}

function calculateScore(a: number, b: number): number {
    const s1 = a.toString(2).replace(/0/g, '').length;
    const s2 = b.toString(2).replace(/0/g, '').length;
    return s1 >= s2 ? s1 * s2 : Math.floor(s2 / s1);
}

4092. 二进制位得分

题目描述

解法

方法一：位计数

评论