了解面试算法之 - 栈&队列&位运算

痛定思痛。 2022-01-14 01:01 127阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

算法，一门既不容易入门，也不容易精通的学问。

对于笔者来说算法算是我程序员生涯很不擅长的技能之一了，自从互联网界招人进入平静期后，越来越多的大厂在社招的时候不但会考验面试者的工作所用到的技能，而且会用算法题来考验面试者的逻辑思维能力和基本数据结构的掌握能力。这也就让想要社招进入大厂的部分同学有了一些望而却步的心理，毕竟工作中大部分时间在与UI层面的逻辑打交道，数据处理方面即使之前在学校中掌握的还还不错，几年的 CV 生活，估计也忘的差不多了。

但是作为一条有梦想的咸鱼，我们还是要重拾这些知识的。之前写过一篇 [搞懂单链表常见面试题][Link 1]，有兴趣的同学可以跳转浏览。今天笔者将会挑选几道栈与队列和位运算的相关题目来回顾下相关算法的基本知识。

## 栈与队列 ##

栈与队列分别是两种数据结构，不同语言对于栈和队列有着不同的声明，在 java 中 Stack 类是继承自 Vector 集合的子类，Queue 则是以接口形式存在，常用的其实现类是 LinkedList 这个双向队列。在C++的标准模版库也是有这两个数据结构定义的具体类的。

栈数据结构的特点是 FILO（first in last out） 即先进后出，队列则是 FIFO（first in first out）即先进先出。相信栈与队列的数据结构的基本特点大家也是熟记于胸了。下面就带大家看一道面试题来带大家看下这两者在面试题中的形式。

### 由两个栈实现一个队列 （✭✭✩✩✩） ###

题目难度两颗星，主要考察了对于栈和队列的数据结构特点。

前文介绍了，对于一个栈来说遵循 pop 操作时从栈的顶部取一个元素，对于队列来说 poll 操作时从队列队首取一个元素。所以该题翻译过来就是使用两个栈定义一种先放入的元素，最先被取出的数据结构。

此题应考虑到两种情况，首先最简单的一种情况，假设有 1，2，3，4，5 个元素依次进入自定义的队列，再依次取出。由于是进栈操作都进行完了才进行出栈操作，所以我们只需在元素出队时，将进栈元素倒入另一个空栈中即可。示意图如下：

![1][]

再一种情况是，如果 add poll 操作是交替进行的，那么如何保证数据结构先进先出的定义呢？比如先放入 1，2，3然后要进行一次取出操作取出 1，随后在进行 add 操作放入4，5，这种情况下如何操作两个栈，才能保证之后再取出的时候元素为 2，3，4，5 顺序？实际上我们只需要保证一下两点就可以：

1.  **无论如果 StackA（最开始add元素的那个栈） 要往 StackB 中压入元素，那么必须选择一次性全部压入。**
2.  **无论什么时候从队列中取元素，必须保证元素是从 StackB 中 pop 出的，也就是说，当 StackB 不为空的时候绝不能再次向 StackB 中压入元素。**

为了方便理解可以看下边这幅图：

![1][1 1]

明白了需要注意的点后就是该写代码的时候了，需要注意的点在图中已经用红色字体标出了，也就是在存入元素一直往 StackA 中存，取元素是从 StackB 中取，但要要注意的是取的时候需要保证 StackB 为空的时候要先将 StackA 中元素一次性压如 StackB 中，在进行从 StackB 中取的操作。

public static class  TwoStackQueue<E>{
            private Stack<E> stackA;
            private Stack<E> stackB;
    
            public TwoStackQueue() {
                stackA = new Stack<>();
                stackB = new Stack<>();
            }
    
            /**
             * 添加元素逻辑
             * @param e 要添加的元素
             * @return 这里只是遵循 Queue 的习惯，这里简单处理返回 true 即可
             */
            public boolean add(E e){
                stackA.push(e);
                return true;
            }
    
            /**
             * 去除元素的时候需要判断两个地方，StackA & StackB 是否都为空
             * StackB 为空的时候讲StackA中的元素全部依次压入 StackB
             * @return 返回队列中的元素 如果队列为空返回 null
             */
            public E poll(){
                //如果队列中没有元素则直接返回空，也可以选择抛出异常
                if (stackB.isEmpty() && stackA.isEmpty()){
                    return null;
                }
                
                if (stackB.isEmpty()){
                    while (!stackA.isEmpty()){
                        stackB.add(stackA.pop());
                    }
                }
                
                return stackB.pop();
            }
    
            /**
             * peek 操作不取出元素，只返回队列头部的元素值 
             * @return 队列头部的元素值
             */
            public E peek(){
                //如果队列中没有元素则直接返回空，也可以选择抛出异常
                if (stackB.isEmpty() && stackA.isEmpty()){
                    return null;
                }
    
                if (stackB.isEmpty()){
                    while (!stackA.isEmpty()){
                        stackB.add(stackA.pop());
                    }
                }
    
                return stackB.peek();
            }
        }
    复制代码

对应的 C++ 解法：

#include <stdio.h>
    #include <stack>
    using namespace std;
    
    template <typename T> class TStackQueue
    {
    public:
        void add(T t);
        T poll();
        
    private:
        stack<T> stackA;
        stack<T> stackB;
    };
    
    template <typename T> void TStackQueue<T>::add(T node) {
        stackA.push(node);
    }
    template<typename T> T TStackQueue<T>::poll(){
        if (stackB.empty() && stackA.empty()) {
            return NULL;
        }
        
        if (stackB.empty()) {
            while (!stackA.empty()) {
                stackB.push(stackA.top());
                stackA.pop();
            }
        }
        T node = stackB.top();
        stackB.pop();
        return node;
    }
    复制代码

### 两个队列实现一个栈 （✭✭✩✩✩） ###

上道题我们完成了两个栈实现一个队列的题目，那么两个队列实现一个栈又该注意哪些呢？

首先队列是先进先出，我们可以发现队列无论怎么倒，我们不能逆序一个队列。既然不能套用上题的解法，那么就得另谋出路，但是可以预知无非就是两个队列进行交替的入队出队操作，那么唯一要做的就是**判断目前出队的值是否是按照放入元素顺序中最后放入的元素。** 依旧画图举例

![1][1 2]

这里我们只看首次取出操作，那么需要注意一点， **如何判断哪一次取出操作后 QueueA 为空？**

事实上作为 `Queue` 作为容器，我们可以通过事先定义好的方法 `queue.size()` 去判断一个队列中元素的个数，有人可能说这是犯规，其实不是的。题目中给出是让你用队列去实现，那么队列中公共 API 都是你可以用的。所以可以想象出下面的伪代码：

//如果 queueA 的大小不为 0 则循环取出元素
    while(queueA.size() > 0){
        //被取出的元素
        int result = queueA.poll();
        // 这里注意我们取出元素后再去判断一次，队列是否为空，如果为空代表是最后一个元素
        if(queueA.size() != 0){
            queueB.add(result)
        }else{
            return result;
        }
    }
    复制代码

上文我们只是说了一次取出操作，那么一次取出操作后，再次放入元素应该怎么放，我们似乎又遇到了困难。

与上题不同的是，我们应该先思考如果连续两次取出应该怎么操作，上面一次取出后 `QueueA` 空了，所以我们如果按照相同的思路将 B 中的元素倒入 A 中，那么将会得到 3 ，这看起来没什么问题。那么如果下一步进行的 push 操作，那么应该放入 `QueueA` 还是 `QueueB` 中才能保证元素先进后出的规则呢，很容易想到是放入 B 中。 那么总结一下操作要点：

1.  **任何时候两个队列总有一个是空的。**
2.  **添加元素总是向非空队列中 add 元素。**
3.  **取出元素的时候总是将元素除队尾最后一个元素外，导入另一空队列中，最后一个元素出队。**

接上图我们开看第一次取出操作后可能的两种操作情况：

![1][1 3]

思路屡清楚了，那么时候写代码了：

public static class TwoQueueStack<E> {
       private Queue<E> queueA;
       private Queue<E> queueB;
    
       public TwoQueueStack() {
           queueA = new LinkedList<>();
           queueB = new LinkedList<>();
       }
    
       /**
        * 选一个非空的队列入队
        *
        * @param e
        * @return
        */
       public E push(E e) {
           if (queueA.size() != 0) {
               System.out.println("从 queueA 入队 " + e);
               queueA.add(e);
           } else if (queueB.size() != 0) {
               System.out.println("从 queueB 入队 " + e);
               queueB.add(e);
           } else {
               System.out.println("从 queueA 入队 " + e);
               queueA.add(e);
           }
           return e;
       }
    
       public E pop() {
           if (queueA.size() == 0 && queueB.size() == 0) {
               return null;
           }
    
           E result = null;
           if (queueA.size() != 0) {
               while (queueA.size() > 0) {
                   result = queueA.poll();
                   if (queueA.size() != 0) {
                       System.out.println("从 queueA 出队 并 queueB 入队 " + result);
                       queueB.add(result);
                   }
               }
               System.out.println("从 queueA 出队 " + result);
    
           } else {
               while (queueB.size() > 0) {
                   result = queueB.poll();
                   if (queueB.size() != 0) {
                       System.out.println("从 queueB 出队 并 queueA 入队 " + result);
                       queueA.add(result);
                   }
               }
               System.out.println("从 queueB 出队" + result);
           }
           return result;
       }
    }
    复制代码

为了方便大家理解我将文章进行下测试：

public static void main(String[] args) {
            TwoQueueStack<Integer> queueStack = new TwoQueueStack<>();
            queueStack.push(1);
            queueStack.push(2);
            queueStack.push(3);
            queueStack.push(4);
            queueStack.pop();
            queueStack.pop();
            queueStack.push(5);
            queueStack.pop();
        }
    复制代码

结果为下面所示,看上去我们的代码是对的

从 queueA 入队 1
    从 queueA 入队 2
    从 queueA 入队 3
    从 queueA 入队 4
    从 queueA 出队 并 queueB 入队 1
    从 queueA 出队 并 queueB 入队 2
    从 queueA 出队 并 queueB 入队 3
    从 queueA 出队 4
    从 queueB 出队 并 queueA 入队 1
    从 queueB 出队 并 queueA 入队 2
    从 queueB 出队3
    从 queueA 入队 5
    从 queueA 出队 并 queueB 入队 1
    从 queueA 出队 并 queueB 入队 2
    从 queueA 出队 5
    复制代码

付C++ 代码实现：

#include <stdio.h>
    #include<queue>
    #include<exception>
    
    using namespace std;
    
    template <typename T> class TQueueStack
    {
    public:
        void push(const T& node);
        T pop();
        
    private:
        queue<T> queueA;
        queue<T> queueB;
    };
    
    // 插入元素
    template<typename T> void TQueueStack<T>::push(const T& node)
    {
        
        //插入到非空队列，如果均为空则插入到queueB中
        if (queueA.size() == 0)
        {
            queueB.push(node);
        }
        else
        {
            queueA.push(node);
        }
    }
    
    template<typename T> T TQueueStack<T>::pop()
    {
        if (queueA.size() == 0 && queueB.size() == 0)
        {
            return NULL;
        }
        T head;
        if (queueA.size() > 0)
        {
            while (queueA.size()>1)
            {
                //queueA中的元素依次删除，并插入到queueB中，其中queueA删除最后一个元素
                //相当于从栈中弹出队尾元素
                T& data = queueA.front();
                queueA.pop();
                queueB.push(data);
            }
            head = queueA.front();
            queueA.pop();
        }
        else
        {
            while (queueB.size()>1)
            {
                //queueB 中的元素依次删除，并插入到 queueA 中，其中 queueB 删除最后一个元素
                //相当于从栈中弹出队尾元素
                
                T& data = queueB.front();
                queueB.pop();
                queueA.push(data);
            }
            head = queueB.front();
            queueB.pop();
        }
        return head;
    }
    复制代码

### 判断出栈顺序是否符合要求（✭✭✭✩✩） ###

经历了上两道题，大家是不是感觉对栈和队列更反感，哦不对是更了解了呢。（额~ 一不小心把实话说出来了）。下面我们来看第二道题这是一个有关于出栈顺序的判断的题目:

> 题目: 输入两个整数数组，第一个表示一个栈的压入序列，请写一个函数，判断第二个数组是否为该栈的出栈序列，假设数组中的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

看到这道题我们首先应该去理解题目中的怎么去判断是否符合出栈顺序，其实题目想要表达的意思是如果以数组 A 的方式进栈但并不是一次全部进栈，比如我们先进栈1，2，3，4 然后出栈 4，然后进栈 5，然后在出栈 5，3，2，1。 那么什么情况下是不可能满足的出栈顺序呢？比如 1，肯定是比 2 先进栈的，所以 2肯定比 1先出栈。所以解题的关键就在于，如何判断数组2 中的元素，是按数组1 中某种进栈顺序操作的出栈序列。

思路是如果我们在进栈的同时维护一个出栈角标，如果栈顶元素等于 `popA[popIndex]` 的时候，将角标加一，并出栈该元素，并继续判断下一个栈顶元素，如果栈顶元素不等于 `popA[popIndex]` 的时候继续入栈元素，直到所有元素入栈完毕如果，栈不为空则表示 popA 不是一个出栈序列。通过下图可以更好的理解题目要考察的内容：

![1][1 4]

所以在编程的只需要注意一下三点：

1.  **执行放入操作后，如果栈顶的元素等于对应角标在 popA 数组中的元素值，那么就需要出栈该元素，同事角标加1**
2.  **如果栈顶的元素不等于对应角标在 popA 数组中的元素值，那么就执行放入操作**。
3.  **待所有的元素都被放入栈中，此时如果栈为空，那么 popA 就是一个出栈序列，反之则不是。**

下面看代码实现：

public static class Solution {
    
       public boolean IsPopOrder(int[] pushA, int[] popA) {
           int len = pushA.length;
    
           Stack<Integer> stack = new Stack<>();
           for (int pushIndex = 0, popIndex = 0; pushIndex < len; pushIndex++) {
               stack.push(pushA[pushIndex]);
               //如果栈顶元素等于 popA[popIndex] 则一直出栈且 popIndex++
               while (popIndex < popA.length && popA[popIndex] == stack.peek()) {
                   stack.pop();
                   popIndex++;
               }
           }
           return stack.isEmpty();
       }
    }
    复制代码

C++实现如下

class Solution {
    public:
        bool IsPopOrder(vector<int> pushA, vector<int> popA) {
            if(pushA() == 0) return false;
            vector<int> stack;
            for(int i = 0,j = 0 ;i < pushA.size();){
                stack.push_back(pushA[i++]);
                while(j < popA.size() && stack.back() == popA[j]){
                    stack.pop_back();
                    j++;
                }       
            }
            return stack.empty();
        }
    };
    复制代码

测试结果如下：

public static void main(String[] args) {
    
       Solution solution = new Solution();
       int[] pushA = new int[]{1, 2, 3, 4, 5};
       int[] popA1 = new int[]{4, 3, 5, 1, 2};
       int[] popA2 = new int[]{4, 5, 3, 2, 1};
    
       System.out.println("popA1 是否是出栈队列 " + solution.IsPopOrder(pushA, popA1));
       System.out.println("popA2 是否是出栈队列 " + solution.IsPopOrder(pushA, popA2));
    }
    // 结果
    //popA1 是否是出栈队列 false
    //popA2 是否是出栈队列 true
    复制代码

## 位运算 ##

上一小节我们用三道题了解一下面试过程中栈和队列的常见面试题。本小节笔者将通过几个位运算的题目来带大家熟悉下常用的位运算知识。

相比于栈和队列来讲，笔者自身认为位运算需要掌握的知识就要多一些，包括对于数字的二进制表示，二进制的反码，补码。以及二进制的常见运算都需要了解。当然如果系统的去学，可能没有经历，也可能即使学完了，仍旧不会做题。所以笔者认为通过直接去刷一些相应的题目，则是一个比较便捷的途径。

### 给定一个整数，请写一个函数判断该整数的奇偶性（✭✩✩✩✩） ###

该题目作为后续题目的铺垫，看上去还是没有任何难度的。主要考察了面试能否想到用二进制的位运算方法去解决。

首先整数可以分为正数，负数，0。也可以分为奇数和偶数。[偶数的定义是：如果一个数是2的整数倍数，那么这个数便是偶数][2]。如果不使用位运算的方法，我们完全可以使用下面的方式解决：

public boolean isOdd(int num){//odd 奇数
        return num % 2 != 0;
    }
    复制代码

可是面试题不可能去简单就考察这么简单的解法，进而我们想到了二进制中如果 **一个数是偶数那么最后一个一定是 0 如果一个数是奇数那么最后一位一定是 1**；而十进制 1 在 8 位二进制中表示为 0000 0001，我们只需将一个数个 1相与（&） 得到的结果如果是 1 则表示该数为奇数，否知为偶数。所以这道题的最佳解法如下：

public boolean isOdd(int num){
        return num & 1 != 0;
    }
    复制代码

#include "iostream"  
    using namespace std;  
    //声明
    bool IsOdd(int num)；
    
    bool IsOdd(int num)
    {
        int res = (num & 1);
        return res != 0;
    }
    复制代码

测试：

int main(int argc, const char * argv[]) {
      std::cout << "是否是奇数 ： " << IsOdd(1) <<endl;
      std::cout << "是否是奇数 ： " << IsOdd(4) <<endl;
      return 0;
    }
    
    //结果
    是否是奇数 ： 1//是 true
    是否是奇数 ： 0//不是 false
    复制代码

### 同样给定一个整数，请写一个函数判断该整数是不是2的整数次幂（✭✩✩✩✩） ###

这道题仍旧考察面试者对于一个数的二进制的表示特点，一个整数如果是2的整数次幂，那么他用二进制表示完肯定有唯一一位为1其余各位都为 0，形如 0..0100...0。比如 8 是 2的3次幂，那么这个数表示为二进制位 0000 1000 。

除此之外我们还应该想到，一个二进制如果表示为 0..0100...0，那么它减去1得到的数二进制表示肯定是 0..0011..1 的形式。那么这个数与自自己减一后的数相与得到结果肯定为0。

如：

![1][1 5]

所以该题最佳解法为：

public boolean log2(int num){
       return (num & (num - 1)) == 0;
    }
    复制代码

#include "iostream"  
    using namespace std;  
    //声明
    bool IsLog2(int num)；
    //定义
    bool IsLog2(int num)
    {
        return (num & (num -1)) == 0;
    }
    复制代码

测试：

int main(int argc, const char * argv[]) {
        std::cout << "是否是2的整数次幂 ： " << IsLog2(1) <<endl;
        std::cout << "是否是2的整数次幂 ： " << IsLog2(3) <<endl;
        return 0;
    }
    
    //结果
    是否是2的整数次幂 ： 1 //是 true
    是否是2的整数次幂 ： 0 //不是 false
    复制代码

### 给定一个整数，请写一个函数判断该整数的二进制表示中1的个数（✭✭✩✩✩） ###

此题较之上一题又再进一步，判断一个整数二进制表示中1的个数，假设这个整数用32位表示，可正可负可0，那么这个数中有多少个1，就需要考虑到符号位的问题了。

相信读者应该都能想到最近基本的解法即通过右移运算后与 1 相与得到的结果来计算结果，如果采用这种解法，那么这个题的陷阱就在于存在负数的情况，如果负数的话标志位应该算一个1。所以右移的时候一定要采用无符号右移才能得到正确的解法。

> ps 对于正数右移和无符号右移得到结果一样，如果是负数，右移操作将在二进制补码左边添加追加1，而无符号右移则是补 0 。

所以此题一种解法如下：

public int count1(int n) {
       int res = 0;
       while (n != 0) {
           res += n & 1;
           n >>>= 1;
       }
       return res;
    }
    复制代码

#include "iostream"  
    using namespace std;
      
    //注意C++中没有无符号右移操作，所以这里传入一个 unsigned 数作为 params
    int count1(unsigned int n){
        int res = 0;
        while(n != 0){
            res += n & 1;
            n >>= 1;
        }
        return res;
    }
    复制代码

测试结果：

int main(int argc, const char * argv[]) {
        std::cout << "二进制中1的个数 ： " <<  count1(-1) <<endl;
        std::cout << "二进制中1的个数 ： " <<  count1(1) <<endl;
        return 0;
    }
    
    //结果
    二进制中1的个数 ： 32
    二进制中1的个数 ： 1
    复制代码

能回答出上边的答案你的面试肯定是及格了，但是作为练习来说，是否有额外的解法呢？首先上述结果最坏的情况可能需要循环32次。上面我们算过一道如何判断一个数是否是2的整数倍，我们用过了 `n&(n-1)==0` 的方法。其实该题的第二个解法也可以用这个方法。为什么呢？我们开看一次上边的图：

![1][1 6]

我们是否能发现，每次与比自己小1的数与那么该数的二进制表示最后一个为1位上的1将将会被抹去。其实这是一个知道有这种原理才能想到的方法，所以大家也不用哀叹说我怎么想不到，通过这次记住有这个规律下次就多一个思路也不是很么坏事。

下面我们来看下判断一个数中有多少个1的完整图解：

![1][1 7]

所以我们可以通过如下方法来得到题解，这样我们可以减少移动次数

public int countA(int n){
       int res = 0;
       while(n != 0){
           n &= (n - 1);
           res++;
       }
       return res;
    }
    复制代码

#include "iostream"  
    using namespace std;  
    // 同上传入无符号整数 
    int countA(unsigned int n){
        int res = 0;
        while(n != 0){
            n &= (n - 1);
            res++;
        }
        return res;
    }
    复制代码

测试结果：

int main(int argc, const char * argv[]) {
        std::cout << "二进制中1的个数 ： " <<  countA(-1) <<endl;
        std::cout << "二进制中1的个数 ： " <<  countA(1) <<endl;
        return 0;
    }
    
    //结果
    二进制中1的个数 ： 32
    二进制中1的个数 ： 1
    复制代码

### 在其他数都出现两次的数组中找到只出现一次的那个数（✭✭✩✩✩） ###

这道题同样是考察为位运算的一道题，但是如果对于不熟悉位运算的朋友可能压根都不会往这方面想，也许当场直接就下边写下了遍历数组记每个数出现次数的代码了。其实这道题要求在时间复杂度在O(n) 空间复杂度为O(1)的条件下，那种解法是不符合要求的。我们来看下为位运算的解题思路。

首先我们应该知道二进制异或操作，异或结果是二进制中两个位相同为0，相异为1。因此可以有个规律：

> 任何整数 n 与 0 异或总等于其本身 n，一个数与其本身异或那么结果肯定是 0。

还需要知道一个规律：

> 多个数异或操作，遵循交换律和结合律。

对于第一条朋友们肯定都很好理解，然而第二条规律才是这道题的解题关键。如果我们有一个变量 `eO = 0` 那么在遍历数组过程中，使每个数与 eO 异或得到的值在赋值给额 eO 即 `eO=eO ^ num` 那么遍历结束后eO的值一定是那个出现一次的数的值。这是为什么呢？我们可以举个例子：

假设有这么一个序列： C B D A A B C 其中只有 D 出现一次，那么因为异或满足交换律和结合律，所以我们遍历异或此序列的过程等价于

eO ^ (A ^ A ^ B ^ B ^ C ^ C ) ^ D = eO ^ 0 ^ D = D
    复制代码

所以对于任何排列的数组，如果只有一个数只出现了奇数次，其他的数都出现了欧数次，那么最终异或的结果肯定为出现奇数次的那个数。

所以此题可以有下面的这种解法：

java 解法

public int oddTimesNum(int[] arr) {
       int eO = 0;
       for (int cur : arr) {
           eO = eO ^ cur;
       }
       
       return eO;
    }
    复制代码

C++ 解法

int oddTimesNum(vector<int> arr) {
        int eO = 0;
        for (int cur : arr) {
            eO = eO ^ cur;
        }
        return eO;
    }
    复制代码

测试：

int main(int argc, const char * argv[]) {
      vector<int>  arr = {2,1,3,3,2,1,4,5,4};
      std::cout << "出现奇数次的那个数： " << oddTimesNum(arr) <<endl;
      return 0;
    }
    
    //结果
    出现奇数次的那个数： 5
    复制代码

关于这道题还有个延伸版本，就是如果数组中出现1次的数有两个，那么该如何得到这两个数。

### 在其他数都出现两次的数组中找到只出现一次的那两个数（✭✭✭✩✩） ###

我们顺着上题的思路来思考，如果有两个数获得的结果 eO 肯定是 `eO = a^b`,此题的关键就在于如何分别得到 a，b 这两个数。我们应该想到，**任何不相同的两个除了跟自己异或外，不可能每一个位都相同**，也就是说不相同的两个数 a b 异或得到结果二进制表示上肯定有一位为 1。 这是关键。

我们可以假设第 k 位不为 0 ，那么就说明 a 与 b 在这位上数值不相同。我们要做只是设置一个数第 k 位 为 1，其余位为 0 记为 `rightOne`。

这时需要拿 `eOhasOne = 0` 再异或遍历一次数组，但是需要忽略与 `rightOne` 相与等于 0 的数。因为相与等于 0 则代表了这个数肯定是两个数中第 k 位不为 1的那个。最终得到的 `eOhasOne` 就是 a b 中第 k 为为 1 的那个。

那么接下来就剩下一个问题要解决了，如何找到 `rightOne` ，这里采用与本身补码相与的方法得到即 `int rightOne = eO & (~eO + 1)` 。

可以参照下图来理解下整个过程：

![1][1 8]

我们来看下最终的代码:

java 写法

public void printOddTimesNum(int[] arr) {
       int eO = 0;
       int eOhasOne = 0;
    
       for (int cur : arr) {
           eO = eO ^ cur;
       }
    
       int rightOne = eO & (~eO + 1);
       for (int cur : arr) {
           if ((rightOne & cur) != 0) {
               eOhasOne = eOhasOne ^ cur;
           }
       }
    
       System.out.println("eOhasOne = " + eOhasOne + "  " + (eOhasOne ^ eO));
    }
    复制代码

C++ 写法

void printOddTimesNum(vector<int> arr) {
        int eO = 0;
        int eOhasOne = 0;
        
        for (int cur : arr) {
            eO = eO ^ cur;
        }
        
        int rightOne = eO & (~eO + 1);
        
        for (int cur : arr) {
            if ((cur & rightOne) != 0) {
                eOhasOne = eOhasOne ^ cur;
            }
        }
        
        std::cout<<"一个出现1次的数 " << eOhasOne << endl;
        std::cout<<"二个出现1次的数 " << (eO ^ eOhasOne) <<endl;
    }
    复制代码

测试：

int main(int argc, const char * argv[]) {
        vector<int>  arr1 = {2,1,3,3,2,1,4,5};
        printOddTimesNum(arr1);
        return 0;
    } 
    
    //结果：
    一个出现1次的数 5
    二个出现1次的数 4
    复制代码

## 总结 ##

本文列举了栈队列以及位运算的一些面试题目，通过这些面试题目我们可以了解到一些面试中算法的考点，对于位运算相关题目，我们还是需要多加练习，但是不要害怕自己某些地方不会限制了解题思路，通过多加练习，记住见过的解题中的规律，相信经过一段时间练习后，也会感受到自我的提高。

最后欢迎大家关注我的掘金专栏，不定时分享一些自己的学习工作总结。

[像一只狗的掘金专栏][Link 2]

## 参考 ##

《剑指 offer 第二版》 《程序员代码面试指南 - 左程云》

转载于:https://my.oschina.net/u/2935389/blog/3030377

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/5ec20ee15e0c4a98a26d24ae5447c9f0.png
[Link 1]: https://juejin.im/post/5aa299c1518825557b4c5806
[1]: https://user-gold-cdn.xitu.io/2018/7/22/164c2a5b4910fbaf?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 1]: https://user-gold-cdn.xitu.io/2018/7/22/164c2a5b494d9d73?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 2]: https://user-gold-cdn.xitu.io/2018/7/22/164c2a5b490df7b3?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 3]: https://user-gold-cdn.xitu.io/2018/7/22/164c2a5b49e8e71b?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 4]: https://user-gold-cdn.xitu.io/2018/7/22/164c2a5b4a9bd27f?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[2]: https://link.juejin.im?target=https%3A%2F%2Fzh.wikipedia.org%2Fwiki%2F0%25E7%259A%2584%25E5%25A5%2587%25E5%2581%25B6%25E6%2580%25A7
[1 5]: https://user-gold-cdn.xitu.io/2018/7/23/164c4dcd61a9dda0?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 6]: https://user-gold-cdn.xitu.io/2018/7/23/164c4dcd61ba3c10?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 7]: https://user-gold-cdn.xitu.io/2018/7/23/164c4dcd628d695c?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 8]: https://user-gold-cdn.xitu.io/2018/7/23/164c4dcd61f50960?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[Link 2]: https://juejin.im/user/56793b0860b2b7af14c637db/posts