【算法刷题】数组篇

---

数组中两个数的最⼤异或值

1. leet code：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/description/
2. 暴力解法：【部分样例超时，通过不了，不可以行】

class Solution {public int findMaximumXOR(int[] nums) {int n = nums.length;int max = Integer.MIN_VALUE;for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {int temp = nums[i] ^ nums[j];if (temp > max)max = temp;}}return max;}
}

3. 基于位操作的贪心解法
   解题流程：
   （1）题目要求整数32位，那就获取数组每个数的32位表达，二进制的01。
   （2）从最高位开始判断，存在两个数，在该位有0，1的表达（异或=1），那么我们答案的这一个为1。
   （3）循环（2）操作得到最后的结果。

    public int findMaximumXOR(int[] nums) {int ans = 0, mask = 0;for (int i = 31; i >= 0; i--) {Set<Integer> pres = new HashSet<>();mask |= (1 << i);// 获取nums所有数的第i位前缀for (int num: nums) {pres.add(num & mask);}int temp = ans|(1 << i);for (int pre: pres) {if (pres.contains(temp ^ pre)){ans = temp;break;}}}return ans;}

---

找出所有⼦集的异或总和再求和

1. leet code:https://leetcode.cn/problems/sum-of-all-subset-xor-totals/submissions/590697647/
2. 暴力解法：【可以通过】

思路：求出所有子集，然后计算每个集合的异或值，全部加起来即可。
（1）通过递归方式生成所有子集。每个元素有两种选择：要么在子集中，要么不在子集中。

    public void generateSubsets(int[] nums, int index, List<Integer> current,List<List<Integer>> subset) {if (index == nums.length) {subset.add(new ArrayList<>(current));return;}// 当前index不加到子集generateSubsets(nums, index + 1, current, subset);// 当前index加到子集current.add(nums[index]);generateSubsets(nums,index + 1,current,subset);// 撤销选择current.remove(current.size() - 1);}public int subsetXORSum(int[] nums) {// 1. 求出子集List<List<Integer>> list = new ArrayList<>();generateSubsets(nums,0, new ArrayList<Integer>(), list);int sum = 0;for (int i = 0; i < list.size(); i++) {List<Integer> subset = list.get(i);int total = subset.isEmpty()? 0 : subset.get(0);for (int j = 1; j < subset.size(); j++) {total ^= subset.get(j);}sum += total;}return sum;}

（2）采用位运算计算子集
思路：
对于一个数组的子集组合，每个位置上，要么有（1），要么没有（0），那么子集就可以采用位置二进制编码表示从000...～1111...，即从0～2^n-1。

   public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new ArrayList<>();int len = (1 << nums.length)-1;for (int i = 0; i <= len; i++) {List<Integer> sub = new ArrayList<>();for (int j = 0; j < nums.length; j++) {// 检测第j位是否为1int temp = (1 << j);if ((temp & i) != 0){sub.add(nums[j]);}}res.add(sub);}return res;}

3. 更好的解法：

   public int subsetXORSum(int[] nums) {int totalXOR = 0;for (int num : nums) {totalXOR |= num; // 逐位统计贡献}int n = nums.length;return totalXOR * (1 << (n - 1)); // 每个数字对异或的总贡献}

---