概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day13 「338. Counting Bits」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
問題
難易度はeasy。
こちらの問題もTop 100 Liked Questionsからです。
やたらGood数が多いのでなんでだろう？と思っていたのですが、解いてみたらあーなるほどってなったので実際に解法をみる前に自分で解いてみると良いかもしれません。
問題としては、空ではない数字の配列が与えられるので、その中に二つ表示されていない数値を抜き出して返してください、とのことです。
Example 1:
Input: [2,2,1]
Output: 1
こちらの例だと1のみが配列の中に1個しかないので1を返します。
Example 2:
Input: [4,1,2,1,2]
Output: 4
こちらの例だと4のみが配列の中に1個しかないので４を返します。
解法
今回は少し情報系について知っているような書き方をしてみました。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for n in nums:
ans ^= n
return ans
# Runtime: 80 ms, faster than 93.89% of Python3 online submissions for Single Number.
# Memory Usage: 16.5 MB, less than 6.56% of Python3 online submissions for Single Number.
Pythonに詳しくない方は
ans ^= n
これなんだよってなるかもしれないので補足しておくと、排他的論理和（XOR）を表す代入演算子ですね。
多くの方がご存知のように、二つの入力のうち、どちらか一方のみが1のときに1をを返すようなXORはこの問題にうってつけです。
実際、解いた後にDiscussを覗いてみたらXORを使った答えが多かったですね。
もう少しいい答えがありそうならば追記します。