☘前言☘
今天是算法零基础打卡的第47天，题目有点难度，给大家亿点点参考。上链接：
《算法零基础100讲》(第47讲) 位运算 (异或) 进阶
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
@[TOC](全文目录)
🎁主要知识点
异或运算
📓课后习题
260. 只出现一次的数字 III
861. 翻转矩阵后的得分
1442. 形成两个异或相等数组的三元组数目
📑写在最后
🎁主要知识点
异或运算
简单凯来说 就是同零异一，来看看真值表
x y x ^ y
0 0 0
1 0 1
0 1 1
1 1 0
📓课后习题
260. 只出现一次的数字 III
260. 只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
解题思路
烧脑时刻就要来临啦0.0
首先如果只出现一次，那么把数组全部异或之后得到的就是只出现一次的两个数字的异或结果。
因为两个数字是不同的，所以至少有一位是不同的，也就是上面的异或结果至少有一位是1.
将对应位为0 和1的数字为两堆分别异或求出来的结果分别对应只出现一次的两个数字
int* singleNumber(int* nums, int numsSize, int* returnSize){ unsigned ans = 0, *ans1= malloc(sizeof(unsigned)*2); memset(ans1,0,sizeof(ans1)); unsigned i ; for(i = 0;i <numsSize;++i) ans ^= nums[i]; //求出a^b for(i = 1;i < 4294967296;i<<=1) if(i & ans) break; //找到第i位不同 for(int j = 0;j < numsSize;++j) if(nums[j] & i) ans1[0] ^= nums[j];//分为两堆异或求解 else ans1[1] ^= nums[j]; *returnSize = 2; return ans1; }
861. 翻转矩阵后的得分
861. 翻转矩阵后的得分
有一个二维矩阵 A 其中每个元素的值为0 或 1 。
移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为1，将所有 1都更改为0。
在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。
返回尽可能高的分数。
解题思路
如果需要结果最大，行翻转使第一列的每个元素为1。(因为第一列权重最大)
列翻转使每列有更多的1。
只需要统计ans的值就好，没必要去创建出来一个矩阵存储
int matrixScore(int** grid, int gridSize, int* gridColSize){ int m = gridSize,n = gridColSize[0]; int ans = m * (1 << (n-1)); //第一列的结果和 for(int j = 1;j < n;j++){ int temp = 0; for(int i = 0;i < m;i++) if(grid[i][0] == 1) temp += grid[i][j]; //不需要翻转直接统计1 的个数 else temp += (1 - grid[i][j]); //需要翻转所以是1-结果的统计1个数 if(temp > m - temp) ans += temp * (1 << (n - j - 1)); //根据结果判断是否列翻转 else ans += (m - temp) * (1 << (n - j - 1)); } return ans; }
1442. 形成两个异或相等数组的三元组数目
1442. 形成两个异或相等数组的三元组数目
给你一个整数数组 arr 。
现需要从数组中取三个下标i、j和k ，其中 (0 <= i < j <= k < arr.length)。
a和b 定义如下：
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令a == b 成立的三元组(i, j , k) 的数目。
解题思路
有点类似于前缀和的思路，由于一个元素被异或两次就会变成0。而0和任何元素的异或结果都是元素本身。
所以我们可以计算每个元素的前缀异或结果。我加了一个0为0是为了统一结果，让只有0元素的时候不需要特殊处理。
int countTriplets(int* arr, int arrSize){ int temp[arrSize + 1]; temp[0] = 0; for(int i = 0;i < arrSize;i++){ //前缀异或 temp[i + 1] = arr[i] ^ temp[i]; } int ans = 0; for(int i = 0;i < arrSize - 1;i++) for(int j = i + 1; j < arrSize;j++) for(int l = j;l < arrSize;l++) if((temp[l + 1] ^ temp[j]) == (temp[j] ^ temp[i])) ans++;//满足条件 return ans; }
