Single Number

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:

def singleNumber(self, A):
    return 2*sum(set(A)) - sum(A)
def singleNumber(self, A):
    return reduce(operator.xor,A)

Single Number II

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:

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.

Maximum Depth of Binary Tree

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:

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

Same Tree

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:

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

Roman to Integer

Given a roman numeral, convert it to an integer.

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

tags:

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".