位运算求最大值的子集数目问题

一、方法：位运算

二、我们再来看解题思路：

记 n 是数组 nums 的长度，数组中的每个元素都可以选取或者不选取，因此数组的非空子集数目一共有 (2n-1) 个。可以用一个长度为 n 比特的整数来表示不同的子集，在整数的二进制表示中，n 个比特的值代表了对数组不同元素的取舍。第 i 位值为 1 则表示该子集选取对应元素，第 i 位值为 0 则表示该子集不选取对应元素。求出每个子集的按位或的值，并计算取到最大值时的子集个数。

代码

Python3

class Solution:def countMaxOrSubsets(self, nums: List[int]) -> int:maxOr, cnt = 0, 0for i in range(1, 1 << len(nums)):orVal = reduce(or_, (num for j, num in enumerate(nums) if (i >> j) & 1), 0)if orVal > maxOr:maxOr, cnt = orVal, 1elif orVal == maxOr:cnt += 1return cnt

Java

class Solution {public int countMaxOrSubsets(int[] nums) {int maxOr = 0, cnt = 0;for (int i = 0; i < 1 << nums.length; i++) {int orVal = 0;for (int j = 0; j < nums.length; j++) {if (((i >> j) & 1) == 1) {orVal |= nums[j];}}if (orVal > maxOr) {maxOr = orVal;cnt = 1;} else if (orVal == maxOr) {cnt++;}}return cnt;}
}

C#

public class Solution {public int CountMaxOrSubsets(int[] nums) {int maxOr = 0, cnt = 0;for (int i = 0; i < 1 << nums.Length; i++) {int orVal = 0;for (int j = 0; j < nums.Length; j++) {if (((i >> j) & 1) == 1) {orVal |= nums[j];}}if (orVal > maxOr) {maxOr = orVal;cnt = 1;} else if (orVal == maxOr) {cnt++;}}return cnt;}
}

C++

class Solution {
public:int countMaxOrSubsets(vector<int>& nums) {int n = nums.size(), maxValue = 0, cnt = 0, stateNumber = 1 << n;for (int i = 0; i < stateNumber; i++) {int cur = 0;for (int j = 0; j < n; j++) {if (((i >> j) & 1) == 1) {cur |= nums[j];}}if (cur == maxValue) {cnt++;} else if (cur > maxValue) {maxValue = cur;cnt = 1;}}return cnt;}
};

C

int countMaxOrSubsets(int* nums, int numsSize){int n = numsSize, maxValue = 0, cnt = 0, stateNumber = 1 << n;for (int i = 0; i < stateNumber; i++) {int cur = 0;for (int j = 0; j < n; j++) {if (((i >> j) & 1) == 1) {cur |= nums[j];}}if (cur == maxValue) {cnt++;} else if (cur > maxValue) {maxValue = cur;cnt = 1;}}return cnt;
}

好了，今天的文章分享就到这里了，希望对大家的学习有帮助哦！