leetcode:136
<b>Question</b>(leetcode:136): Given an array of integers, every element appearstwiceexcept for one. Find that single one.(給定一個(gè)整型數(shù)組,每一個(gè)元素出現(xiàn)兩次,只有一個(gè)元素出現(xiàn)一次,找到這個(gè)元素)
import operator
class Solution:
def singleNumber(self,A):
return reduce(operator.xor,A)
if __name__ == '__main__':
print Solution().singleNumber([1,1,2,3,2,4,4])
- 其中我們導(dǎo)入了python的operator的庫(kù),這個(gè)庫(kù)主要提供一些基本的函數(shù)操作,這個(gè)函數(shù)中主要使用xor函數(shù)(異或函數(shù))
xor(a,b) -> same as a ^ b
- 我們用到了python的高階函數(shù)-reduce
reduce把一個(gè)函數(shù)作用在一個(gè)序列[x1, x2, x3...]上谜洽，這個(gè)函數(shù)必須接收兩個(gè)參數(shù)萝映，reduce把結(jié)果繼續(xù)和序列的下一個(gè)元素做累積計(jì)算，其效果就是：
reduce(f, [x1, x2, x3, x4]) = f(f(f(x1, x2), x3), x4)
reduce(operato.xor,A) 等于下面
(( (1 ^ 1) ^ 2) ^ 3).....
- 核心是
((a ^ b) ^ a) = b
leetcode:137
<b>Question</b>: Given an array of integers, every element appears three times except for one. Find that single one.(給定一個(gè)數(shù)組,每一個(gè)元素出現(xiàn)3次,除了一個(gè)找到這一個(gè))
class Solution3:
def singleNumber(self,A ):
one,two,three = 0,0,0
for x in A:
#是否是第二次相同
two = one & x | two
one = one ^ x
three = one & two
one = one & ~three
two = two & ~three
print 'one:%x,two:%x,three:%x' % (one,two,three)
if __name__ == '__main__':
print Solution3().singleNumber([4,4,3,4,1,1,1,2,3,3])
