leetcode算法讲解（LeetCode力扣官方题解）(1)

2044. 统计按位或能得到最大值的子集数目

题目描述

难易度：中等

给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。

如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。

对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。

示例 1：

输入：nums = [3,1] 输出：2 解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ： - [3] - [3,1]

示例 2：

输入：nums = [2,2,2] 输出：7 解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。

示例 3：

输入：nums = [3,2,1,5] 输出：6 解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ： - [3,5] - [3,1,5] - [3,2,5] - [3,2,1,5] - [2,5] - [2,1,5]

提示：

解决方案

方法一：位运算

思路

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

代码

Python3

class Solution: def countMaxOrSubsets(self, nums: List[int]) -> int: maxOr, cnt = 0, 0 for 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, 1 elif orVal == maxOr: cnt = 1 return 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; }

Golang

func countMaxOrSubsets(nums []int) (ans int) { maxOr := 0 for i := 1; i < 1<<len(nums); i { or := 0 for j, num := range nums { if i>>j&1 == 1 { or |= num } } if or > maxOr { maxOr = or ans = 1 } else if or == maxOr { ans } } return }

JavaScript

var countMaxOrSubsets = function(nums) { let maxOr = 0, cnt = 0; for (let i = 0; i < 1 << nums.length; i ) { let orVal = 0; for (let 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; };

复杂度分析

方法二：回溯

思路

记 n 是数组 nums 的长度。方法一的缺点是，计算不同状态的按位或的值，都需要消耗 O(n) 的时间。这一步部分可以进行优化。每个长度为 n 比特的状态的按位或的值，都是可以在长度为 n−1 比特的状态的按位或的值上计算出来的，而这个计算只需要消耗常数时间。以此类推，边界情况是长度为 0 比特的状态的按位或的值。我们定义一个搜索函数，参数 pos 表示当前下标，orVal 表示当前下标之前的某个子集按位或值，这样就可以保存子集按位或的值的信息，并根据当前元素选择与否更新 orVal。当搜索到最后位置时，更新最大值和子集个数。

代码

Python3

class Solution: def countMaxOrSubsets(self, nums: List[int]) -> int: maxOr, cnt = 0, 0 def dfs(pos: int, orVal: int) -> None: if pos == len(nums): nonlocal maxOr, cnt if orVal > maxOr: maxOr, cnt = orVal, 1 elif orVal == maxOr: cnt = 1 return dfs(pos 1, orVal | nums[pos]) dfs(pos 1, orVal) dfs(0, 0) return cnt

Java

class Solution { int[] nums; int maxOr, cnt; public int countMaxOrSubsets(int[] nums) { this.nums = nums; this.maxOr = 0; this.cnt = 0; dfs(0, 0); return cnt; } public void dfs(int pos, int orVal) { if (pos == nums.length) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt ; } return; } dfs(pos 1, orVal | nums[pos]); dfs(pos 1, orVal); } }

C#

public class Solution { int[] nums; int maxOr, cnt; public int CountMaxOrSubsets(int[] nums) { this.nums = nums; this.maxOr = 0; this.cnt = 0; DFS(0, 0); return cnt; } public void DFS(int pos, int orVal) { if (pos == nums.Length) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt ; } return; } DFS(pos 1, orVal | nums[pos]); DFS(pos 1, orVal); } }

C

class Solution { public: int countMaxOrSubsets(vector<int>& nums) { this->nums = nums; this->maxOr = 0; this->cnt = 0; dfs(0, 0); return cnt; } void dfs(int pos, int orVal) { if (pos == nums.size()) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt ; } return; } dfs(pos 1, orVal| nums[pos]); dfs(pos 1, orVal); } private: vector<int> nums; int maxOr, cnt; };

C

void dfs(int pos, int orVal, const int* nums, int numsSize, int* maxOr, int* cnt) { if (pos == numsSize) { if (orVal > *maxOr) { *maxOr = orVal; *cnt = 1; } else if (orVal == *maxOr) { (*cnt) ; } return; } dfs(pos 1, orVal | nums[pos], nums, numsSize, maxOr, cnt); dfs(pos 1, orVal, nums, numsSize, maxOr, cnt); } int countMaxOrSubsets(int* nums, int numsSize) { int cnt = 0; int maxOr = 0; dfs(0, 0, nums, numsSize, &maxOr, &cnt); return cnt; }

Golang

func countMaxOrSubsets(nums []int) (ans int) { maxOr := 0 var dfs func(int, int) dfs = func(pos, or int) { if pos == len(nums) { if or > maxOr { maxOr = or ans = 1 } else if or == maxOr { ans } return } dfs(pos 1, or|nums[pos]) dfs(pos 1, or) } dfs(0, 0) return }

JavaScript

var countMaxOrSubsets = function(nums) { this.nums = nums; this.maxOr = 0; this.cnt = 0; dfs(0, 0); return cnt; }; const dfs = (pos, orVal) => { if (pos === nums.length) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal === maxOr) { cnt ; } return; } dfs(pos 1, orVal | nums[pos]); dfs(pos 1, orVal); }

复杂度分析

BY /

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。

,