czxttkl

         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

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Code

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stk = []
        for s in tokens:
            try:
                # test whether s is a number
                int(s)
                stk.append(s)
            except:
                a = stk.pop()
                b = stk.pop()
                stk.append(str(int(eval(str(float(b)) + s + a))))
                
        return int(stk[-1])

Idea

Use stack. Every time you see an operator, pop the last element in the stack.

Code

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if head is None:
            return None
        
        # store copied nodes indexed by label
        copynodes = dict()
        copyhead = RandomListNode(head.label)
        head_bak = head
        copyhead_bak = copyhead
        
        # copy 'next' for each node
        while head.next:
            copyhead.next = RandomListNode(head.next.label)
            copynodes[head.next.label] = copyhead.next
            copyhead = copyhead.next
            head = head.next

        copyhead = copyhead_bak
        head = head_bak

        # copy 'random' for each node
        while head:
            if head.random:
                copyhead.random = copynodes[head.random.label]
            head = head.next
            copyhead = copyhead.next

        return copyhead_bak

Idea

Two rounds copy. In the first round, make sure node is copied and connected one by one. During the first round, also record newly copied nodes in a dictionary copynodes. In the second round, copy field random. You need to use the dictionary to locate the new copied nodes in constant time.

Note: This algorithm only works when no two nodes have the same label because we use node.label as keys in the dictionary.

More elegant way to utilize defaultdict:

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

from collections import defaultdict
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        d = defaultdict(lambda: RandomListNode(0))
        d[None] = None
        tmp = head
        while tmp:
            d[tmp].label = tmp.label
            d[tmp].next = d[tmp.next]
            d[tmp].random = d[tmp.random]
            tmp = tmp.next
        return d[head]

Idea

d is a defaultdict. The key of d is original node and the value is the copied node.

Reference: https://discuss.leetcode.com/topic/5954/my-short-python-solution-with-o-n-complex-using-collections-defaultdict

Another very convoluted way to solve this problem. Only constant extra space will be used: https://discuss.leetcode.com/topic/7594/a-solution-with-constant-space-complexity-o-1-and-linear-time-complexity-o-n/2

Code

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

Idea

A XOR B XOR A= B

Code

import sys
from collections import defaultdict

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        mapping = defaultdict(int)
        for ch in t:
            mapping[ch] = mapping[ch] + 1
            
        d = sys.maxint
        valid = len(t)
        start = 0
        minstart, minend = None, None

        for end, ch in enumerate(s):
            if mapping[ch] > 0:
                valid -=1 
            mapping[ch] -= 1

            while valid == 0:
                if end - start + 1 < d:
                    minend, minstart = end, start
                    d = end - start + 1

                mapping[s[start]] += 1
                if mapping[s[start]] > 0:
                    valid += 1
                start += 1 
        
        if minstart is None:
            return ""
        else:
            return s[minstart:minend+1]
        
        

Idea

Create a dictionary mapping which stores how many times each character in t should appear. (line 11-13)

You have two pointers, start and end, which denote the border of the temporary window you are looking at. valid is a variable that when it reaches 0, we know the current window contains all characters in t. At first, `start` pointer is at index 0 and `end` pointer starts to move right.

When valid reaches 0,  you start to maintain the minimum string: you have variables d, minend and minstart and do the maintenance in line 26-28.

Then, you start to check whether a smaller window can also contains t. To do so, you move start pointer left. At the same time, you need to recover mapping dictionary.

Reference:

https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems

Code

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left < right:
            mid = left + (right - left) / 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        
        return right

Idea

Binary Search.