iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 17
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 17

【從面試題學邏輯-17】找一個不會影分身的傢伙怎麼這麼討人厭?(leetcode 137. Single Number II)

題目:
請寫一個方法,找出int陣列中只出現過一次的數字,其他數字都會出現三次

舉例:
輸入{1,1,3,1}的話,應該要輸出3

點我前往LeetCode題目


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


這題是single number的續集,讓我們先列出一個邏輯吧!/images/emoticon/emoticon12.gif
(還沒有看過前面題目的話,建議先去看看喔)

  1. 和single number一樣,我們可以用一個int,加上XOR的方法找出答案。
  2. 由於其他數字會重複三次,XOR做三次會導致最後大家都出現在答案內,所以要另外用東西紀錄「它出現兩次了」。當然我們可以繼續利用XOR的作法,用一個int紀錄出現第二次,如果出現兩次就不加入找答案的數字。

讓我們先上程式碼再一一解釋:

class Solution {
    public int singleNumber(int[] nums) {
        int one=0, two=0;
        for(int n : nums) {
            one = (one^n) & ~two;
            two = (two^n) & ~one;
        }
        return one;
    }
}

除了one, two之外都是啥東西?!

讓我們逐一解釋一下流程

首先one, two的運作邏輯應該是這樣:

  1. 如果不在one或two內,就塞進one內
  2. 如果在one內,把one內的東西刪掉,再塞進two內
  3. 如果在two內,就把two內的東西刪掉

實際上流程是:

  1. 先塞進one內XOR,如果two內有的話,把剛剛的動作取消
  2. 先塞進two內XOR,如果one內有的話,把剛剛的動作取消

所以說,我們把{1,1,1}丟進去的話,one和two的變化應該要是:

那大家一定會問& ~one& ~two到底是幹嘛用的?

因為上面的程式碼一定會先把n丟進one及two內做XOR,所以後面的東西是「如果不應該把n丟進去XOR,就把前面的動作取消」

大家知道 1 & ~1 = 0 這件事對吧?(1和反1做AND會抵消)

& ~two就代表說,如果n已經在one內,而two中也有nn就會被抵銷。因為two內的n變成了~n(反n)

& ~one相同,如果n已經在two內,而one中也有nn就會被抵銷。因為one內的n變成了~n(反n)

大家可以試著在腦中想像{1,1,1}丟進去這串程式碼後的運作過程,想像一下就會通了


這樣位元運算就結束嘍

明天開始我們來進入遞迴的題目


上一篇
【從面試題學邏輯-16】拔智齒可以不要寫鐵人賽嗎?好像不能這樣做诶(leetcode 78. Subsets)
下一篇
【從面試題學邏輯-18】用遞迴找子集似乎把事情搞得更難懂了……(leetcode 78. Subsets)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言