精华内容
下载资源
问答
  • 异或法总结

    2021-09-14 20:40:15
    异或符号为:^ 。 0与任何数异或都为任何数本身。相同为0,不同为1。 例如 0^3 = 3 1^3=2 000 001 011 011 ----- ------- 011 010 异或虽然看起来????️用,但是可以运用在很多题目上。其中有一个非常经典的...

    异或符号为:^ 。 0与任何数异或都为任何数本身。相同为0,不同为1。

    例如 0^3 = 3           1^3=2

    000                       001

    011                         011

    -----                   -------

    011                         010

    异或虽然看起来🈚️用,但是可以运用在很多题目上。其中有一个非常经典的题目就是消失的数字,来试试看吧


    数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

    示例 1:

    输入:[3,0,1]
    输出:2
     

    示例 2:

    输入:[9,6,4,2,3,5,7,0,1]
    输出:8

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/missing-number-lcci

    首先第一眼看到这道题目,我相信很多人都会想去用循环每个去比对,最后查找出最后没有的数字,但是!!这道题目有时间复杂度的限时 为O(n),所以我们就需要有其他的思路~这时候异或法的特点就体现出来了,它可以使一样的数字消失变成0。老师刚开始讲的时候我也是一脸懵逼,但是经过我自己动笔去算算之后,发现它是多么的神奇。

    比如说实例1中数组的3,若找到与0~3中与3匹配的数字 消除的时候就是3^3=0 这样的话,就可以用异或的办法去消除数组中有的数字,剩下的就是输出结果2啦~

    具体过程如下:

    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int x = 0;
            //这里设置为0 因为0与任何数异或都是任何数本身
            for(int i = 0;i < nums.size();i++)
            {
                x^=nums[i];
            }
            //这里异或剩下的数字
            for(int i = 0;i<=nums.size();i++)
            {
                x^=i;
            }
            //与含有所有数字的数组比对,相同的数字消掉为0 同样因为是0 所以0^剩下的数=它本身
            return x;
        }
    };

    如果还是抱有疑惑的小伙伴们可以自己去尝试算算 或者debug 🧐


    第二道题呢 就相对于来说要复杂一点 更难想一点(我自己都还是懵懵懂懂 所以来捋一捋

    题目:260. 只出现一次的数字 III

    给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

    进阶:你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

    示例 1:

    输入:nums = [1,2,1,3,2,5]
    输出:[3,5]
    解释:[5, 3] 也是有效的答案。
    

    示例 2:

    输入:nums = [-1,0]
    输出:[-1,0]
    

    示例 3:

    输入:nums = [0,1]
    输出:[1,0]

    首先要补充一个知识点:<< 移位算法

    A = (1<<2),1写成二进制就是0000 0001,这个一左移2位就是0000 0100,所以得到的数A为0000 0100,即0x04。

    再如:B = (2<<4),2写成二进制就是0000 0010,这个一左移4位就是0010 0000,所以得到的数B为0010 0000,即0x20。

    上面两个移位算法都是正确的,第一种写法,表示第三位为1其余都是0的数,数的时候是从0数起的,再比如(1<<0)表示的是0000 0001,(1<<7)表示的是1000 0000,但是第二种写法没有没有这种意义,移位也用于乘除法,左移一位乘以2,右移移位除以2,上面的第二种写法2左移四位得到的数是2×2×2×2×2=32,也就是上面的0x20。


    OK言归正传 这个题两个知识点都需要用上,看到题目中有两个相同元素出现 有了前面奠定的基础我们不得不想到了异或法 没错又是它!因为它是消去两个相同元素的最好方法 当相同的数字都被划去之后 那么剩下的就是输出的结果:x1、x2了。

    然后我们就把第一步写出来……然后发现 欸!结果不就是x=x1^x2了吗 那怎么把x1和x2分离出来了呢。现在是这样的一个情况 那实例1举例子:这是3^5

           00011

           00101              

           -------

    x     00110       找出x里面第m位为1说明x1和x2第m位不一样 一个为1一个为0。 

    m=0时 00110&00001=00000 m=1时 00110&00010=00010 嘿 True break

    取元素中分离出x1和x2 即各在一组。

             if(nums[i]&(1<<m)){        
                    x1^=nums[i];               
                }         

    当3(00011)&00010 =00010 =》true ,x1^3=0^3 = 3

    另一个数也被分出来了

    最后注意的是返回值需要以vector

    class Solution {
    public:
        vector<int> singleNumber(vector<int>& nums) {
            int x=0;
            for(int i=0;i<nums.size();i++)
            {
                x^=nums[i];
            }
            int m = 0;
            while(m<32)  //最多32位
            {
                if(x&(1<<m)) break;
                else ++m;
            }
            int x1=0,x2=0;
            for(int i=0;i<nums.size();i++)
            {
                if(nums[i]&(1<<m)){
                    x1^=nums[i];
                }
                else
                {
                    x2^=nums[i];
                }
            }
            vector<int> v;
            v.push_back(x1);
            v.push_back(x2);
            return v;
        }
    };

    匆匆结束 我困了…… 有问题的话 可以评论哦~

    展开全文
  • 题目描述 ...异或法的思路是:首先明确异或运算的规则:相同两个数异或为0,不同两个数异或为1,任何数和0异或值都不变。 1.先将数组中的所有数异或一下,出现两次的数异或不改变结果,最终得到的结

    题目描述

    一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

    题目分析

    这个题目主要有两种方法:
    1.hash法
    2.异或法

    1. hash法是先遍历一遍数组利用map记录数字出现的此时,第二次遍历则将出现次数为1的数存入vecor数组并输出。

      时间复杂度:O(n)
      空间复杂度:O(n)

    2. 异或法的思路是:首先明确异或运算的规则:相同两个数异或为0,不同两个数异或为1,任何数和0异或值都不变。
      1.先将数组中的所有数异或一下,出现两次的数异或不改变结果,最终得到的结果result是两个出现次数为1的数。
      2.其中result中二进制1一定由0和1(1和0)异或而成,因此只需要将0和出现次数为1的数异或,结果就是出现次数为1的数。
      **注意:**计算机中存储的二进制数是补码,因此需要将补码转换为原码:
      正数的原码与补码相同。
      负数的原码=补码&(-补码)。
      时间复杂度:O(n)
      空间复杂度:O(1)

    代码

    C++代码如下:

    1.hash法:

    class Solution {
    public:
        void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) 
        {
            unordered_map<int,int> map;
            for(const int k : data) ++map[k];
            vector<int> num;
            for(const int k : data)
            {
                if(map[k]==1)
                    num.push_back(k);
            }
            *num1=num[0];
            *num2=num[1];
        }
    };
    

    2.异或法:

    class Solution {
    public:
        void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) 
        {
           int result=0;
            for(const int k : data)
            {
                result^=k;
            }
            result&=(-result);
            *num1=0;
            *num2=0;
            for(const int k : data)
            {
                if(k&result) 
                    *num1^=k;
                else
                    *num2^=k;
            }
        }
    };
    
    展开全文
  • 设有int型两个变量 a和b,不借助于临时变量可用异或法交换两个变量的值,注意这里的异或为位异或操作; 通过操作  a = a ^ b;  b = b ^ a;  a = a ^ b; 可以实现两个变量值得交换,已知异或操作满足交换律和...

    设有int型两个变量 a和b,不借助于临时变量可用异或法交换两个变量的值,注意这里的异或为位异或操作;

    通过操作

            a = a ^ b;
            b = b ^ a;
            a = a ^ b;

    可以实现两个变量值得交换,已知异或操作满足交换律和结合律,a^a=0,0^a=a;故而上述操作解释为:

            a = a ^ b   (1);
            b = b ^ a   (2);b=b^a^b=b^b^a=0^a=a
            a = a ^ b   (3);将右边的a用(1)展开b用(2)展开为a=a^b^b^a,注意,这里右边的两个a值不同,最右边的a=a^b;

    故而(3)中a=a^b^b^a^b=a^a^b^b^b=0^b=b。值的交换完成

    展开全文
  • void Exchange_tmp(int a, int b) ...// 当然这种方法并没有太大的毛病,要怪就怪谁想出的下面的异或法TAT void Exchange_sum(int a, int b) { b = a + b;// 只要记住b中存着 a、b的和 a = b - a;// 右式:把两数之和
    void Exchange_tmp(int a, int b)
    {
    	int tmp = 0;
    	tmp = a;
    	a = b;
    	b = tmp;
    	printf("%d,%d\n", a, b);
    	return;
    }
    // 这种方法应该不需用解释原理:
    // 当然这种方法并没有太大的毛病,为什么还要其他两种方法呢?因为另外两种不需用额外空间。今天,通过优化省去4个字节;未来,通过优化或许就改变了许多!
    
    void Exchange_sum(int a, int b)
    {             // 如果想要理解其中原理,逐个看每一条语句的解释。
    	b = a + b;// 这里只要记住b中存着 a、b的和
    	a = b - a;// 右式:把两数之和减掉a,剩下b ; 赋值符:b赋值给a(一定记住b中始终存着两数和,分析的时候我所称呼的b,全是指没有相加之前的b,两数的和具体存在哪里先不用考虑,等到会分析这个算法过后再考虑为什么两数和放在b中)
    	b = b - a;// 目前情形:a中存着b的值   右式:两数和减去b就得到了a的值  ; 赋值符:将a赋值给b。
    	// 如果都把两数和单独领出来而不作为b的值,分析第一步到第三步会清晰很多
    
    	// 现在要解决的是:为什么两数和要存在b中。我一开始听说不用中间变量来交换两数的时候,第一个想法也是这种相加的方法。为什么想到这个和的方法:其实这个做法和生活中的情形很相似,你两只手各拿着一个棒棒糖,你现在要交换过来,可不就是将一只手里的棒棒糖先放在另一只手上,用空了的那只手拿走原本另一只手上的??
    
    	// 	有了这个实际情况,理解这个算法就容易多了。但是计算机相加之后不是棒棒糖那么好分辨谁是谁,
    	// 所以就要进行”用一个数挤出去另一个数“的方法分离。第二步算是容易理解的”分离“(把a挤出去,留下了b),第三步一定记住a存着b,这时就靠a(存着的b)把出去b挤出去,留下了a
    	// 如果读第一遍没有理解,结合后面的生活实例尝试自己分析前面三步,不会也不要紧。作为新手,总要多见识见识的,到后面刷题还会遇见它,到那时会须就会了(因为我就是当时不会,后来再次遇到才想明白的)
    	printf("%d,%d\n", a, b);
    	return;
    }
    // 分析这个算法的缺陷,对于两个都接近int范围的数,相加之后必然超过范围,继而导致交换算法的结果出错
    
    
    // 了解一下两个规律有助于理解这个算法:任意数异或这个数自己都等于0(a^a=0); 0与任意数异或都等于该数(0^a=a)
    void Exchange_eor(int a, int b)
    {
    	b = a ^ b; // 这种方法和第二种差不多思想 如果对于上面两个规律不能理解就当这个和上面第二种方法一样是在求和
    	a = b ^ a;// 右式:和减去a得到b;赋值符:把b给a(将b作为固定和,b本身没变化过)
    	b = b ^ a;// 右式:b减去b,得到了a; 赋值号:把a给b(这里当赋值的一刻,b才开始变化)
    	printf("%d,%d", a, b);
    	return;// 这题结合上一道题,慢慢想一想,想不出来不要紧,以后还会遇到,而且以后的思维会更灵活。只要能再找工作前解决就没问题
    	
    	// 对于有体验过上面两个规律的同学将做如下讲解
    	b = a ^ b;// 和上面利用和的方法一样,这里不要记b中存着a^b ,只要知道有一个数是 a^b
    	a = b ^ a;// 整理目前所有已知的信息:一个存着a^b的变量 ;接下来分析右边的式子,a^b 和a 进行异或,相当于b^(a^a),由第一个规律化简就是b^0 ,再由第二个规律化简就是b;赋值符:将b赋值给a
    	b = b ^ a;// 现在a中存着b;分析右边的式子:a^b 和b异或(这里脑袋要转过弯哦),相当于a^(b^b),得到a^0,也就是a ;赋值符:将a赋值给b
    	// 和上面的加法相同,一定不要想b中存着谁。先搞清为什么这样操作能完成交换,再把b中存着的对象加入到分析过程
    }
    
    int main()
    {
    	int a = 0, b = 0;
    
    	scanf("%d%d", &a, &b);
    	Exchange_tmp(a, b);
    	Exchange_sum(a, b);
    	Exchange_eor(a, b);// 异或法
    	return 0;
    }
    // 或许你能发现,和的方法 与 异或法 只是运算符变了。当然,这是两个方法中同时把b作为存储a+b和a^b的地方。你可以把两数和更存到a中自己写试一试
    
    
    展开全文
  • hdu2095 异或法

    2017-04-11 17:17:17
    看了好多大佬的 ,纯属复制,供以后自己复习,自己的代码没用异或超时了 说明: 1. a^a=0, 0^a=a 2. 如果一组数中,只有一个是奇数个,那么全部异或后就找出来了 #include  int main() { int n,...
  • 将两个数字进行交换,一共有3种方法: 使用额外空间的方法: 最常用的方法,代码如下: ...不使用额外空间的方法:(1)加减法 (2)异或法 ...(2)异或法(是两数交换所用时间最快的方法)
  • 连连看(异或法

    2019-06-26 19:35:16
    Description 小志最近喜欢连连看这个游戏,但是连连看太难了,所以他发明了一种简易的连连看,为了简化问题,现在我们有n对整数,每对数字都是相同的,但是...//异或法 } printf("%d",x); return 0; }  
  • 异或法 学习过程中,我们交换两个数字总要用到第三方变量暂存其中一个变量的值。 做法通常如下: //第三变量法 int a = 2, b = 3; int c; c=a; a=b; b=c; 这种方法有溢出的风险,此外还有两种方法——加...
  • C#的异或法画图 清除绘画

    热门讨论 2010-04-19 17:04:28
    C#画图中并没有像C++那样有异或画法,所以在完成擦除图形的时候,很麻烦。比如说你可以很轻松画一个圆,但是要你擦除这个圆,就会让你比较烦了,我试过设置每个像素来处理,但是这个使图形的边看起来不是很圆滑。这...
  • 原题:896. 单调数列 如果数组是单调递增或单调递减的,那么它是单调的。 如果对于所有 i <= j,A[i] <= A[j],那么数组 A 是单调递增的。 如果对于所有 i <...网上很多人采用的是多情况讨论,.
  • 思路:本地用异或加密好图片---放入Android的assets文件夹下---在程序里用异或解密。 都知道解压APK文件能拿到程序的图片资源,为了保护图片资源不被盗用,可采用简单异或的方法对图片进行加密,这样即使解压APK...
  • 代码非常的简单明了,其实最核心的就是异或的思想,因为如果一个数只出现一次就代表这个数组的个数一定是奇数,那么出现两次的数,因为数值相同,所以异或的结果是0,那么数组中所有的数异或得到的结果就是那个只...
  • 异或法 已知两个整型变量的值,要求两个值进行交换。 临时变量交换法 首先假设两个值为X,Y,需要将X的内容放入Y中,将Y的值放入X中,要完成这个过程,需要创建一个同类型的临时变量Z,整个交换过程为: 首先将X的值...
  • 【数据结构与算法】(七)异或法

    千次阅读 2019-07-05 16:46:30
    异或是基于二进制的位运算,用符号XOR或者^表示,对符号两边的数的二进制进行运算,相同为0,不同为1。简单理解就是不进位加法。 性质: (1)交换律 : a^b = b^a (2)结合律 : a^b^c = a^(b^c) (3)x^x = 0 ...
  • 一: 直接暴力。遍历然后统计出现的次数。 完整代码 for i in nums: if nums.count(i) == 1: # 当有一个元素仅出现一次的时候,返回该数 return i 二: 使用哈希表存储元素出现的次数,然后找到出现一次的。 ...
  • 我的一个同学在吃饭聊天的时候,给我说这种题的时候,但是他把题设“这些数都在1~1000的范围内”给漏了,于是他想让我在不知道这些数是什么数的情况下,用异或法来做,并且尽量有时间复杂度为o(n)。在一度怀疑自己...
  • 解题思路: 异或的性质:任何数异或自己都为0;任何数异或0都等于自己。 所以让0对s和t分别进行异或,剩下的就是加入的数。C++和Python的效率差别还是很大的,相同的逻辑C++能超越100%时间。 题解: # python3 击败...
  • 题目描述 来源: ... 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 ...异或法 ...参考的用户是 LeetCode yinyin nie 的 Java 异或法
  • 解题思路: 使用异或的性质,对于一个数a, 对他自己进行异或,值为0。不难得出:a ^ x ^ a = x 。有了上述的定理,我们可以将整个给定的链表节点值加上位置信息(可以自己设计Hash, 本文直接采用与中间位置的距离与...
  • 性质4:对任意a,偶数个a异或结果为0,奇数个a异或结果为a -------------------------------------------------------------------------------- 2.对一个非负整数序列定义平衡态和非平衡态 对n个非负整数序列A1...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 53,409
精华内容 21,363
关键字:

异或法