czxttkl

Code

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        sum = 0
        for i in xrange(32):
            sum += (n >> i) & 1
        
        return sum

Idea

Classic bit operation to count 1.

Another way to count 1 is to do n = n & (n-1) until n is equal to 0:

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        while n:
            n = n & (n-1)
            count += 1
        return count

Reference: https://discuss.leetcode.com/topic/20120/c-solution-n-n-1

Code

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

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        if (not p) or (not root):
            return None
        
        # if p has right child, its inorder successor is
        # the leftmost leaf of his right child
        if p.right:
            return self.leftmost(p.right)
        
        # record the most recent traversed node that has the left branch leading to p    
        prev_root = None
        while root != p:
            if p.val <= root.val:
                prev_root = root
                root = root.left
            else:
                root = root.right

        return prev_root

    def leftmost(self, node):
        while node.left:
            node = node.left
        return node

Idea

If p has right child, then its inorder successor is the leftmost leaf of his right child

Otherwise, p’s inorder successor is the most recent traversed node that has the left branch leading to p.

Actually, the code can be simplified as: 

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

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        succ = None
        while root:
            # think in this way: find the smallest element 
            # that is larger than p
            if p.val < root.val:
                succ = root
                root = root.left
            else:
                root = root.right
        return succ

Reference: https://discuss.leetcode.com/topic/25698/java-python-solution-o-h-time-and-o-1-space-iterative

Code

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0
        
        timeline = []
        for i in intervals:
            timeline.append(('start', i.start))
            timeline.append(('end', i.end))
            
        # sort timeline tuples by time first then by 'start' or 'end' tag
        # e.g. ('end', 13) < ('start', 13)
        timeline = sorted(timeline, key=lambda x: (x[1], x[0]))
        
        room = 0
        max_room = 0
        for k, v in timeline:
            if k == 'start':
                room += 1
            else:
                room -= 1
            if room > max_room:
                max_room = room
        
        return max_room
                

Idea

Create a timeline, a list of tuples. Each tuple marks a “start” or “end” tag with the time. Then sort the timeline and start traversing it. Whenever you see a start time, that means a new room is requested. Whenever you see an end time, that means a room is returned. 

You can also use heap to solve this problem: https://discuss.leetcode.com/topic/25904/python-heap-solution-with-comments

Code

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

from heapq import *

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        intervals = sorted(intervals, key=lambda x: x.start)
        heap = []
        for i in intervals:
            # if the new meeting happens after the earliest meeting ends,
            # replace the earliest ending meeting with the new meeting
            if heap and i.start >= heap[0]:
                heappop(heap)
                heappush(heap, i.end)
            else:
                heappush(heap, i.end)

        return len(heap)

Code

# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):

class Solution(object):
    def read(self, buf, n):
        """
        :type buf: Destination buffer (List[str])
        :type n: Maximum number of characters to read (int)
        :rtype: The number of characters read (int)
        """
        idx = 0

        while True:
            if idx == n:
                return idx 

            buf4 = [0]*4
            read4_ret = read4(buf4)
            for i in xrange(read4_ret):
                if idx < n:
                    buf[idx] = buf4[i]
                    idx += 1
                else:
                    return idx

            if read4_ret < 4:
                return idx

Idea

You read contents into buf. You should create a small buffer buf4 to save contents from read4. Then, based on how many characters you have read, determine when to return.

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Code

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ans = []
        self.removeHelper(s, 0, 0, '(', ')', ans)
        return ans

    def removeHelper(self, s, last_i, last_j, char1, char2, ans):
        """ Remove invalid parentheses in two rounds:
            1st round: detect ')' appears more times then '('
            2nd round: detect '(' appears more times then ')'
        """
        sum = 0
        for i in xrange(last_i, len(s)):
            if s[i] == char1: 
                sum += 1
            if s[i] == char2:
                sum -= 1
            if sum >= 0: 
                continue
            # anytime when sum < 0, we can start deleting a char2 between [last_j, i]
            for j in xrange(last_j, i+1):
                # deleted char2 should be first seen or not repeating (to avoid duplication)
                if s[j] == char2 and (j == last_j or s[j] != s[j-1]):
                    self.removeHelper(s[:j] + s[j+1:], i, j, char1, char2, ans)
            # invalid string has had valid result added to ans in recursion. so stop here.
            return
        
        s = s[::-1]
        if char1 == '(':
            self.removeHelper(s, 0, 0, ')', '(', ans)
        else:
            ans.append(s)
        

Idea

Remove invalid parentheses in two rounds:
1st round: detect ‘)’ appears more times then ‘(‘
2nd round: detect ‘(‘ appears more times then ‘)’

We use sum to record whether char2 appears more than char1. Whenever sum < 0, we can start deleting a char2 between [last_j, i]. A char2 to be deleted should be first seen or not repeating with previous chars. (check yourself by some examples.) last_j records the last deletion position. last_i records the last traversed position. 

In the second round, we can just reverse s and swap char1 and char2.

Reference: https://discuss.leetcode.com/topic/34875/easy-short-concise-and-fast-java-dfs-3-ms-solution

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.