了解面試算法之 - 棧&隊列&位運算
本文已經(jīng)授權 玉剛寫作平臺 提供寫作贊助
版權聲明：本文版權歸微信公眾號 玉剛說 所有，未經(jīng)許可不得以任何形式轉載
算法，一門既不容易入門，也不容易精通的學問。
對于筆者來說算法算是我程序員生涯很不擅長的技能之一了，自從互聯(lián)網(wǎng)界招人進入平靜期后，越來越多的大廠在社招的時候不但會考驗面試者的工作所用到的技能，而且會用算法題來考驗面試者的邏輯思維能力和基本數(shù)據(jù)結構的掌握能力。這也就讓想要社招進入大廠的部分同學有了一些望而卻步的心理，畢竟工作中大部分時間在與UI層面的邏輯打交道，數(shù)據(jù)處理方面即使之前在學校中掌握的還還不錯，幾年的 CV 生活，估計也忘的差不多了。
但是作為一條有夢想的咸魚，我們還是要重拾這些知識的。之前寫過一篇 搞懂單鏈表常見面試題，有興趣的同學可以跳轉瀏覽。今天筆者將會挑選幾道棧與隊列和位運算的相關題目來回顧下相關算法的基本知識。
棧與隊列
棧與隊列分別是兩種數(shù)據(jù)結構，不同語言對于棧和隊列有著不同的聲明，在 java 中 Stack 類是繼承自 Vector 集合的子類，Queue 則是以接口形式存在，常用的其實現(xiàn)類是 LinkedList 這個雙向隊列。在C++的標準模版庫也是有這兩個數(shù)據(jù)結構定義的具體類的。
棧數(shù)據(jù)結構的特點是 FILO（first in last out） 即先進后出，隊列則是 FIFO（first in first out）即先進先出。相信棧與隊列的數(shù)據(jù)結構的基本特點大家也是熟記于胸了。下面就帶大家看一道面試題來帶大家看下這兩者在面試題中的形式。
由兩個棧實現(xiàn)一個隊列 （?????）
題目難度兩顆星，主要考察了對于棧和隊列的數(shù)據(jù)結構特點。
前文介紹了，對于一個棧來說遵循 pop 操作時從棧的頂部取一個元素，對于隊列來說 poll 操作時從隊列隊首取一個元素。所以該題翻譯過來就是使用兩個棧定義一種先放入的元素，最先被取出的數(shù)據(jù)結構。
此題應考慮到兩種情況，首先最簡單的一種情況，假設有 1，2，3，4，5 個元素依次進入自定義的隊列，再依次取出。由于是進棧操作都進行完了才進行出棧操作，所以我們只需在元素出隊時，將進棧元素倒入另一個空棧中即可。示意圖如下：
再一種情況是，如果 add poll 操作是交替進行的，那么如何保證數(shù)據(jù)結構先進先出的定義呢？比如先放入 1，2，3然后要進行一次取出操作取出 1，隨后在進行 add 操作放入4，5，這種情況下如何操作兩個棧，才能保證之后再取出的時候元素為 2，3，4，5 順序？實際上我們只需要保證一下兩點就可以：
- 無論如果 StackA（最開始add元素的那個棧） 要往 StackB 中壓入元素，那么必須選擇一次性全部壓入。
- 無論什么時候從隊列中取元素，必須保證元素是從 StackB 中 pop 出的，也就是說，當 StackB 不為空的時候絕不能再次向 StackB 中壓入元素。
為了方便理解可以看下邊這幅圖：
明白了需要注意的點后就是該寫代碼的時候了，需要注意的點在圖中已經(jīng)用紅色字體標出了，也就是在存入元素一直往 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;
}
兩個隊列實現(xiàn)一個棧 （?????）
上道題我們完成了兩個棧實現(xiàn)一個隊列的題目，那么兩個隊列實現(xiàn)一個棧又該注意哪些呢？
首先隊列是先進先出，我們可以發(fā)現(xiàn)隊列無論怎么倒，我們不能逆序一個隊列。既然不能套用上題的解法，那么就得另謀出路，但是可以預知無非就是兩個隊列進行交替的入隊出隊操作，那么唯一要做的就是判斷目前出隊的值是否是按照放入元素順序中最后放入的元素。 依舊畫圖舉例
這里我們只看首次取出操作，那么需要注意一點， 如何判斷哪一次取出操作后 QueueA 為空？
事實上作為 Queue 作為容器，我們可以通過事先定義好的方法 queue.size() 去判斷一個隊列中元素的個數(shù)，有人可能說這是犯規(guī)，其實不是的。題目中給出是讓你用隊列去實現(xiàn)，那么隊列中公共 API 都是你可以用的。所以可以想象出下面的偽代碼：
//如果 queueA 的大小不為 0 則循環(huán)取出元素
while(queueA.size() > 0){
//被取出的元素
int result = queueA.poll();
// 這里注意我們取出元素后再去判斷一次，隊列是否為空，如果為空代表是最后一個元素
if(queueA.size() != 0){
queueB.add(result)
}else{
return result;
}
}
上文我們只是說了一次取出操作，那么一次取出操作后，再次放入元素應該怎么放，我們似乎又遇到了困難。
與上題不同的是，我們應該先思考如果連續(xù)兩次取出應該怎么操作，上面一次取出后 QueueA 空了，所以我們如果按照相同的思路將 B 中的元素倒入 A 中，那么將會得到 3 ，這看起來沒什么問題。那么如果下一步進行的 push 操作，那么應該放入 QueueA 還是 QueueB 中才能保證元素先進后出的規(guī)則呢，很容易想到是放入 B 中。 那么總結一下操作要點：
- 任何時候兩個隊列總有一個是空的。
- 添加元素總是向非空隊列中 add 元素。
- 取出元素的時候總是將元素除隊尾最后一個元素外，導入另一空隊列中，最后一個元素出隊。
接上圖我們開看第一次取出操作后可能的兩種操作情況：
思路屢清楚了，那么時候寫代碼了：
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++ 代碼實現(xiàn)：
#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;
}
判斷出棧順序是否符合要求（?????）
經(jīng)歷了上兩道題，大家是不是感覺對棧和隊列更反感，哦不對是更了解了呢。（額~ 一不小心把實話說出來了）。下面我們來看第二道題這是一個有關于出棧順序的判斷的題目:
題目: 輸入兩個整數(shù)數(shù)組，第一個表示一個棧的壓入序列，請寫一個函數(shù)，判斷第二個數(shù)組是否為該棧的出棧序列，假設數(shù)組中的所有數(shù)字均不相等。例如序列 1,2,3,4,5 是某棧的壓入順序，序列 4,5,3,2,1 是該壓棧序列對應的一個彈出序列，但 4,3,5,1,2 就不可能是該壓棧序列的彈出序列。
看到這道題我們首先應該去理解題目中的怎么去判斷是否符合出棧順序，其實題目想要表達的意思是如果以數(shù)組 A 的方式進棧但并不是一次全部進棧，比如我們先進棧1，2，3，4 然后出棧 4，然后進棧 5，然后在出棧 5，3，2，1。 那么什么情況下是不可能滿足的出棧順序呢？比如 1，肯定是比 2 先進棧的，所以 2肯定比 1先出棧。所以解題的關鍵就在于，如何判斷數(shù)組2 中的元素，是按數(shù)組1 中某種進棧順序操作的出棧序列。
思路是如果我們在進棧的同時維護一個出棧角標，如果棧頂元素等于 popA[popIndex] 的時候，將角標加一，并出棧該元素，并繼續(xù)判斷下一個棧頂元素，如果棧頂元素不等于 popA[popIndex] 的時候繼續(xù)入棧元素，直到所有元素入棧完畢如果，棧不為空則表示 popA 不是一個出棧序列。通過下圖可以更好的理解題目要考察的內容：
所以在編程的只需要注意一下三點：
- 執(zhí)行放入操作后，如果棧頂?shù)脑氐扔趯菢嗽?popA 數(shù)組中的元素值，那么就需要出棧該元素，同事角標加1
- 如果棧頂?shù)脑夭坏扔趯菢嗽?popA 數(shù)組中的元素值，那么就執(zhí)行放入操作。
- 待所有的元素都被放入棧中，此時如果棧為空，那么 popA 就是一個出棧序列，反之則不是。
下面看代碼實現(xiàn)：
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++實現(xiàn)如下
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
位運算
上一小節(jié)我們用三道題了解一下面試過程中棧和隊列的常見面試題。本小節(jié)筆者將通過幾個位運算的題目來帶大家熟悉下常用的位運算知識。
相比于棧和隊列來講，筆者自身認為位運算需要掌握的知識就要多一些，包括對于數(shù)字的二進制表示，二進制的反碼，補碼。以及二進制的常見運算都需要了解。當然如果系統(tǒng)的去學，可能沒有經(jīng)歷，也可能即使學完了，仍舊不會做題。所以筆者認為通過直接去刷一些相應的題目，則是一個比較便捷的途徑。
給定一個整數(shù)，請寫一個函數(shù)判斷該整數(shù)的奇偶性（?????）
該題目作為后續(xù)題目的鋪墊，看上去還是沒有任何難度的。主要考察了面試能否想到用二進制的位運算方法去解決。
首先整數(shù)可以分為正數(shù)，負數(shù)，0。也可以分為奇數(shù)和偶數(shù)。偶數(shù)的定義是：如果一個數(shù)是2的整數(shù)倍數(shù)，那么這個數(shù)便是偶數(shù)。如果不使用位運算的方法，我們完全可以使用下面的方式解決：
public boolean isOdd(int num){//odd 奇數(shù)
return num % 2 != 0;
}
可是面試題不可能去簡單就考察這么簡單的解法，進而我們想到了二進制中如果 一個數(shù)是偶數(shù)那么最后一個一定是 0 如果一個數(shù)是奇數(shù)那么最后一位一定是 1；而十進制 1 在 8 位二進制中表示為 0000 0001，我們只需將一個數(shù)個 1相與（&） 得到的結果如果是 1 則表示該數(shù)為奇數(shù)，否知為偶數(shù)。所以這道題的最佳解法如下：
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 << "是否是奇數(shù) ： " << IsOdd(1) <<endl;
std::cout << "是否是奇數(shù) ： " << IsOdd(4) <<endl;
return 0;
}
//結果
是否是奇數(shù) ： 1//是 true
是否是奇數(shù) ： 0//不是 false
同樣給定一個整數(shù)，請寫一個函數(shù)判斷該整數(shù)是不是2的整數(shù)次冪（?????）
這道題仍舊考察面試者對于一個數(shù)的二進制的表示特點，一個整數(shù)如果是2的整數(shù)次冪，那么他用二進制表示完肯定有唯一一位為1其余各位都為 0，形如 0..0100...0。比如 8 是 2的3次冪，那么這個數(shù)表示為二進制位 0000 1000 。
除此之外我們還應該想到，一個二進制如果表示為 0..0100...0，那么它減去1得到的數(shù)二進制表示肯定是 0..0011..1 的形式。那么這個數(shù)與自自己減一后的數(shù)相與得到結果肯定為0。
如：
所以該題最佳解法為：
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的整數(shù)次冪 ： " << IsLog2(1) <<endl;
std::cout << "是否是2的整數(shù)次冪 ： " << IsLog2(3) <<endl;
return 0;
}
//結果
是否是2的整數(shù)次冪 ： 1 //是 true
是否是2的整數(shù)次冪 ： 0 //不是 false
給定一個整數(shù)，請寫一個函數(shù)判斷該整數(shù)的二進制表示中1的個數(shù)（?????）
此題較之上一題又再進一步，判斷一個整數(shù)二進制表示中1的個數(shù)，假設這個整數(shù)用32位表示，可正可負可0，那么這個數(shù)中有多少個1，就需要考慮到符號位的問題了。
相信讀者應該都能想到最近基本的解法即通過右移運算后與 1 相與得到的結果來計算結果，如果采用這種解法，那么這個題的陷阱就在于存在負數(shù)的情況，如果負數(shù)的話標志位應該算一個1。所以右移的時候一定要采用無符號右移才能得到正確的解法。
ps 對于正數(shù)右移和無符號右移得到結果一樣，如果是負數(shù)，右移操作將在二進制補碼左邊添加追加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 數(shù)作為 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的個數(shù) ： " << count1(-1) <<endl;
std::cout << "二進制中1的個數(shù) ： " << count1(1) <<endl;
return 0;
}
//結果
二進制中1的個數(shù) ： 32
二進制中1的個數(shù) ： 1
能回答出上邊的答案你的面試肯定是及格了，但是作為練習來說，是否有額外的解法呢？首先上述結果最壞的情況可能需要循環(huán)32次。上面我們算過一道如何判斷一個數(shù)是否是2的整數(shù)倍，我們用過了 n&(n-1)==0 的方法。其實該題的第二個解法也可以用這個方法。為什么呢？我們開看一次上邊的圖：
我們是否能發(fā)現(xiàn)，每次與比自己小1的數(shù)與那么該數(shù)的二進制表示最后一個為1位上的1將將會被抹去。其實這是一個知道有這種原理才能想到的方法，所以大家也不用哀嘆說我怎么想不到，通過這次記住有這個規(guī)律下次就多一個思路也不是很么壞事。
下面我們來看下判斷一個數(shù)中有多少個1的完整圖解：
所以我們可以通過如下方法來得到題解，這樣我們可以減少移動次數(shù)
public int countA(int n){
int res = 0;
while(n != 0){
n &= (n - 1);
res++;
}
return res;
}
#include "iostream"
using namespace std;
// 同上傳入無符號整數(shù)
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的個數(shù) ： " << countA(-1) <<endl;
std::cout << "二進制中1的個數(shù) ： " << countA(1) <<endl;
return 0;
}
//結果
二進制中1的個數(shù) ： 32
二進制中1的個數(shù) ： 1
在其他數(shù)都出現(xiàn)兩次的數(shù)組中找到只出現(xiàn)一次的那個數(shù)（?????）
這道題同樣是考察為位運算的一道題，但是如果對于不熟悉位運算的朋友可能壓根都不會往這方面想，也許當場直接就下邊寫下了遍歷數(shù)組記每個數(shù)出現(xiàn)次數(shù)的代碼了。其實這道題要求在時間復雜度在O(n) 空間復雜度為O(1)的條件下，那種解法是不符合要求的。我們來看下為位運算的解題思路。
首先我們應該知道二進制異或操作，異或結果是二進制中兩個位相同為0，相異為1。因此可以有個規(guī)律：
任何整數(shù) n 與 0 異或總等于其本身 n，一個數(shù)與其本身異或那么結果肯定是 0。
還需要知道一個規(guī)律：
多個數(shù)異或操作，遵循交換律和結合律。
對于第一條朋友們肯定都很好理解，然而第二條規(guī)律才是這道題的解題關鍵。如果我們有一個變量 eO = 0 那么在遍歷數(shù)組過程中，使每個數(shù)與 eO 異或得到的值在賦值給額 eO 即 eO=eO ^ num 那么遍歷結束后eO的值一定是那個出現(xiàn)一次的數(shù)的值。這是為什么呢？我們可以舉個例子：
假設有這么一個序列： C B D A A B C 其中只有 D 出現(xiàn)一次，那么因為異或滿足交換律和結合律，所以我們遍歷異或此序列的過程等價于
eO ^ (A ^ A ^ B ^ B ^ C ^ C ) ^ D = eO ^ 0 ^ D = D
所以對于任何排列的數(shù)組，如果只有一個數(shù)只出現(xiàn)了奇數(shù)次，其他的數(shù)都出現(xiàn)了歐數(shù)次，那么最終異或的結果肯定為出現(xiàn)奇數(shù)次的那個數(shù)。
所以此題可以有下面的這種解法：
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 << "出現(xiàn)奇數(shù)次的那個數(shù)： " << oddTimesNum(arr) <<endl;
return 0;
}
//結果
出現(xiàn)奇數(shù)次的那個數(shù)： 5
關于這道題還有個延伸版本，就是如果數(shù)組中出現(xiàn)1次的數(shù)有兩個，那么該如何得到這兩個數(shù)。
在其他數(shù)都出現(xiàn)兩次的數(shù)組中找到只出現(xiàn)一次的那兩個數(shù)（?????）
我們順著上題的思路來思考，如果有兩個數(shù)獲得的結果 eO 肯定是 eO = a^b,此題的關鍵就在于如何分別得到 a，b 這兩個數(shù)。我們應該想到，任何不相同的兩個除了跟自己異或外，不可能每一個位都相同，也就是說不相同的兩個數(shù) a b 異或得到結果二進制表示上肯定有一位為 1。 這是關鍵。
我們可以假設第 k 位不為 0 ，那么就說明 a 與 b 在這位上數(shù)值不相同。我們要做只是設置一個數(shù)第 k 位 為 1，其余位為 0 記為 rightOne。
這時需要拿 eOhasOne = 0 再異或遍歷一次數(shù)組，但是需要忽略與 rightOne 相與等于 0 的數(shù)。因為相與等于 0 則代表了這個數(shù)肯定是兩個數(shù)中第 k 位不為 1的那個。最終得到的 eOhasOne 就是 a b 中第 k 為為 1 的那個。
那么接下來就剩下一個問題要解決了，如何找到 rightOne ，這里采用與本身補碼相與的方法得到即 int rightOne = eO & (~eO + 1) 。
可以參照下圖來理解下整個過程：
我們來看下最終的代碼:
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<<"一個出現(xiàn)1次的數(shù) " << eOhasOne << endl;
std::cout<<"二個出現(xiàn)1次的數(shù) " << (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;
}
//結果：
一個出現(xiàn)1次的數(shù) 5
二個出現(xiàn)1次的數(shù) 4
總結
本文列舉了棧隊列以及位運算的一些面試題目，通過這些面試題目我們可以了解到一些面試中算法的考點，對于位運算相關題目，我們還是需要多加練習，但是不要害怕自己某些地方不會限制了解題思路，通過多加練習，記住見過的解題中的規(guī)律，相信經(jīng)過一段時間練習后，也會感受到自我的提高。
最后歡迎大家關注我的掘金專欄，不定時分享一些自己的學習工作總結。
參考
《劍指 offer 第二版》
《程序員代碼面試指南 - 左程云》
