题目引出
给你一个下标从 0 开始的整数数组 nums 。
三个下标 i ，j 和 k 的 有效值 定义为 ((nums[i] | nums[j]) & nums[k]) 。
一个数组的 xor 美丽值 是数组中所有满足 0 <= i, j, k < n 的三元组 (i, j, k) 的 有效值 的异或结果。
请你返回 nums 的 xor 美丽值。(力扣周赛:力扣)
注意：
val1 | val2是val1和val2的按位或。val1 & val2是val1和val2的按位与。
这一题首先想到的肯定是暴力求解:回溯便可以求出来,代码如下
public int xorBeauty(int[] nums) {
backTracking(nums);
int res = 0;
for (Integer integer : result) {
res ^= integer;
}
return res;
}
ArrayList<Integer> list = new ArrayList<>();
public void backTracking(int[] nums) {
if (list.size() == 3) {
result.add((list.get(0) | list.get(1)) & list.get(2));
return;
}
for (int i = 0; i < nums.length; ++i) {
list.add(nums[i]);
backTracking(nums);
list.remove(list.size() - 1);
}
}这样的时间复杂度是很高的,因此我们不采用这种方法
因为这是| & ^运算,因此每一bite上的数字必然是0或者1,并且不同位置上的0和1是相互之间不影响的,只是对应位置上的相互影响,
设 含有三个比特位分别为a,b,c,
则(a|b)&c=1 则必须c=1,a和b有一个1的时候才成立
设这一共有n个元素,则一共一列共含有n个0或者1
设一共含有x个1,n-x个0
(a|b)&c=1 则有a|b为1则有:
–
(a|b)&c=1 有x(–)=x(2*n*x-)个
因为^运算的值为1时有奇数个1,则推导之后仅与x的数量有关,
结论:因此有奇数个1,则异或之后的结果为1
public int xorBeauty(int[] nums) {
int res=0;
for(int num:nums){
res^=num;
}
return res;
}这一题也可以推出结论:详细见:力扣
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/101055.html
