Skip to content

Latest commit

 

History

History
368 lines (300 loc) · 8.33 KB

File metadata and controls

368 lines (300 loc) · 8.33 KB
comments difficulty edit_url rating source tags
true
简单
1372
第 241 场周赛 Q1
位运算
数组
数学
回溯
组合数学
枚举

English Version

题目描述

一个数组的 异或总和 定义为数组中所有元素按位 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 <= 12
  • 1 <= nums[i] <= 20

解法

方法一:二进制枚举

我们可以用二进制枚举的方法,枚举出所有的子集,然后计算每个子集的异或总和。

具体地,我们在 $[0, 2^n)$ 的范围内枚举 $i$,其中 $n$ 是数组 $nums$ 的长度。如果 $i$ 的二进制表示的第 $j$ 位为 $1$,那么代表着 $nums$ 的第 $j$ 个元素在当前枚举的子集中;如果第 $j$ 位为 $0$,那么代表着 $nums$ 的第 $j$ 个元素不在当前枚举的子集中。我们可以根据 $i$ 的二进制表示,得到当前子集对应的异或总和,将其加到答案中即可。

时间复杂度 $O(n \times 2^n)$,其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$

Python3

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(1 << n):
            s = 0
            for j in range(n):
                if i >> j & 1:
                    s ^= nums[j]
            ans += s
        return ans

Java

class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < 1 << n; ++i) {
            int s = 0;
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 1) {
                    s ^= nums[j];
                }
            }
            ans += s;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < 1 << n; ++i) {
            int s = 0;
            for (int j = 0; j < n; ++j) {
                if (i >> j & 1) {
                    s ^= nums[j];
                }
            }
            ans += s;
        }
        return ans;
    }
};

Go

func subsetXORSum(nums []int) (ans int) {
	n := len(nums)
	for i := 0; i < 1<<n; i++ {
		s := 0
		for j, x := range nums {
			if i>>j&1 == 1 {
				s ^= x
			}
		}
		ans += s
	}
	return
}

TypeScript

function subsetXORSum(nums: number[]): number {
    let ans = 0;
    const n = nums.length;
    for (let i = 0; i < 1 << n; ++i) {
        let s = 0;
        for (let j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                s ^= nums[j];
            }
        }
        ans += s;
    }
    return ans;
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function (nums) {
    let ans = 0;
    const n = nums.length;
    for (let i = 0; i < 1 << n; ++i) {
        let s = 0;
        for (let j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                s ^= nums[j];
            }
        }
        ans += s;
    }
    return ans;
};

方法二:DFS

我们也可以使用深度优先搜索的方法,枚举出所有的子集,然后计算每个子集的异或总和。

我们设计一个函数 $dfs(i, s)$,其中 $i$ 表示当前搜索到数组 $nums$ 的第 $i$ 个元素,$s$ 表示当前子集的异或总和。初始时,$i=0$, $s=0$。在搜索的过程中,每次我们都有两种选择:

  • $nums$ 的第 $i$ 个元素加入当前子集,即 $dfs(i+1, s \oplus nums[i])$
  • $nums$ 的第 $i$ 个元素不加入当前子集,即 $dfs(i+1, s)$

当我们搜索完数组 $nums$ 的所有元素时,即 $i=n$ 时,当前子集的异或总和为 $s$,将其加到答案中即可。

时间复杂度 $O(2^n)$,空间复杂度 $O(n)$。其中 $n$ 是数组 $nums$ 的长度。

Python3

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        def dfs(i: int, s: int):
            nonlocal ans
            if i >= len(nums):
                ans += s
                return
            dfs(i + 1, s)
            dfs(i + 1, s ^ nums[i])

        ans = 0
        dfs(0, 0)
        return ans

Java

class Solution {
    private int ans;
    private int[] nums;

    public int subsetXORSum(int[] nums) {
        this.nums = nums;
        dfs(0, 0);
        return ans;
    }

    private void dfs(int i, int s) {
        if (i >= nums.length) {
            ans += s;
            return;
        }
        dfs(i + 1, s);
        dfs(i + 1, s ^ nums[i]);
    }
}

C++

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        function<void(int, int)> dfs = [&](int i, int s) {
            if (i >= n) {
                ans += s;
                return;
            }
            dfs(i + 1, s);
            dfs(i + 1, s ^ nums[i]);
        };
        dfs(0, 0);
        return ans;
    }
};

Go

func subsetXORSum(nums []int) (ans int) {
	n := len(nums)
	var dfs func(int, int)
	dfs = func(i, s int) {
		if i >= n {
			ans += s
			return
		}
		dfs(i+1, s)
		dfs(i+1, s^nums[i])
	}
	dfs(0, 0)
	return
}

TypeScript

function subsetXORSum(nums: number[]): number {
    let ans = 0;
    const n = nums.length;
    const dfs = (i: number, s: number) => {
        if (i >= n) {
            ans += s;
            return;
        }
        dfs(i + 1, s);
        dfs(i + 1, s ^ nums[i]);
    };
    dfs(0, 0);
    return ans;
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function (nums) {
    let ans = 0;
    const n = nums.length;
    const dfs = (i, s) => {
        if (i >= n) {
            ans += s;
            return;
        }
        dfs(i + 1, s);
        dfs(i + 1, s ^ nums[i]);
    };
    dfs(0, 0);
    return ans;
};