一、题目
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
