def maxDepth(self, root):

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

• map(函数，iterable的object）-> 把函数逐个用在对象的元素上，返回一个list

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p and not q:
            return False
        if not p and q:
            return False
        while p and q:
            if p.val != q.val:
                return False
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right);
        return True

Use self to refer to instance variables and methods from other instance methods. Also put self as the first parameter in the definition of instance methods.

A example:

class MyClass(object):

    my_var = None

    def my_method(self, my_var):
         self.my_var = my_var
         self.my_other_method()

    def my_other_method(self):
         # do something...

判断数组是否有重复的元素

# Method 1 -- Apply hashtable O(n)
    # hashNum = {}
    # for i in nums:
    #     if i not in hashNum:
    #         hashNum[i] = 1
    #     else:
    #         return True
    # return False

    # Method 2 -- Sorting
    # l =  len(nums)
    # if l < 2:
    #     return False
    # nums.sort()
    # for i in range(l-1):
    #     if nums[i] == nums[i+1]:
    #         return True
    # return False

    # Method 3 -- Set solution for python
    numsSet =  set(nums)
    if len(nums) == len(numsSet):
        return False
    return True

找二叉树的Lowest Common Ancester
​def lowestCommonAncestor(self, root, p, q):

        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root==None:
            return None
        if root==p or root==q:
            return root
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)
        if l and r:
            return root
        else:
            if l:
                return l
            if r:
                return r

“移位”等于“乘除” ---- 找二进制数里面的1

    int hammingWeight(uint32_t n) {
        int rtn = 0;
        while(n!=0){
            if(n&1==1) rtn ++;
            n = n >> 1;
        }
        return rtn;
    }

def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<2:
            return n
        else:
            if n%2==1:
                return self.hammingWeight(n/2)+1
            else:
                return self.hammingWeight(n/2)

In Python 3 the ordinary / division operator returns floating point values even if both operands are integers.

 // means integer division

Python String Operations

def titleToNumber(self, s):
        """
        :type s: str
        :rtype: int
        """
        rtn = 0
        for i in range(len(s)):
            c = s[-1]
            s = s[:-1]
            rtn += (ord(c)-64) * pow(26, i)
        return rtn

chr(n) -- get the character of ascii n

Python 超偷懒的iteration ---- 判断两字符的字母组成是否相同

    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        # Method 1: Hash - using dictionary (array)
        
        map = {}
        
        for c in s:
            if c not in map:
                map[c] = 1
            else:
                map[c] += 1
        for c in t:
            if c not in map:
                map[c] = -1
            else:
                map[c] -= 1
        for key in map:
            if map[key] != 0:
                return False
        return True

判断对象是否为None

def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head==None or head.next==None:
            return head
        c = head.next
        head.next = None
        p = head
        n = c.next
        while(c!=None):
            c.next = p
            p = c
            c = n
            if n!=None:
                n = n.next
        return p

关于set ---- 判断一个数是否为happy number

    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        #Hash
        s = set()
        while(n!=1):
            temp = 0
            while(n!=0):
                temp += pow((n%10),2)
                n = n//10
            n = temp
            if n in s:
                return False
            else:
                s.add(n)
        return True

细节细节。。判断是否平衡树

def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        
        
        if root==None:
            return True
        else:
            if self.getHeight(root)!=-2:
                return True
            else:
                return False
        
    def getHeight(self, root):
        if root==None:
            return 0
        l = self.getHeight(root.left)
        r = self.getHeight(root.right)
        if l<0 or r<0:
            return -2
        if abs(l-r)<2:
            return max(l, r)+1
        else:
            return -2

考虑树的时候如果太复杂，少考虑一层 ---- 判断对称树

def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root==None:
            return True
        return self.isSubSymmetric(root.left, root.right)
        
    def isSubSymmetric(self, l, r):
        if l==None:
            return r==None
        if r==None:
            return l==None
        return l.val==r.val and self.isSubSymmetric(l.right, r.left) and self.isSubSymmetric(l.left, r.right)
        
        
        """
        # Method 1: Naive
        if root==None:
            return True
        if root.left==None and root.right==None:
            return True
        if root.left==None and root.right!=None:
            return False
        if root.left!=None and root.right==None:
            return False
        if root.left.val != root.right.val:
            return False
        return self.checkSymmetric(root.left, root.right)
    
    def checkSymmetric(self, n1, n2):
        if n1==None and n2==None:
            return True
        if (n1.left==None and n2.right!=None) or (n1.left!=None and n2.right==None) or (n1.right==None and n2.left!=None) or (n1.right!=None and n2.left==None):
            return False
        if n1.left!=None:
            if n1.left.val != n2.right.val:
                return False
        if n1.right!=None:
            if n1.right.val != n2.left.val:
                return False
        return self.checkSymmetric(n1.left, n2.right) and self.checkSymmetric(n1.right, n2.left)
        """

细节细节：除去某元素

def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        l = len(nums)
        if l==0:
            return 0
        j = l-1
        for i in range(l):
            while nums[i]==val and j>i:
                nums[i], nums[j] = nums[j], nums[i]
                j -= 1
            if j<=i:
                break
        if nums[j]==val:
            return j
        else:
            return j+1

数n!尾部的0

Concept:

Since 0 only company with 5*2 So only need to count the volume of 5 factor. (because 2 always enough)

So.. 100! 's zero has => floor(100/5) + floor(100/25) = floor(100/5) + floor((100/5)/5)
 

class Solution(object):
    def trailingZeroes(self, n):
        zeroCnt = 0
        while n > 0:
            n = n/5; zeroCnt += n

        return zeroCnt

两个单链表后期并成一个单链表，找相交的node

• Two pointer solution (O(n+m) running time, O(1) memory):
  • Maintain two pointers pA and pB initialized at the head of A and B, respectively. Then let them both traverse through the lists, one node at a time. 
  • When pA reaches the end of a list, then redirect it to the head of B (yes, B, that's right.); similarly when pB reaches the end of a list, redirect it the head of A. 
  • If at any point pA meets pB, then pA/pB is the intersection node.
  • To see why the above trick would work, consider the following two lists: A = {1,3,5,7,9,11} and B = {2,4,9,11}, which are intersected at node '9'. Since B.length (=4) < A.length (=6), pB would reach the end of the merged list first, because pB traverses exactly 2 nodes less than pA does. By redirecting pB to head A, and pA to head B, we now ask pB to travel exactly 2 more nodes than pA would. So in the second iteration, they are guaranteed to reach the intersection node at the same time.
  • If two lists have intersection, then their last nodes must be the same one. So when pA/pB reaches the end of a list, record the last element of A/B respectively. If the two last elements are not the same one, then the two lists have no intersections.

边界处理太渣。。。

def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA==None or headB==None:
            return None
        a = headA
        b = headB
        a_go = headB
        b_go = headA
        if a.val==b.val:
            return a
        else:
            if a.next==None:
                a = a_go
                if a_go==headA:
                    a_go = headB
                else:
                    a_go = headA
            else:
                a = a.next
            if b.next==None:
                b = b_go
                if b_go==headA:
                    b_go = headB
                else:
                    b_go = headA
            else:
                b = b.next
        while a.val!=b.val:
            if a==headA or b==headB:
                return None
            if a.next==None:
                a = a_go
                if a_go==headA:
                    a_go = headB
                else:
                    a_go = headA
            else:
                a = a.next
            if b.next==None:
                b = b_go
                if b_go==headA:
                    b_go = headB
                else:
                    b_go = headA
            else:
                b = b.next
        return a

Python set ---- Contains Duplicates with in range k

def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        l = len(nums)
        if k>=l:
            return l>len(set(nums))
        s = set(nums[:k])
        for i in range(k, l):
            if nums[i] in s:
                return True
            else:
                s.add(nums[i])
                s.remove(nums[i-k])
        return False

判断一个list是否为空

# list = []

# method 1
len(list)==0

#method 2
if not list

多开一个数组保持思路清晰Count and Say

def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        rtn = "1"
        for _ in range(n-1):
            i, record, count, s = 0, rtn[0], 1, ""
            for i in range(1, len(rtn)):
                if rtn[i]==record:
                    count += 1
                else:
                    s += str(count) + record
                    count = 1
                    record = rtn[i]
            if count!=0:
                s += str(count) + record
            rtn = s    
        return rtn

相比于重复大块代码，不如开始统一输入形式 Add Binary

        la = len(a)
        lb = len(b)
        if la==0:
            return b
        if lb==0:
            return a
        carry = 0
        m = min(la, lb)
        M = max(la, lb)
        i = 0
        rtn = ""
        if la<lb:
            for _ in range(lb-la):
                a = "0" + a
        if lb<la:
            for _ in range(la-lb):
                b = "0" + b
        for i in range(-1, -1-M, -1):
            s = int(a[i]) + int(b[i]) + carry
            if s>1:
                carry = 1
                s -= 2
            else:
                carry = 0
            rtn = str(s) + rtn
        # if la>lb:
        #     for i in range(-1-m, -1-la, -1):
        #         s = int(a[i]) + carry
        #         if s>1:
        #             carry =1
        #             s -= 2
        #         else:
        #             carry = 0
        #         rtn = str(s) + rtn
        # if la<lb:
        #     for i in range(-1-m, -1-lb, -1):
        #         s = int(b[i]) + carry
        #         if s>1:
        #             carry =1
        #             s -= 2
        #         else:
        #             carry = 0
        #         rtn = str(s) + rtn
        if carry!=0:
            rtn = str(carry) + rtn
        return rtn