个人刷Leetcode的一点解法，欢迎批评讨论，每日更新

GitHub: 

singleNumber

Core: A XOR B XOR A XOR C XOR B = C

class Solution(object):    def singleNumber(self, nums):        """        :type nums: List[int]        :rtype: int        """        result = 0        for each in range(len(nums)):            result ^= nums[each]        return result

reverseString

Core: Serializing String Value, then descending the list

class Solution(object):    def reverseString(self, s):        lst = []        for i in range(len(s)):            lst.append(s[-(i + 1)])        lst = ''.join(lst)        return lst

Nim GAME

Core: Second player only win when  total accoumt % 4 = 0

class Solution(object):    def canWinNim(self, n):        val = n % 4        if val != 0:            return True        else:            return False

Counting Bits

Core: 

Each time the value is 2^n

The different between the the first half and second half is only the first digit

Example with 7

0 to 7 is

000

----

001

----

010

011

----

100

101

110

111

The Second half is always "1+Second Half

class Solution(object):    def countBits(self, num):        val = [0]        while len(val) <= num:            val += [i + 1 for i in val]        return val[:num + 1]

Sum of two integers

Core: Implementation of an array of Full Adder

class Solution(object):    def half_adder(self, a, b):        s = a ^ b        cin = a & b        return s, cin    def full_adder(self, a, b, cin):        s1, c1 = self.half_adder(a, b)        s2, c2 = self.half_adder(cin, s1)        c_out = c1 | c2        return s2, c_out    def getSum(self, a, b):        mask = 1        ci = 0        sum_total = 0        while mask <= 0x080000000:            a1 = a & mask            b1 = b & mask            (s, ci) = self.full_adder(a1, b1, ci)            sum_total = sum_total | s            ci <<= 1            mask <<= 1            print "s: " + str(s) + "     ci: " + str(ci)        maximum = 0x7FFFFFFF        mask = 0xFFFFFFFF        if sum_total > maximum:            sum_total = ~(sum_total ^ mask)        return sum_total

Add Digits

Core: 

Dr(n) = n -9floor((n-1)/9) 

Reference:

class Solution(object):    def addDigits(self, num):        """        :type num: int        :rtype: int        """        if num == 0:            return 0        else:            return num - 9 * int((num - 1) / 9)

Maximum Depth of Binary Tree

Core: 

Recursion

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def maxDepth(self, root):        """        :type root: TreeNode        :rtype: int        """        return self.search(root, 0)    def search(self, node, i):        if node is None:            return i        else:            i += 1            a = self.search(node.left, i)            b = self.search(node.right, i)            if a > b:                return a            else:                return b

Two Sum II

Core: 

Binary Search, Ignoring repeat value

Remain: Squeeze is not suitable for this kind of scenes

class Solution(object):    def twoSum(self, numbers, target):        """        :type numbers: List[int]        :type target: int        :rtype: List[int]        """        if not numbers:            return []        for i in xrange(len(numbers)):            if i > 0 and numbers[i-1] == numbers[i]:                continue            ind1 = i            ind2 = len(numbers) - i -1            while ind1 <= ind2:                sumv = numbers[ind1] + numbers[ind2]                if sumv == target:                    return [ind1+1, ind2+1]                elif sumv > target:                    ind2 -= 1                else:                    ind1 += 1

Find the Difference

Core: Sort,Serializing String Value

class Solution(object):    def findTheDifference(self, s, t):        """        :type s: str        :type t: str        :rtype: str        """        s = list(s)        s.sort()        t = list(t)        t.sort()        for i in range(len(s)):            if s[i] != t[i]:                return t[i]        return t[len(t)-1]

Invert Binary Tree

Core: Recursion

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def invertTree(self, root):        """        :type root: TreeNode        :rtype: TreeNode        """        self.invert(root)        return  root    def invert(self, node):        if node is not None:            template = node.left            node.left = node.right            node.right = template            self.invert(node.left)            self.invert(node.right)

singleNumber

Core: A XOR B XOR A XOR C XOR B = C, Use Bit with different value in the two single value to regist each value in list(otherwise, divide list with the regist bit)

Reference：

class Solution(object):    def singleNumber(self, nums):        """        :type nums: List[int]        :rtype: List[int]        """        result = [0, 0]        x = 0        for each in nums:            x ^= each        # x = result_1 XOR result_2        x &= -x        for each in nums:            if each & x == 0:                result[0] ^= each            else:                result[1] ^= each        return result

Move Zeroes

class Solution(object):    def moveZeroes(self, nums):        """        :type nums: List[int]        :rtype: void Do not return anything, modify nums in-place instead.        """        real_i = 0        for each in xrange(0,len(nums)):            nums[real_i] = nums[each]            if nums[real_i] != 0:                real_i += 1        for each in xrange(real_i, len(nums)):            nums[each] = 0

Linked List Random Node

Core: Recursion, for elements in an unknow list, fisrt of all, get 1 elements as output, for the following recursion, use 1/n(current recursion deep +1) probablity to repeat output, in the end of the recursion, the probability that each elements saved in output value is 1/(recursion deep +1),otherwise, the probablity developing with the recursion deep developing.

from random import randomclass Solution(object):    def __init__(self, head):        """        @param head The linked list's head.        Note that the head is guaranteed to be not null, so it contains at least one node.        :type head: ListNode        """        self.header = head    def getRandom(self):        """        Returns a random node's value.        :rtype: int        """        head = self.header        index = 1        while head:            if random() * index <= 1:                value = head.val            index += 1            head = head.next        return value

Product of Array Except Self

Core: Divide the multplication into two part( before self and after self)

class Solution(object):    def productExceptSelf(self, nums):        """        :type nums: List[int]        :rtype: List[int]        """        output = [1] * len(nums)        n = len(nums)        template = 1        for i in range(1, n):            template = template * nums[i - 1]            output[i] *= template        template = 1        for i in range(n - 2, -1, -1):            template = template * nums[i + 1]            output[i] *= template        return output

Delete Node in a Linked List

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def deleteNode(self, node):        """        :type node: ListNode        :rtype: void Do not return anything, modify node in-place instead.        """        node.val = node.next.val        node.next = node.next.next

Ransom Note

Core: Hash two string

class Solution(object):    def canConstruct(self, ransomNote, magazine):        """        :type ransomNote: str        :type magazine: str        :rtype: bool        """        magazine_dir = {}        for each in list(magazine):            if magazine_dir.get(each) is not None:                magazine_dir[each] += 1            else:                magazine_dir[each] = 1        for each in list(ransomNote):            if magazine_dir.get(each) is not None:                magazine_dir[each] -= 1                if magazine_dir[each] < 0:                    return False            else:                return False        return True

Intersection of two arrays

Core: data structure convertion

class Solution(object):    def intersection(self, nums1, nums2):        """        :type nums1: List[int]        :type nums2: List[int]        :rtype: List[int]        """        set1 = set(nums1)        set2 = set(nums2)        return list(set1 & set2)

Same True

Core: Use Stack to save the node order

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def isSameTree(self, p, q):        """        :type p: TreeNode        :type q: TreeNode        :rtype: bool        """        if not p and not q: return True        if not p or not q: return False        stack_p = [p]        stack_q = [q]        while stack_p and stack_q:            node_p = stack_p.pop()            node_q = stack_q.pop()            if node_p.val != node_q.val:                return False            if node_p.left and node_q.left:                stack_p.append(node_p.left)                stack_q.append(node_q.left)            elif not node_p.left and not node_q.left:                pass            else:                return False            if node_p.right and node_q.right:                stack_p.append(node_p.right)                stack_q.append(node_q.right)            elif not node_p.right and not node_q.right:                pass            else:                return False        return True

is Sub sequence

Core: Two Pointer, Serializing String Value

class Solution(object):    def isSubsequence(self, s, t):        """        :type s: str        :type t: str        :rtype: bool        """        list_s = list(s)        list_t = list(t)        list_s.sort()        list_t.sort()        i = 0        j = 0        while i < len(list_s):            if j >= len(list_t):                return False            if list_s[i] == list_t[j]:                i += 1            j += 1        return True

Top K Frequent Element

Core:  Map the frequent and sort the map

class Solution(object):    def topKFrequent(self, nums, k):        """        :type nums: List[int]        :type k: int        :rtype: List[int]        """        dir_nums = {}        for each in nums:            if each in dir_nums:                dir_nums[each] += 1            else:                dir_nums[each] = 1        return sorted(dir_nums, key=dir_nums.get, reverse=True)[:k]