class Solution {
public:
int subsetXORSum(vector<int>& nums) {
}
};
1863. 找出所有子集的异或总和再求和
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
[2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
注意：在本题中，元素 相同 的不同子集应 多次 计数。
数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
示例 1：
输入：nums = [1,3] 输出：6 解释：[1,3] 共有 4 个子集： - 空子集的异或总和是 0 。 - [1] 的异或总和为 1 。 - [3] 的异或总和为 3 。 - [1,3] 的异或总和为 1 XOR 3 = 2 。 0 + 1 + 3 + 2 = 6
示例 2：
输入：nums = [5,1,6] 输出：28 解释：[5,1,6] 共有 8 个子集： - 空子集的异或总和是 0 。 - [5] 的异或总和为 5 。 - [1] 的异或总和为 1 。 - [6] 的异或总和为 6 。 - [5,1] 的异或总和为 5 XOR 1 = 4 。 - [5,6] 的异或总和为 5 XOR 6 = 3 。 - [1,6] 的异或总和为 1 XOR 6 = 7 。 - [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。 0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28
示例 3：
输入：nums = [3,4,5,6,7,8] 输出：480 解释：每个子集的全部异或总和值之和为 480 。
提示：
1 <= nums.length <= 121 <= nums[i] <= 20原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-09-12 20:15:47
impl Solution {
pub fn subset_xor_sum(nums: Vec<i32>) -> i32 {
let mut res = 0;
for num in &nums {
res |= *num;
}
res << (nums.len() - 1)
// nums.iter().fold(0, |acc, &x| acc | x) << (nums.len() - 1)
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.9 MB, 提交时间: 2023-09-12 20:14:53
class Solution {
public:
int subsetXORSum(vector<int>& nums) {
int ans = 0;
for ( int num: nums ) {
ans |= num;
}
return ans << (nums.size() - 1);
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.7 MB, 提交时间: 2023-09-12 20:14:25
class Solution {
public int subsetXORSum(int[] nums) {
int ans = 0;
for ( int num: nums ) {
ans |= num;
}
return ans << (nums.length - 1);
}
}
php 解法, 执行用时: 0 ms, 内存消耗: 18.8 MB, 提交时间: 2023-09-12 20:13:12
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function subsetXORSum($nums) {
$ans = array_reduce($nums, function($a, $b) { return $a | $b; }, 0);
return $ans << (count($nums) - 1);
}
}
php 解法, 执行用时: 12 ms, 内存消耗: 18.8 MB, 提交时间: 2023-09-12 20:12:00
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function subsetXORSum($nums) {
$ans = 0;
foreach ( $nums as $num ) {
$ans |= $num;
}
return $ans << (count($nums) - 1);
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 16 MB, 提交时间: 2023-09-12 20:08:11
class Solution:
def subsetXORSum(self, nums: List[int]) -> int:
from functools import reduce
return reduce(lambda x, y: x | y, nums, 0) << (len(nums) - 1)
python3 解法, 执行用时: 44 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-12 20:06:04
class Solution:
def subsetXORSum(self, nums: List[int]) -> int:
ans = 0
for num in nums:
ans |= num
return ans << (len(nums) - 1)
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2021-06-09 10:37:40
func subsetXORSum(nums []int) int {
ans := 0
for _, num := range nums {
ans |= num
}
return ans << (len(nums) - 1)
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2021-06-08 22:54:32
func subsetXORSum(nums []int) int {
ans := 0
for _, num := range nums {
ans |= num
}
return ans << (len(nums) - 1)
}