Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

tags:

- Hash Table
- Bit Manipulation

```
def singleNumber(self, A):
return 2*sum(set(A)) - sum(A)
```

```
def singleNumber(self, A):
return reduce(operator.xor,A)
```

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

tags:

- Bit Manipulation

```
class Solution:
# @param A, a list of integer
# @return an integer
def singleNumber(self, A):
ec1, ec2, ec3 = 0, 0, 0
for ai in A:
ec3 = ec2 & ai
ec2 = (ec2 | (ec1 & ai)) & (~ec3)
ec1 = (ec1 | ai) & (~ec3)
return ec1
```

Image the numbers in A have just one bit,

that is: A = [0, 0, 0, 1, 1, 1, x]

We have three times "0", three times "1", and a different "x".

So, if count of "1" in A is three's multiple, than x = 0,

else, x = 1.

Iterate all numbers in A.

When encount FIRST "1", set "ec1 = 1";

When encount SECOND "1", set "ec2 = 1";

When encount THIRD "1", set "ec3 = 1, ec1 = 0, ec2 = 0", and move on...

At last "ec1" is the different number.

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

tags:

- Tree
- Depth-first Search

```
def maxDepth(self, root):
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
```

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

tags:

- Tree
- Depth-first Search

```
def isSameTree(self, p, q):
if p == None and q == None:
return True
elif p and q :
return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
else :
return False
```

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

tags:

- Math
- String

```
class Solution:
# @return an integer
def romanToInt(self, s):
roman = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
sum = 0
for index, i in enumerate(s):
if index == 0:
sum += roman[i]
continue
if roman[i] <= roman[s[index - 1]]:
sum += roman[i]
else:
sum = sum - 2 * roman[s[index - 1]] + roman[i]
return sum
```

```
class Solution:
# @return an integer
def romanToInt(self, s):
dic = {
'I': lambda i: -1 if s[i + 1] in ['V', 'X'] else 1,
'X': lambda i: -10 if s[i + 1] in ['L', 'C'] else 10,
'C': lambda i: -100 if s[i + 1] in ['D', 'M'] else 100,
'V': lambda i: 5,
'L': lambda i: 50,
'D': lambda i: 500,
'M': lambda i: 1000,
}
x = 0
s += '@'
for i, ch in enumerate(s[:-1]):
x += dic[ch](i)
return x
```

```
class Solution:
# @return an integer
def romanToInt(self, s):
result=0
dic={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
for i in s[-1::-1]:
symbol=1
if (i in ['I','X','C']) and result>=5*dic[i]:
symbol=-1
result+=dic[i]*symbol
return result
```

The main problem is to deal with the special numbers "IV","IX","XL","XC","CD","CM",for in these numbers "I","X","C" have the unusual meaning(subtract not plus).

If given a Roman without numbers mentioned above,we can easily get the result by plusing all the numbers from right to left . So we need to find out what "I","X","C" mean when they appear(mean plus or subtract).

"I" for example,the symbol "I" only appear in following circumstances: "I","II","III","VI",VII","VIII","IV","IX","XI"ยทยทยทยท(omitting "IIII" for it is special) .

We can figure out that when we plus the symbols from left to right. If sum>=5,then the "I" we get can only mean "-1".Otherwise,it means "+1".The same is true with "X" and "C".