凡科网站做的好不好,手机网站建设哪家专业,做网站所需知识,wordpress漂浮文章目录1. 异或的性质2. 题目一3. 题目二4. 题目三5. 题目四1. 异或的性质
我们知道#xff0c;异或的定义是#xff1a;相同为0#xff0c;相异为1。所以也被称为无进位相加#xff0c;根据这定义#xff0c;我们可以得出三个性质#xff1a; 1. N ^ N0。2. N ^ 0N。3… 文章目录1. 异或的性质2. 题目一3. 题目二4. 题目三5. 题目四1. 异或的性质
我们知道异或的定义是相同为0相异为1。所以也被称为无进位相加根据这定义我们可以得出三个性质 1. N ^ N0。2. N ^ 0N。3. 异或满足结合律与交换率所以一组数据一起异或结果一定是同一个值。
2. 题目一
如何不创建临时变量交换两个值 答案是aa ^ bba ^ baa ^ b。
证明aa ^ ba变了b没变。ba ^ b就等于ba ^ b ^ bba ^ 0ba。最后一步aa ^ b ^ a就是ab ^ 0ab。 两个数就进行交换了但是这个方法只能用在a与b指向不同的内存空间如果指向同一个内存空间这样写会把此内存置成0。
3. 题目二
怎么把一个int类型的数提取出最右侧的1来 什么意思呢 就是一个数a如何得到ans这样的值就是把最右侧的1提取出来。
答案是a(-a)或者a((~a)1)。这个大家可以自己证明一下。
4. 题目三
一个数组中有两种数出现了奇数次其它数都出现了偶数次怎么找到这两个数 解题思路假设出现两个奇数次的是a和b。 第一步将数组里的数全部异或那么结果就是a ^ b因为其它都是偶数次异或为0。 第二步找出a ^ b最右侧的1位置因为a和b是不同的所以a ^ b一定不为0所以a ^ b二进位中一定存在1的。 第三步a ^ b二进位中的1位置说明a和b在此位置上是不相等的。我们就把数组中所有此位置为1的分成一组此位置为0的分成一组。 第四步将此位置为1的异或在一起就能得出其中一个奇数次在异或a ^ b就能得出另外一个奇数次。
代码实现
5. 题目四
一个数组中有一种数出现K次其它数都出现了M次M1KM。找到出现K次的数。要求时间复杂度O(N)空间复杂度O(1)。
解题思路 第一步因为一个int类型是32位所以我们可以先定义一个32的数组。因为是常量数组所以空间复杂度是O(1)。。 第二步遍历数组里所有数如果这个数的某个位置是1我们就在32位数组中这个位置上1。 如果是4就在下标2的位置上1如果是12就在下标为2和3的位置上1。
第三步遍历这个32位数组如果某位置上能被M整除说明出现K次的那个数在此位置上为0如果此位置不能被M整除说明此位置上出现K次的那个数此位置为1。因为KM所有不存在能被M整除还存在出现K次的那个数。 假设K3M7某位置上1的个数是3838不能被7整除说明此位置上出现K此的那个数一定为1。
第四步定义一个变量为0如果此位置上不能整除我们就左移1然后或上去。
代码实现
