精华内容
下载资源
问答
  • 亦或

    2016-10-17 18:10:29
    题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。 分析:这是一道很新颖的关面试题。 首先我们考虑这个问题的一个...

    题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)

    分析:这是一道很新颖的关面试题。

    首先我们考虑这个问题的一个简单版本:一个数组里除了一个数字之外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

    这个题目的突破口在哪里?题目为什么要强调有一个数字出现一次,其他的出现两次?我们想到了异或运算的性质:任何一个数字异或它自己都等于0。也就是说,如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是那个只出现依次的数字,因为那些出现两次的数字全部在异或中抵消掉了。

    有了上面简单问题的解决方案之后,我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中,包含一个只出现一次的数字,而其他数字都出现两次。如果能够这样拆分原数组,按照前面的办法就是分别求出这两个只出现一次的数字了。

    我们还是从头到尾依次异或数组中的每一个数字,那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次,在异或中全部抵消掉了。由于这两个数字肯定不一样,那么这个异或结果肯定不为0,也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置,记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组,第一个子数组中每个数字的第N位都为1,而第二个子数组的每个数字的第N位都为0

    现在我们已经把原数组分成了两个子数组,每个子数组都包含一个只出现一次的数字,而其他数字都出现了两次。因此到此为止,所有的问题我们都已经解决。

    求一个数最低位1的个数还有多种方法(编程之美提到过)。

    基于上述思路,我们不难写出如下代码:

    #include<stdio.h>
    #include<string.h>
    int we(int b)
    {
        int c[33];
        memset(c,0,sizeof(c));
        int t;
        int p=32;
        while(b)
        {
            c[p--]=b%2;
            b=b/2;
        }
        for(int i=32;i>=0;i--)
        {
            if(c[i]==1)
            {
                t=i;
                break;
            }
        }
        return t;
    }
    int main()
    {
        int n;
        while(scanf("%d",&n)!=-1)
        {
            int sum=0;
            int a[100];
            for(int i=0;i<n;i++)
            {
               scanf("%d",&a[i]);
                sum=sum^a[i];
            }
            int f=we(sum);
            int g=0,k=0;
            for(int i=0;i<n;i++)
            {
                if(we(a[i])==f)
                {
                    g^=a[i];
                }
                else
                {
                   k^=a[i];
                }
            }
            printf("%d %d\n",g,k);
        }
    }

    数组A中,除了某一个数字x之外,其他数字都出现了三次,而x出现了一次。请给出最快的方法,找到x。

    分析

    乍一看这个题目,不少同学立马给出了答案:异或。但举个例子,就会发现,异或是行不通的,一般的方法是利用异或的的如下特性:

    • A xor A = 0

    • A xor 0 = A

    但是这个题目中,数字都是奇数个的,直接采用之前类似题目的异或方法,已经不合适了。

    除此之外,我们还可能想到如下的方法:

    • 采用hashmap,时间复杂度O(n),空间复杂度O(n)

    • 对数组A进行排序,然后在遍历一次,时间复杂度O(nlogn),空间复杂度O(1) 这个方法还可以。

    是否还有一些效果更好的方法呢?这一类的题目,即使简单的异或不能解决,也可以从二进制位、位操作方面去考虑,总之这样的大方向是不会错的。

    题目中,如果数组中的元素都是三个三个出现的,那么从二进制表示的角度,每个位上的1加起来,应该可以整除3。如果有一个数x只出现一次,会是什么情况呢?

    • 如果某个特定位上的1加起来,可以被3整除,说明对应x的那位是0,因为如果是1,不可能被3整除

    • 如果某个特定位上的1加起来,不可以被3整除,说明对应x的那位是1

    根据上面的描述,我们可以开辟一个大小为32的数组,第0个元素表示,A中所有元素的二进制表示的最低位的和,依次类推。最后,再转换为十进制数即可。这里要说明的是,用一个大小为32的整数数组表示,同样空间是O(1)的。

    程序实现:

    #include<iostream>
    using namespace std;
    void set(int& s,int i) { s |= (1<< (i & 0x1F));}//3不能被m[i]整除。则s的二进制的第i个位置为1, 否则第i位置为0                                   +  
    void clr(int& s,int i) { s &= ~(1<<(i & 0x1f));}
    void find(int a[],int n)
    {
        int m[32];
        for(int i=0;i<32;i++)
            m[i]=0;
        for(int i=0;i<32;i++)
        {
            for(int j=0;j<n;j++)
            {
                int bit=a[j]&1;//&相当于mod 2
                m[i]+=bit;
                a[j]>>=1;//相当于除以二
            }
        }
        int result=0;
        for(int i=0;i<32;i++)
        {
            if(m[i]%3!=0)
            set(result,i);
        }
        cout<<result<<endl;
    }
    int main()
    {
        int a[]={2,2,2,3,3,3,4,4,4,7};
        int n=sizeof(a)/sizeof(a[0]);
         find(a,n);
    }
    void set(int& a,int i) { a |= (1<< (i & 0x1F));} 把a第i位置为1;
    void clr(int& a,int i) { a &= ~(1<<(i & 0x1f));} 把a的第i位清0;
    

    不过这里申请了一个数组的空间,如果这个是不被允许的呢?

    参考:http://www.ituring.com.cn/article/56178


    展开全文
  • Java中亦或运算符

    2020-01-16 10:29:51
    Java中亦或运算符 最近遇到这样一道算法题:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 示例: 输入【2562569】 输出:9 当时毫无解决思路,对亦或...

    Java中亦或运算符

    最近遇到这样一道算法题:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    示例:
    输入【2562569】
    输出:9

    当时毫无解决思路,对亦或运算毫无了解,经过多方资料查找进行总结
    首先我们先了解下什么是亦或运算符
    1、亦或运算符是一个数学运算符,应用于逻辑算法,符号:" ^ "
    2、有好多小伙伴会被其名字迷惑,亦或是针对于变量在计算机组成的二进制来计算的
    举个例子:假如用 a,b 代替2个变量(可以是数字也可以是任何字符)他们的值分别是5和8,他们的二进制编码分别是:
    在这里插入图片描述其中5的二进制为101
    8的二进制为1000
    亦或遵循规则:
    相同为0:00=0;11=1
    相异为1:10=1;01=1
    0与任何数亦或为其本身
    则5^8 二进制结果为1101(值为13)不会可以看看二进制的运算
    由此可得:两个相同的数例如:6^6 由于他们在计算机中的二进制相同所以结果为0,0与任何数亦或得本身(例如:0 ^ 9得到9)
    3、对于上面示例找9的题你是否有答案了
    我们可以这样解题:我们把数字按照数学的逻辑交换位置(2^2) ^ (5 ^ 5) ^ (6 ^ 6) ^9 套公式进行技术得到 0 ^ 0 ^0 ^ 9 最后得到 9 本身
    4、用程序实现

    int[] numarry = new int[]{2,5,6,2,5,6,9};
    int only = numarry[0];
    for(int i = 1; i < 7; i++)
    {
    only = only ^ numarry[i];
    }
    System.out.println(“最后:”+only);
    
    展开全文
  • 海明码和亦或

    2019-10-03 16:34:58
    亦或 异或,英文为exclusive OR,缩写成xor。异或(xor) 是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”,计算机符号为"xor” 。 其运算法则为: a⊕b= (¬a^b)v (a ^¬b),如果a、b两个值不相同,则异或...

    亦或

    异或,英文为exclusive OR,缩写成xor。异或(xor) 是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”,计算机符号为"xor” 。
    其运算法则为:
    a⊕b= (¬a^b)v (a ^¬b),如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。

    运算方法如下:
    真⊕假=真
    假⊕真=真
    假⊕假=假
    真⊕真=假

    或者为:
    True⊕False = True
    False⊕True = True
    False⊕False = False
    True⊕True = False

    海明码

    海明码(也叫汉明码)具有一位纠错能力。

    编码:

      确定校验码的位数x

      设数据有n位,校验码有x位。则校验码一共有2^{^{x}}种取值方式。其中需要一种取值方式表示数据正确,剩下2^{^{x}}-1种取值方式表示有一位数据出错。因为编码后的二进制串有n+x位,因此x应该满足

    2^{^{x}} -1 ≥ n+x   

      使不等式成立的x的最小值就是校验码的位数。在本例中,n=7,解得x=4。

    展开全文
  • 神奇的亦或

    2016-02-02 23:21:00
     解析:根据a^a=0,只需将所有的元素亦或起来,得到的结果就是该元素。以LeetCode 136.为例,代码如下:   class Solution { public: int singleNumber(vector<int>& nums) { ...

     一、一个整数数组,只有唯一一个元素出现一次,其他的元素都出现两次,找出这个元素。

      解析:根据a^a=0,只需将所有的元素亦或起来,得到的结果就是该元素。以LeetCode 136.为例,代码如下:

      

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int ans=0;
            for(int i=0;i<nums.size();++i)
                ans^=nums[i];
            return ans;
        }
    };
    

     

    二、一个整数数组,有两个不同的元素各出现一次,其他元素均出现两次,找出这两个元素。

      解析:设要求的两个元素为x、y。将所有元素的亦或起来,便得到这两个元素的亦或运算值,并且这个值一定不是0,即,在某位比特位(假设第k位)上值是1。所以根据第k位上的值将数组中的元素分成两部分,分别亦或起来得到的两个值便是x和y的值。以LeetCode 260.为例,代码如下:

      

    class Solution {
    public:
        vector<int> singleNumber(vector<int>& nums) {
            vector<int>ans;
            int a=0;
            for(int i=0;i<nums.size();++i)
                a^=nums[i];
            a=a^(a&(a-1));
            int x=0,y=0;
            for(int i=0;i<nums.size();++i)
                if(nums[i]&a) x^=nums[i];
                else y^=nums[i];
            ans.push_back(x);
            ans.push_back(y);
            return ans;
        }
    };
    

      

    三、有一个长度为n+1的数组,其中的元素是0~n这n+1个数。现在,这个数组中丢失了一个元素,请找回这个元素。

      解析:这道题太简单了。。。以LeetCode 268.为例,代码如下:

     

    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int xor1=0;
            for(int i=0;i<nums.size();++i)
                xor1^=nums[i]^(i+1);
            return xor1;
        }
    };
    

      

    四、一个整数数组中,只有元素x出现一次,其他元素均出现三次,找到这个元素。

      解析:对于32位以内的每一个整数,这32个比特位构成的0-1组合是唯一的。所以,当某个数出现三次,那么他的每一比特位上的数字累加和应为3的倍数,所以将所有数的数位上的值累加起来,如果哪一位上的和模3等于1,那么x就在这一位上取值。以LeetCode 137.为例,代码如下:

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int *a=new int[32];
            fill(a,a+32,0);
            for(int i=0;i<nums.size();++i)
                for(int j=0;j<32;++j)  if(nums[i]&(1<<j))
                    ++a[j];
            int ans=0;
            for(int i=0;i<32;++i)
                if(a[i]%3) ans|=(1<<i);
            delete []a;
            return ans;
        }
    };
    

      这是一个通法,如果其他元素出现次数是其他的值,这种方法依然有用!!!

    转载于:https://www.cnblogs.com/20143605--pcx/p/5178735.html

    展开全文
  • 通过亦或的性质: 1)a^a = 0 0^a = a 2)交换律 a^b = b^ a 3)结合律 (a^b)^c=a^(b^c) 这样很容易证明将所有的数亦或就能得到唯一的一个只存在一个的数。 1 class Solution { 2 public: 3 int s...
  • 同样用亦或来解决(参考编程之美的1.5) 先去取出总亦或值 然后分类,在最后一位出现1的数位上分类成 ans[0]和ans[1] a&(-a)就是计算出这个数,可以参考树状数组。 最后就是注意(nums[i] & a) == 0要加...
  • 独立董事津贴与公司业绩正相关:信号显示亦或激励?,谢德仁,黄亮华,基于水平模型的回归显示独立董事津贴和公司业绩之间存在显著的正向关联关系。但这一正向关联关系背后的经济逻辑是什么呢?本文运
  • 或 与 非 亦或

    千次阅读 2018-08-15 17:40:39
    : 00为0 其它都为1 与 :11为1 其它都为0 异或:同为0,不同为1 非:00为1,其它为0 与非:11为0,其它为1
  • 把开发过程中较好的一些代码备份一次,如下的资料是关于C语言基础:亦或xor操作的代码。 #include <stdio.h> void main () { printf(“0 ^ 0 is %dn”, 0 ^ 0); printf(“0 ^ 1 is %dn”, 0 ^ 1); printf(“1 ...
  • 在之前的一篇文章中我们知道如何求求数X在储存了0-1的字典树数组A[I]当中去寻找X与A[i]的最大值 且A[i]是可以进行重复利用的 那么现在我们来求求亦或的最小值问题 先挂出题: Q - Perfect Security Alice has a very...
  • hdu 5014 亦或的性质

    2015-02-09 23:45:05
    根据亦或的性质,要获得最大的和,那么两两配对的数的二进制数的每一位都不相同,所以会形成一种对称的局势. 比如1111到0000之间就是两两对称 1010和0101之间也是两两对称, 根据这种性质,那么只要...
  • 亦或

    2018-03-11 15:43:26
    考虑到分解为二进制后 疑惑后只有每一位是一得个数有奇数个才行 就统计出每位1,0的个数 查询,我也不是多明白。就这样搞吧。。。 // luogu-judger-enable-o2 #include&lt;...const int N...
  • 思路:偶数个相同数字亦或得到0,奇数个亦或得到本身,那么如果把一段区间暴力亦或,得到的其实就是出现次数为奇数的数字的亦或和,所以我们希望这段区间内的所有数字出现次数都+1,使奇偶性互换。 我们先处理出...
  • CF 242E [线段树区间亦或+求和] 题目链接 题意:给你n个数,有两种操作,op=1,对从l到r的数求和,op=2,对从l到r的值xor val。 思路:由于亦或是位运算,我们可以考虑位运算的关系, 1 xor 1=0, 0 xor 1=1, 1 xor 0=1...
  • 首先我想说明一下亦或这个应用,我认为亦或是一个非常重要的知识点。 总结一下亦或的性质 : 1.a ^ a = 0; 2.a ^ 0 = a; 3.(a ^ b) ^ c = a ^ (b ^ c); 4.已知 a ^ b = c 得到 a = b ^ c;  这些性质对于...
  • 使用 【^ 亦或运算符】 实现【变量值交换】和 【数组反转】废话不多说,直接上代码,一切尽在注释中!!! 废话不多说,直接上代码,一切尽在注释中!!! package demo; public class XOR { public static ...
  • 算法中的亦或 ^1.亦或的性质 交换律 a^b = b^a 结合律 a^b^c=a^(b^c)=(a^b)^c 0^a=a 0与任何数亦或都是这个数 a^a=0 2.典型应用:2.1 交换两个数a=a^b; b=b^a;(b^a^b=b^b^a=a) a=a^b;((a^b)^a=b)2.2 落单的数对于...
  • 美国硅谷时间12月5日,200多位区块链名人以及社区成员在硅谷 Palo Alto 共聚一堂,欢庆 Bitrue 年度酒会。酒会以“2019趋势及预测:火热,不确定,亦或...
  • * @description 寻找数组中唯一重复的一个数,用到亦或的交换和提取 * @date 2020-08-26 13:55 */ public class FindRepetitionNum { public static void main(String[] args) { int N = 11; int[] nums = new...
  • People in the Tomskaya region like magic formulas very much. You can see some of them below. Imagine you are given a sequence of positive integer numbers p1, p2, ...,pn. Lets write down some magi
  • 1. 题目 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: ...2.为什么可以用亦或解答 public class Time { public static ...
  • 与或非亦或与交换

    2016-09-05 18:01:11
    说明: 1.首先需理解二进制的概念 2.在10进制,2进制,8进制,16进制能够自由转换 正文:  1.... 说明:二进制相同位中 两个运算数都为1,结果为1,...运算  符号:|  说明:二进制相同位中两个运算数只要有一
  • subscribe?亦或 async

    2019-01-08 13:45:22
    获取的属性可以直接使用在组件模板的任何一个地方方法,无需依赖各种变通observable;当然,使用subscribe需要手动在组件destory的时候,去取消subscribe以免造成内存泄漏; 使用 rxjs 的takeUntil...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,413
精华内容 3,765
关键字:

亦或