class Solution {
public:
long long subsequenceSumOr(vector<int>& nums) {
}
};
2505. 所有子序列和的按位或
给你一个整数数组 nums ，返回对数组中所有可能的 子序列 之和进行按位 或 运算后得到的值。
数组的 子序列 是从数组中删除零个或多个元素且不改变剩余元素的顺序得到的序列。
示例 1：
输入：nums = [2,1,0,3] 输出：7 解释：所有可能的子序列的和包括：0、1、2、3、4、5、6 。 由于 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 = 7，所以返回 7 。
示例 2：
输入：nums = [0,0,0] 输出：0 解释：0 是唯一可能的子序列的和，所以返回 0 。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 109原站题解
rust 解法, 执行用时: 52 ms, 内存消耗: 3.5 MB, 提交时间: 2023-10-22 11:01:29
impl Solution {
pub fn subsequence_sum_or(nums: Vec<i32>) -> i64 {
let mut tmp = vec![0;64];
let mut ans = 0_i64;
for v in nums {
for i in 0..32 {
if ((v >> i) & 1) == 1 {
tmp[i] += 1;
}
}
}
for i in 0..63 {
if tmp[i] > 0 {
ans |= 1 << i;
}
tmp[i+1] += tmp[i] / 2;
}
ans
}
}
python3 解法, 执行用时: 716 ms, 内存消耗: 26.2 MB, 提交时间: 2023-10-22 11:01:01
class Solution:
def subsequenceSumOr(self, nums: List[int]) -> int:
lst = [0] * 64
for num in nums:
for index, digit in enumerate(bin(num)[2:][::-1]):
if digit == '1':
lst[index] += 1
cur = 1
res = 0
for i in range(63):
if lst[i] > 0:
res += cur
cur *= 2
lst[i + 1] += lst[i] // 2
return res
python3 解法, 执行用时: 116 ms, 内存消耗: 26 MB, 提交时间: 2023-10-22 11:00:46
class Solution:
def subsequenceSumOr(self, nums: List[int]) -> int:
if len(nums) == 1: return nums[0]
if sum(nums) == 0: return 0
nums.sort()
s = 0
for n in nums:
s |= n
p = 0
while s & 1 == 0:
s >>= 1
p += 1
return (1 << (int(log(sum(nums)) / log(2)) + 1)) - (1 << p)
python3 解法, 执行用时: 84 ms, 内存消耗: 26 MB, 提交时间: 2023-10-22 11:00:34
class Solution:
def subsequenceSumOr(self, nums: List[int]) -> int:
cur = 0
ans = 0
for num in nums:
cur += num
ans |= num | cur
return ans