czxttkl

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

Code

class MovingAverage(object):

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.size = size
        self.vals = [0]* size
        self.cnt = 0
        self.sum = 0

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        self.cnt += 1
        idx = (self.cnt - 1) % self.size 

        # replace old value
        self.sum -= self.vals[idx]
        self.sum += val
        self.vals[idx] = val

        return float(self.sum) / self.cnt if self.cnt < self.size \
            else float(self.sum) / self.size

# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

Idea

A cyclic list

You can also use deque however when you calculate average it takes O(K) time where K is the window size.: https://discuss.leetcode.com/topic/44116/4-line-python-solution-using-deque

Code

class Solution(object):
    def findMissingRanges(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: List[str]
        """
        if nums is None:
            nums = []
        
        res = []
        nums = [lower-1] + nums + [upper+1]

        for i in xrange(1, len(nums)):
            prev, cur = nums[i-1], nums[i]
            if cur - prev == 2:
                res.append(str(cur-1))
            elif cur - prev > 2:
                res.append(str(prev+1) + '->' + str(cur-1))

        return res

Idea

To make the code consistent in different cases, I add lower-1 in front of nums and append upper+1 in the end of nums. Then if the current element is exactlye greater than the previous element by 2, then we miss a single number; else, if the current element is greater than the previous element more than 2, then we miss a range; if the current element is just 1 greater than the previous element, we do not do anything.

Also see a similar question: https//nb4799.neu.edu/wordpress/?p=944

dir
    subdir1
    subdir2
        file.ext

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

Code

class Solution(object):
    def lengthLongestPath(self, input):
        """
        :type input: str
        :rtype: int
        """
        if not input:
            return 0
        
        longest = 0
        prev_tab_cnt = 0
        # store tuples (name, level)
        stk = []

        s = input.split('\n')
        
        for ss in s:
            ss_tab_cnt = 0
            while ss.startswith('\t'):
                ss_tab_cnt += 1
                # \t only takes one character
                ss = ss[1:]
            
            while stk and stk[-1][1] >= ss_tab_cnt:
                stk.pop()
            stk.append((ss, ss_tab_cnt))
            if self.isfile(ss):
                longest = max(longest, len('/'.join(map(lambda x: x[0], stk))))

        return longest

    def isfile(self, s):
        if s.startswith('.') or len(s.split('.')) >= 2:
            return True
        else:
            return False

Idea

Maintain a stack which stores the names of file/directory as well as their levels. Whenever you see it is a file name, concatenate all names in the stack. Whenever you see the current level is less than the stack top’s level, that means the previous trace has ended and the current file/directory starts from some upper level. So you need to pop stack (line 24~25).

You can change stack to dictionary. Reference: https://discuss.leetcode.com/topic/55097/simple-python-solution

https://leetcode.com/problems/house-robber/

Code (Naive)

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        return max(nums[0] + self.helper(nums, 2), self.helper(nums, 1))
    
    def helper(self, nums, idx):
        if idx >= len(nums):
            return 0
        else:
            return max(nums[idx] + self.helper(nums, idx+2), self.helper(nums, idx+1))

Idea

This is my naive code. While this seems working, it actually takes O(2^N) time and O(N) space.

Code

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
            
        prev, cur = 0, 0
        for n in nums:
            new_cur = max(prev+n, cur)
            prev = cur
            cur = new_cur
        
        return cur

Idea

It uses two caches: prev, cur. For every n in nums, prev is the maximum stolen amount until the element which is two elements apart from n. cur is the maximum stolen amount until the element before n. Therefore, the maximum stolen amount until n, new_cur, is max(prev+n, cur). 

Reference: https://discuss.leetcode.com/topic/17199/python-solution-3-lines

https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/

   1
    \
     3
    / \
   2   4
        \
         5

   2
    \
     3
    / 
   2    
  / 
 1

# 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 longestConsecutive(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
            
        self.res = 0
        self.helper(root, root.left, 1)
        self.helper(root, root.right, 1)
        return self.res
        
    def helper(self, prev, cur, length):
        if cur is None:
            self.res = max(self.res, length)
            return
            
        if cur.val == prev.val + 1:
            self.helper(cur, cur.left, length+1)
            self.helper(cur, cur.right, length+1)
        else:
            self.res = max(self.res, length)
            self.helper(cur, cur.left, 1)
            self.helper(cur, cur.right, 1)
            

Of course you can implement one that does not require a global variable: https://discuss.leetcode.com/topic/29205/simple-recursive-dfs-without-global-variable

Code

from math import sqrt

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            return -1
        elif n == 0:
            return 0
        else:
            return int((((1 + sqrt(5))/2)**(n+1) - ((1 - sqrt(5))/2)**(n+1))/sqrt(5))

Idea

Essentially a fibonacci sequence.

Code

class Solution(object):
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num == 0:
            return num
        elif num % 9 != 0:
            return num % 9
        else:
            return 9

Idea

The result is called Digital root. Digital root will be equal to num % 9 except when num equals to 0 or num is itself 9’s multiples.