czxttkl

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Code

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # no duplication in result. so sort candidates first.
        candidates = sorted(candidates)
    
        path, res = [], []
        self.dfs(0, candidates, path, res, target)
        return res
    
    def dfs(self, start_idx, candidates, path, res, target):
        # original target and all candidates are positive
        if target < 0:
            return
        elif target == 0:
            res.append(list(path))
            return
        
        for i in xrange(start_idx, len(candidates)):
            # remove duplication
            if i > start_idx and candidates[i] == candidates[i-1]:
                continue
            path.append(candidates[i])
            self.dfs(i+1, candidates, path, res, target-candidates[i])
            path.pop()
        

Idea

Essentially it is a DFS. In order to avoid duplicate combinations, we sort the candidates first (line 9) and also apply some mechanism at line 25. Then, we try adding `candidates[i]` to path, modifying target to `target-candidates[i]` and recurring on `dfs` method. 

Reference: https://discuss.leetcode.com/topic/19845/java-solution-using-dfs-easy-understand

Code

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class NestedIterator(object):

    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        # initialize a pair. 1st: the next element to explore, 
        # 2nd: the next index of that element to explore, if that element is a list-like NestedInteger
        self.stack = [[nestedList, 0]]
        
    def next(self):
        """
        :rtype: int
        """
        # hasNext() always makes sure the latest element on self.stack
        # is a list containing a non-list NestedInteger
        if self.hasNext():
            l, idx = self.stack.pop()
            return l.getInteger()

    def hasNext(self):
        """
        # hasNext() always makes sure the latest element on self.stack
        # is a list containing a non-list NestedInteger
        
        :rtype: bool
        """
        while self.stack:
            l, idx = self.stack[-1]
            if type(l) is NestedInteger and l.isInteger():
                return True
            else:
                if type(l) is NestedInteger and idx < len(l.getList()): 
                    self.stack[-1][1] += 1
                    self.stack.append([l.getList()[idx], 0])
                # the first added element in self.__init__ is a pure list    
                elif type(l) is list and idx < len(l):
                    self.stack[-1][1] += 1
                    self.stack.append([l[idx], 0])
                else:
                    # pop the element if the idx, the next position to explore, has already
                    # exceeded the length of the element
                    self.stack.pop()
        return False
        

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Idea

Use a stack to maintain the elements to iterate. The next element to be iterated will be on the top of the stack. The stack is initialized as [nestedList, 0] in self.__init__(), as we are going to explore the first element in nestedList in the future.

In self.next(), we always first call self.hasNext(). The goal of self.hasNext() is to put the next integer on the top of the stack and also a boolean indicating whether there indeed exists the next integer to iterate.

In self.hasNext(), we peek the top element in the stack (line 55). If it is already an integer, return True and we don’t need to arrange the stack further. If it is a list of integers, we need to start exploring that list and put the next integer on the stack. Before that, we need to increase the top element’s index by one (line 60 and 64). This means that the next time when we visit this list, we should start exploring from the updated index.

The advantage of this algorithm is that it does not need to load all integers of the whole list into the stack at one time. Its space complexity is O(K), where K is the depth of the deepest nested list.

Reference: https://discuss.leetcode.com/topic/41870/real-iterator-in-python-java-c

Code

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        left, right = 0, len(nums)-1
        while left <= right:
            if nums[left] == val:
                nums[left], nums[right] = nums[right], nums[left]
                right -= 1
            else:
                left += 1
            
        return right + 1

Idea

Everything on the right of right are elements equal to val.

Code (Naive)

import sys


class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if not divisor: return sys.maxint
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        dividend, divisor = abs(dividend), abs(divisor)

        res = 0
        while dividend - divisor >= 0:
            dividend -= divisor
            res += 1

        return res * sign

This is  a naive solution, where you count how many times dividend is to divisor by subtracting divisor from dividend until dividend < divisor. This solution causes Time Limit Error when dividend is large and divisor is small.

Code

import sys

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if not divisor: 
            return sys.maxint
        
        # In python there is no overflow issue.
        # This condition is here for a specific test case.
        if (dividend == -2**31 and divisor == -1):
            return 2**31-1
        
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        dividend, divisor = abs(dividend), abs(divisor)
    
        res = 0
        while dividend >= divisor:
            tmp_divisor = divisor
            tmp_multiple = 1
            while dividend >= (tmp_divisor << 1):
                tmp_divisor <<= 1
                tmp_multiple <<= 1
                
            dividend -= tmp_divisor
            res += tmp_multiple
        
        return res * sign

Idea

This is a quicker way to do the division. You approach to the quotient by doubling divisor until dividend < (tmp_divisor << 1). (line 22-27)

Reference: https://discuss.leetcode.com/topic/15568/detailed-explained-8ms-c-solution/2

Another idea is to use some mathematical properties to the quotient. If integer size is fixed at 32bit, then the algorithm takes constant time: https://discuss.leetcode.com/topic/17600/32-times-bit-shift-operation-in-c-with-o-1-solution

Code

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

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        headbak = head = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                head.next = l1
                l1 = l1.next
            else:
                head.next = l2
                l2 = l2.next
                
            head = head.next
        
        while l1:
            head.next = l1
            l1 = l1.next
            head = head.next
        
        while l2:
            head.next = l2
            l2 = l2.next
            head = head.next
        
        return headbak.next

Idea

When two lists’ heads are not None, splice the smaller node into the new list and move the list’s head to the next of the smaller pointer. Then, when only one list’s head is not None, concatenate all of its remaining nodes.

See a harder version: Merge k sorted list: https//nb4799.neu.edu/wordpress/?p=926

Code

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        
        prefix = ""
        for k in xrange(len(strs[0])):
            for i in xrange(1, len(strs)):
                if k < len(strs[i]) and strs[i][k] == strs[0][k]:
                    continue
                return prefix
            prefix += strs[0][k]
        
        return prefix

Idea

Suppose there are N strings and average K length for each string. Then this algorithm takes O(NK) time, which I believe is the fastest solution so far. Note that we start prefix from an empty string. In this way, we only need to test whether to add one character to prefix each time. 

Reference: https://discuss.leetcode.com/topic/20991/accepted-c-6-lines-4ms/6