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
原題連結
https://leetcode.com/contest/weekly-contest-293/problems/largest-combination-with-bitwise-and-greater-than-zero/
您的支援是我最大的動力
- linux 安裝 ES 8.0 和 kibana 8.0 爬米共坑
- ES 8.0 及其生態配置過程一條龍服務
- 2022 年中紀
- leetcode 1048. Longest String Chain(python)
- leetcode 1354. Construct Target Array With Multiple Sums(python)
- leetcode 2311. Longest Binary Subsequence Less Than or Equal to K(python)
- leetcode 2304. Minimum Path Cost in a Grid(python)
- leetcode 2303. Calculate Amount Paid in Taxes(python)
- 帶你輕鬆入門 Bert
- leetcode 1332. Remove Palindromic Subsequences(python)
- leetcode 3. Longest Substring Without Repeating Characters (python)
- leetcode 2296. Design a Text Editor (python)
- leetcode 2293. Min Max Game(python)
- leetcode 1584. Min Cost to Connect All Points(python)
- leetcode 318. Maximum Product of Word Lengths(python)
- 沙灘 美女才是夏天的正確開啟方式
- leetcode 2275. Largest Combination With Bitwise AND Greater Than Zero (python)
- leetcode 2258. Escape the Spreading Fire(python)
- leetcode 2257. Count Unguarded Cells in the Grid(python)
- leetcode 2273. Find Resultant Array After Removing Anagrams(python)