資訊專欄INFORMATION COLUMN
摘要：解決方案異或操作異或運算是對于二進制數字而言的，比如說一個有兩個二進制，如果兩個值不相同，則異或結果為。比如說，本質上其實是和的每一對比特位執行異或操作，等價于下面數字對應的二進制數字對應的二進制數字對應的二進制因此的結果就為啦。
新年第一篇文章，先祝大家新年快樂??！那么接下來進入正文。
前言前陣子突發奇想，突然開始刷leetcode。其中刷到了一道有意思的題目，發現這道題是當時秋招的時候，騰訊面試官曾經問過我的題目。于是分享給大家看下。
題目描述給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。
初步解法這道題第一眼看過去，思路挺簡單的，我們只需要維護一個對象來記錄每一個元素出現的次數，使用元素的值作為key,元素出現的次數作為value。之后再遍歷這個對象，找到value為1的key。對應的key就是那個元素。代碼如下:
function singleNumber(nums) {
const obj = {};
for (let i = 0; i < nums.length; i++) {
obj[nums[i]] = obj[nums[i]] ? obj[nums[i]] + 1 : 1;
}
for (let key in obj) {
if (obj[key] === 1) {
return Number(key); // 由于 key 是 string ,因此我們這里需要轉化下
}
}
}
console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8])); // 8
增加限制
是吧，這道題很簡單，那我為什么要說它有意思呢？
因為題目里面其實還有一個限制：
你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎？
重點在于不使用額外空間。我們上面那種解法，創建了一個新的對象來儲存結果，明顯是不行的。那么有沒有辦法可以只使用原來的數組來實現這個功能呢？
最終解法我們可以思考下，一個數組里，所有的數字都出現兩次，除了一個我們要找的數字只出現一次。那么，我們有沒有辦法將兩個相同的數字給過濾掉呢？
好啦，不賣關子了，之前有了解過的人應該就知道解決方案了，如果之前沒了解過這方面東西的人，可以繼續往下看。
解決方案：異或操作
異或運算是對于二進制數字而言的，比如說一個有兩個二進制a、b，如果a、b兩個值不相同，則異或結果為1。如果a、b兩個值相同，異或結果為0。
而javascript的按位異或(即^操作)操作，則會對兩個數字相應的每一對比特位執行異或操作。
比如說 1 ^ 2，本質上其實是1和2的每一對比特位執行異或操作，等價于下面
00000000000000000000000000000001 // 數字1對應的二進制 ^ 00000000000000000000000000000010 // 數字2對應的二進制 = 00000000000000000000000000000011 // 數字3對應的二進制
因此1^2的結果就為3啦。
那么如果兩個相同的數字進行異或操作，結果就可想而知，答案為0啦。
如果是0和任何一個數字異或呢？結果是數字本身。
我們舉個栗子：
假設我們有一個數組，里面元素為[a, a, c, c, b, b, d]。那么我們對數組里的所有元素進行按位異或操作，即a ^ a ^ c ^ c ^ b ^ b ^ d,是不是就等價于0 ^ 0 ^ 0 ^ d = d。而d就是數組里只出現一次的元素。
那么我們可以擴展一下，對于任意滿足某個元素只出現一次以外，其余每個元素均出現兩次的數組，是不是可以通過這種方式來得到那個只出現一次的元素。
這樣一來的話，我們是不是有了這個問題的解決辦法了？我們只需要遍歷數組，將所有的值取異或，最終剩下的值，就是那個只出現一次的數字。代碼如下：
/**
* 只存在一次的數字
* https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/
* @param {number[]} nums
* @return {number}
*/
function singleNumber(nums) {
for (let i = 1; i < nums.length; i++) {
nums[0] ^= nums[i];
}
return nums[0];
};
console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8]));
結語
這道面試題主要考驗面試者對異或的理解，以及能不能活學活用，將這道題與異或聯系在一起。當然，最重要的還是多學習、多刷題、多看書。這樣才能不斷進步。
本文地址在->本人博客地址, 歡迎給個 start 或 follow
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100669.html
摘要：但是題目非要弄成鏈表的形式，說實在的，我真沒有見過前端什么地方還需要用鏈表這種結構的除了面試的時候，所以說這種題目對于實際工作是沒什么用處的，但是腦筋急轉彎的智商題既然這樣出了，我們就來看看怎么解決它吧。 今天在知乎上看到一個回答《為什么前端工程師那么難招？》，作者提到說有很多前端工程師甚至連單鏈表翻轉都寫不出來。說實話，來面試的孩子們本來就緊張，你要冷不丁問一句單鏈表翻轉怎么寫，估計...
摘要：重溫一個面試題內容數組內容為數組內容為個英文字母，使用兩個線程分別輸入兩個數組，打印內容為這樣的規律提取一下核心內容，去除次要內容兩個線程需要交替執行，打印數字的線程需要先執行，數組打印完畢后線程需要結束。 一道多線程面試題引起的自我救贖 近日去一個知名互聯網企業參加面試，之前準備多多信心滿滿，但是面試一開始就是一道不起眼的編程題 數組A內容為 1,2,3,4...52 ,數組B內容...
摘要：據了解，現在前端面試也喜歡考算法題了。下面說一個跟前端有點相關并且有點趣的一道算法題。遍歷二維數組連續的個數連續的個數形狀的總數第幾個形狀形狀的面積最后的代碼圖片路徑讀取整張圖片的像素。 據了解，現在前端面試也喜歡考算法題了。前幾天去面試，果不其然的，面試官給我四道算法題，讓我自己回去做。下面說一個跟前端有點相關并且有點趣的一道算法題。 題目： 平面上有若干個不特定的形狀，如下圖所示...
摘要：正如我標題所說，簡歷被拒?？戳宋液啔v之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學投稿的面試經歷 關注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學的分享 目錄： 印象中的頭條 面試背景 準備面試 ...
閱讀 4025·2021-11-22 13:53
閱讀 1724·2021-09-23 11:52
閱讀 2443·2021-09-06 15:02
閱讀 948·2019-08-30 15:54
閱讀 907·2019-08-30 14:15
閱讀 2391·2019-08-29 18:39
閱讀 662·2019-08-29 16:07
閱讀 427·2019-08-29 13:13
