czxttkl

  ["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.

'A' -> 1
'B' -> 2
...
'Z' -> 26

Code

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or s.startswith('0'):
            return 0
            
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        dp[1] = 1

        for i in xrange(1, len(s)):
            if 1 <= int(s[i]) <= 9:
                dp[i+1] += dp[i]
            if 10 <= int(s[i-1:i+1]) <= 26:
                dp[i+1] += dp[i-1]

        return dp[-1]

Idea

Use 1D DP. dp[0] means an empty string will have one way to decode, dp[1]means the way to decode a string of size 1. I then check one digit and two digit combination and save the results along the way. In the end, dp[n] will be the end result.

Reference: https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation

I was initially trying the following code. However this easily time limits when the input string is long:

class Solution(object):
    def __init__(self):
        self.res = 0

    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        self.helper(s)
        return self.res
    
    def helper(self, s):
        if s.startswith('0'):
            return
        
        if len(s) == 1:
            self.res += 1
        elif len(s) == 2:
            if int(s) <= 26:
                self.res+= 1
            self.helper(s[1:])
        else:
             self.helper(s[1:]) 
             if int(s[:2]) <= 26:
                 self.helper(s[2:]) 

Code

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if len(b) > len(a):
            a, b = b, a
        b = '0' * (len(a)-len(b)) + b

        carry = 0
        res = ['0'] * (len(a))

        for idx, (i,j) in enumerate(zip(a[::-1], b[::-1])):
            tmp = i + j + carry
            if tmp < 2:
                res[-idx-1] = str(tmp)   
            else:
                res[-idx-1] = str(tmp % 2)
                carry = 1

        # result cannot be longer than len(a)+1
        if carry:
            return str(carry) + ''.join(res)
        else:
            return ''.join(res)

Idea

From right to left, add each position. 

Code

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # maintain how many zeroes we have seen
        count0 = 0

        for idx, v in enumerate(nums):
            if v != 0:
                if count0 > 0:
                    nums[idx-count0] = v
                    nums[idx] = 0
            else:
                count0 += 1

Idea

An element should be moved count0 ahead, where count0 records how many zeroes we have seen.

If the order of non-zero elements is not required to maintain, we can have another algorithm:

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        start, end = 0, len(nums)-1
        while start < end:
            if nums[start] == 0:
                nums[start], nums[end] = nums[end], nums[start]
                end -= 1
            else:
                start += 1

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

Code

class Solution(object):

    def __init__(self, nums):
        """
        
        :type nums: List[int]
        :type numsSize: int
        """
        self.nums = nums
        

    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        count = 0
        for idx, v in enumerate(self.nums):
            if v == target:
                count += 1
                if random.randrange(count) == 0:
                    res = idx
        return res


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)

Idea

Reservoir Sampling. O(n) time and O(1) space. n is the length of nums.

Reference

https://discuss.leetcode.com/topic/58301/simple-reservoir-sampling-solution

If someone requires O(1) pick speed, one can construct a dictionary recording indices in __init__. See: https://discuss.leetcode.com/topic/58635/o-n-constructor-o-1-pick-two-ways

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Code

from collections import defaultdict

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        res = defaultdict(list)
        for s in strs:
            # you can also use tuple(sorted(s)) as dictionary key
            ss = ''.join(sorted(s))
            res[ss].append(s)
            
        return res.values()

Idea

Sort every string. Therefore, anagrams will always result in the same sorted string. Using the sorted string as key in dictionary so all anagrams will be grouped under the same key.

The time complexity is O(N MlogM), where $latex N$ is the length of strs and $latex M$ is the maximum length of single string in strs .  

Another idea is to hash every string such that a anagram group can be hashed into the same value. One way is to use prime numbers: https://discuss.leetcode.com/topic/12509/o-m-n-algorithm-using-hash-without-sort. However, this method may incur overflow.