leetcode：6127. 优质数对的数目【位运算找规律 + 两数之和大于等于k + 二分】

分析

首先位运算必然找规律
找到规律为a or b + a and b的1的个数 = a的1个数 + b的1个数
问题转化为有多少种组合使得num1和num2的1的个数大于等于k
使用排序加二分即可轻松解决

ac code

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        # 位运算找规律
        # or + and的1之和 = 原两个num1之和
        # 1 1： 2 == 2
        # 1 0： 1 == 1
        # 0 0： 0 == 0
        cnts = []
        nums = set(nums)
        for num in nums:
            cnts.append(bin(num)[2:].count('1'))
        cnts.sort()
        ans = 0

        #print(cnts)
        for i, v in enumerate(cnts):
            least = k - v
            idx = bisect_left(cnts, least)
            rest = len(cnts) - idx
            #print(i, v, least, idx, rest)
            ans += rest

        return ans

总结

关键在于问题的转化