leetcode 2275. Largest Combination With Bitwise AND Greater Than Zero （python）

描述

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

• For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.
• Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

Return the size of the largest combination of candidates with a bitwise AND greater than 0.

Example 1:

Input: candidates = [16,17,71,62,12,24,14]
Output: 4
Explanation: The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0.
The size of the combination is 4.
It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0.
Note that more than one combination may have the largest size.
For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.

Example 2:

Input: candidates = [8,8]
Output: 2
Explanation: The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0.
The size of the combination is 2, so we return 2.

Note:

1 <= candidates.length <= 10^5
1 <= candidates[i] <= 10^7

解析

根據題意，陣列 nums 的 bitwise AND 是 nums 中所有整數的按位與結果。

• 例如，對於 nums = [1, 5, 3]，按位與等於 1 & 5 & 3 = 1。
• 此外，對於 nums = [7]，按位與為 7。

給定一個正整數候選陣列 candidates 。 可以從中找若干數字形成一個組合，candidates 中的每個數字在每個組合中只能使用一次。返回按位與操作且大於 0 的組合的最大數量。

其實這道題就是考察位相關操作，我們知道在二進位制按位與操作中只有都為 1 結果才為 1 ，如果出現至少一個 0 結果就為 0 ，而題目要求我們找大於 0 的組合，所以我們可以將 candidates 中所有的元素都轉換成二進位制，然後比較他們每個相同位上面的 1 出現的數量，最後取某個位上面的 1 的最多出現數量即可。

時間複雜度為 O(N) ，空間複雜度為 O(N) 。

解答

class Solution(object):
    def largestCombination(self, candidates):
        """
        :type candidates: List[int]
        :rtype: int
        """
        c = [bin(c)[2:]for c in candidates]
        maxLength = max(len(s) for s in c)
        result = 0
        for i in range(1, maxLength+1):
            tmp = 0
            for s in c:
                if i > len(s):
                    continue
                elif s[-i] == '1':
                    tmp += 1
            result = max(result, tmp)
        return result

執行結果

80 / 80 test cases passed.
Status: Accepted
Runtime: 1492 ms
Memory Usage: 29.1 MB

原題連結

http://leetcode.com/contest/weekly-contest-293/problems/largest-combination-with-bitwise-and-greater-than-zero/

您的支援是我最大的動力