一、题目

Single Number II

二、解题

需要注意题目的意思是，所有数都出现了3次，除了一个（这个只出现了一次）
线性的复杂度，首先想到的是遍历一次用字典储存。

• 如果键不在字典里面，则加入并设置值为1
• 如果键在字典里面，判断是否为2（因为加起来等于3了），如果是2，就删除该键；否则加一
• 最后字典里面只有一个键，即为所求

三、尝试与结果

class Solution(object):
    def singleNumber(self, nums):
        resultDic = {}
        for i in nums:
            if i in resultDic.keys():
                if resultDic[i] == 2:
                    del resultDic[i]
                else:
                    resultDic[i] = resultDic[i] + 1
            else:
                resultDic[i] = 1
        return list(resultDic.keys())[0]

结果：喜闻乐见TL

超时用例1.6s

四、学习与记录

class Solution(object):
    def singleNumber(self, nums):
        one = 0
        two = 0
        three = 0
        for i in range(0,len(nums)):
            two |= one & nums[i] #当新来的为0时，two = two | 0，two不变，当新来的为1时，（当one此时为0，则two = two|0，two不变；当one此时为1时，则two = two | 1，two变为1
            one ^= nums[i]       #新来的为0，one不变，新来为1时，one是0、1交替改变
            three = one & two    #当one和two为1是，three为1（此时代表要把one和two清零了）
            one &= ~three        #把one清0
            two &= ~three        #把two清0
        return one 

说明：
这个解法可以初学者会看不明白，详细说明一下：
1）有个数只出现一次，换个思考角度表达，用二进制的思考，即二进制每一位上都有一个数只出现一次
那对上面三个数1、2、1（简单为例子使用4位表示）：
0,0,0,1
0,0,1,0
0,0,0,1

第一位：1,0,1
第二位：0,1,0
第三位：0,0,0
第四位：0,0,0

2）我们使用三个变量one、two、three来存储每一个位上出现的1、2、3次的情况（其实是模拟了3进制的概念），拿第一位思考（特别注意one、two、three的每一位，都表示当前位出现了1次）
使用上面的第一位的序列1,0,1为例子

• 第一位来了1，则one变成1，two不变，three不变
• 再来0，one不变，two不变，three不变
• 再来1，one需要变成0，two变成1，three不变

此时，加入再来一个1，则one变成1，two也是1，three变成0（此时就需要进位了）
要变成one为0，two为0，three为1（算法的要进行的模拟的三进制操作就是这个）

3）因此，"拼凑"出的算法就是
two = two | (one & num[i])
one = one ^ num[i]
three = one & two
one = ~three
two = ~three