czxttkl

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import defaultdict, deque

class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []

        d = defaultdict(list)
        l = deque([(root,0)])
     
        while l:
            n, v = l.popleft()
            d[v].append(n.val)
            if n.left: 
                l.append((n.left, v-1))
            if n.right: 
                l.append((n.right, v+1))

        res = []
        for k in sorted(d.keys()):
            res.append(d[k])
        
        return res

Idea

Use BFS to traverse nodes. Since result must take O(N) space anyway, I don’t think there is much room to improve. 

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Code

import sys

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.min = sys.maxint
        self.stk = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if x <= self.min:
            self.stk.append(self.min)
            self.min = x
        self.stk.append(x)
        

    def pop(self):
        """
        :rtype: void
        """
        if self.stk:
            if self.stk[-1] == self.min:
                self.min = self.stk[-2]
                self.stk.pop()
            self.stk.pop()

    def top(self):
        """
        :rtype: int
        """
        if self.stk:
            return self.stk[-1]

    def getMin(self):
        """
        :rtype: int
        """
        if self.stk:
            return self.min
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

Idea

Whenever self.min changes, push the old self.min into stack. When popping an element equal to self.min, then the previous element in the stack is self.min before the element was added.

You can also add self.min along with the new element every time you execute push: https://discuss.leetcode.com/topic/11985/my-python-solution

This is the interview question from http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe?rq=1:

You are given a bag of numbers which are 0 ~ N-1 integers except k numbers. Return the k missing numbers. The solution should operate in O(N) time complexity and O(k) space complexity.

Although the highest voted post uses some theorem to solve the question, I would like to expand another solution which seems more intuitive and practical.

Code

class Solution(object):
    def find_k_missing(self, a, n):
        k = n - len(a)
        if k == 0:
            return a
        elif k == n:
            return range(n)

        a.extend([a[0]] * k)

        for i in xrange(n):
            while a[i] != a[a[i]]:
                t = a[i]
                a[i] = a[a[i]]
                a[t] = t

        return [idx for idx, v in enumerate(a) if idx != v]


if __name__ == "__main__":
    s = Solution()
    print s.find_k_missing([3,1,0,4], 5)

Idea

Suppose we have a bag a which contains the N-k numbers.

1. Extend the a with k additional numbers. The k additional numbers are set as the same value as any existing number, say, a[0]. After this step, a has N numbers.
2. We want to reorder a such that a[j] == j for j in the original N-k numbers.  To do so, traverse every number a[i] in a: swap a[i] and a[a[i]] until a[a[i]] == a[i]. This makes sure at least a[a[i]] == a[i] after the swap, which means a[a[i]] will be associated with the correct number.
3. Then, any position a[j] != j denotes the missing number.

Reference:

http://pastebin.com/9jZqnTzV

Code

from collections import defaultdict

class Solution(object):
    def multiply(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: List[List[int]]
        """
        C = [[0] * len(B[0]) for i in xrange(len(A))]
        
        # cache for A
        dA = defaultdict(lambda: defaultdict(int))
        for i in xrange(len(A)):
            for j in xrange(len(A[0])):
                if A[i][j]:
                    dA[i][j] = A[i][j]

        # cache for B
        dB = defaultdict(lambda: defaultdict(int))
        for i in xrange(len(B)):
            for j in xrange(len(B[0])):
                if B[i][j]:
                    dB[i][j] = B[i][j]

        # only calculate necessary elements
        for i in dA:
            for j, Aij in dA[i].iteritems():
                for k, Bjk in dB[j].iteritems():
                    C[i][k] += Aij * Bjk

        return C

Idea

If you calculate $latex C_{ik} = \sum\limits_j A_{ij} \cdot B_{jk}$, the total time complexity is O(N^3) (assume A, B and C have size O(N^2).)

To speed it up, you need to cache non-zero of A and B. And calculate $latex A_{ij} \cdot B_{jk}$ when necessary. 

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class 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
        tmp = node.next.next
        node.next.next = None
        node.next = tmp

Idea

Replace this node with this node’s next node.

         1
       /  \
      2    3
     / \    \
    4   5    7

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Code 

from collections import deque
# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None:
            return

        d = deque([(root, 0)])
        
        while d:
            if len(d) >= 2:
                # level is the same
                if d[0][1] == d[1][1]:
                    d[0][0].next = d[1][0]
                
            old_node, old_lvl = d.popleft()
            if old_node.left: d.append((old_node.left, old_lvl + 1))
            if old_node.right: d.append((old_node.right, old_lvl + 1))

Idea

Using BFS. Also look at the similar problem: https//nb4799.neu.edu/wordpress/?p=2044. Time complexity and space complexity are both O(N).

Code

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    
    def find_child(self, node, start_from_left_or_right):
        """ find the first occurrence of a child from the level of node.

        Return:
        1. child node
        2. its parent node
        3. "left" if it is the left child of its parent, otherwise "right"

        If child node is not found, return (None, None, None)
        """
        
        if node and start_from_left_or_right == 'right':
            if node.right:
                return node.right, node, 'right'
            else:
                node = node.next

        while node:
            if node.left:
                return node.left, node, 'left'
            elif node.right:
                return node.right, node, 'right'
            else:
                node = node.next

        return None, None, None


    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None: 
            return
        
        # pre is the first node in the previous layer
        pre = root
        
        while pre:
            # search the first child in the current layer
            first_child, first_child_parent, first_child_as_left_or_right = self.find_child(pre, 'left')
            pre = first_child

            while first_child is not None:
                # search the next child in the current layer
                if first_child_as_left_or_right == "left":
                    second_child, second_child_parent, second_child_as_left_or_right = \
                        self.find_child(first_child_parent, 'right')
                else:
                    second_child, second_child_parent, second_child_as_left_or_right = \
                        self.find_child(first_child_parent.next, 'left')
                
                if second_child is not None:
                    first_child.next = second_child
                    
                first_child, first_child_parent, first_child_as_left_or_right = \
                    second_child, second_child_parent, second_child_as_left_or_right                 



            
                

Idea

Modified from the O(1) space solution from: https//nb4799.neu.edu/wordpress/?p=2044

class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        if a == 0:
            return b
        elif b == 0:
            return a
        
        mask = 0xffffffff

        # in Python, every integer is associated with its two's complement and its sign.
        # However, doing bit operation "& mask" loses the track of sign. 
        # Therefore, after the while loop, a is the two's complement of the final result as a 32-bit unsigned integer. 
        while b != 0:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask

        # a is negative if the first bit is 1
        if (a >> 31) & 1:
            return ~(a ^ mask)
        else:
            return a

Adding two integers a and b (no matter positive or negative) can always be boiled down into 3 steps:

1. convert a and b into two’s complements.
2. add both two’s complements. The result is a new two’s complement
3. convert the result back to integer

Two things to note:
1. In Python, every integer is associated with its two’s complement and its sign. However, doing bit operation “& mask” loses the track of sign. For example, `-1 & 0xffffffff` becomes a huge positive number 4294967295. Therefore, after the while loop, a is the two’s complement of the final result as a **32-bit unsigned integer**.
2. The magic is that if there is a negative integer `n`, and its unsigned 32-bit two’s complement is `m`, then `m = ~(n ^ 0xffffffff)` and `n = ~(m ^ 0xffffffff)`. So using this magic, you can do the conversion in step 3.

Reference: https://discuss.leetcode.com/topic/65027/most-straightforward-python-solution

Code

from collections import deque

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 3:
            return True

        # when n = 1,2,3, you can always win
        d = deque([True] * 3)
        
        for i in xrange(4, n+1):
            newd = not (d[0] and d[1] and d[2])
            d.popleft()
            d.append(newd)

        return d[-1]

Idea

d contains three elements: when there are i-3, i-2 and i-1 remaining stones, can one have an optimal strategy to win? If they are all trues, no matter how many stones you take, your opponent will win.

Of course, this can be equivalent to: 

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n % 4 != 0

Code

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        d = [[0]*(len(word2)+1) for i in xrange(len(word1)+1)]
        
        for i in xrange(len(word1)+1):
            d[i][0] = i

        for j in xrange(len(word2)+1):
            d[0][j] = j

        for i in xrange(1, len(word1)+1):
            for j in xrange(1, len(word2)+1):
                if word1[i-1] == word2[j-1]:
                    d[i][j] = d[i-1][j-1]
                else:
                    d[i][j] = min(d[i-1][j]+1,   # delete word1[i]
                                  d[i][j-1]+1,   # delete word2[j]
                                  d[i-1][j-1]+1  # replace word1[i] by word2[j]
                                  )
        return d[-1][-1] 

Idea

We maintain a 2D array d, where d[i][j] means the edit distance between the substring word1[:i] and word2[:j]. 

Code

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        d = [i for i in xrange(len(word1)+1)]
      
        for j in xrange(1, len(word2)+1):
            pre = d[0]
            d[0] = j
            for i in xrange(1, len(word1)+1):      
                if word1[i-1] == word2[j-1]:
                    d[i], pre = pre, d[i]
                else:
                    d[i], pre = min(d[i-1]+1,  # delete word1[i]
                                    d[i]+1,    # delete word2[j]
                                    pre+1      # replace word1[i] by word2[j]
                                   ), d[i]
        return d[-1] 

Idea

Convert the 2D DP matrix into 1D. pre is the value of d[i-1][j-1] when d is 2D.

Reference

https://discuss.leetcode.com/topic/17639/20ms-detailed-explained-c-solutions-o-n-space