Leetcode挑戰: Day11 single number

為了加強自己的程式能力，因此開始記錄每天刷leetcode的解法+說明，會用Ruby、python和JavaScript三個語言來解題，今天是第十一天，讓我們開始吧！

題目來源：leetcode

Ruby

1
2
3

def single_number(nums)
  nums.reduce(:^)
end

這次用到XOR符號^，這是種運算邏輯，用於對兩個二進制數的對應位進行比較，規則如下：兩個對應位數字不同，會回傳1，兩個對應位不同則會回傳0，用此來找出只出現一次的數字。

範例如下：

1
2
3
4

0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0

如果我們傳入[4, 1, 2, 1, 2]呢？根據reduce(:^)會這樣運算4 ^ 1 ^ 2 ^ 1 ^ 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

  4:  100
  1:  001
XOR:  101  

  5:  101
  2:  010
XOR:  111 

  7:  111
  1:  001
XOR:  110 

  6:  110
  2:  010
XOR:  100

也可以用另外一個方法理解，1 ^ 1 = 0, 2 ^ 2 = 0, 0 ^ 4 = 4
只要有不同於其他的數，就會被留下來，這樣答案就出來了！

Python

1
2
3

class Solution:
    def singleNumber(self, nums):
        return reduce(lambda x, y: x ^ y, nums)

Python也是一樣邏輯，只不過reduce寫法不同，可以參考：reduce

JavaScript

1
2
3

var singleNumber = function(nums) {
    return nums.reduce((acc, num) => acc ^ num, 0);
  };

JS也是一樣邏輯，只不過reduce寫法不同，可以參考：reduce