Tuesday, August 25, 2015

Leetcode 186. Reverse Words in a String II

[locked]

# Time: O(n)
# Space:O(1)
#
# Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
# 
# The input string does not contain leading or trailing spaces and the words are always separated by a single space.
# 
# For example,
# Given s = "the sky is blue",
# return "blue is sky the".
# 
# Could you do it in-place without allocating extra space?
#

class Solution:
    # @param s, a list of 1 length strings, e.g., s = ['h','e','l','l','o']
    # @return nothing
    def reverseWords(self, s):
        self.reverse(s, 0, len(s))
        
        i = 0
        for j in xrange(len(s) + 1):
            if j == len(s) or s[j] == ' ':
                self.reverse(s, i, j)
                i = j + 1
    
    def reverse(self, s, begin, end):
        for i in xrange((end - begin) / 2):
            s[begin + i], s[end - 1 - i] = s[end - 1 - i], s[begin + i]

Leetcode 179. Largest Number

https://leetcode.com/problems/largest-number/

Note: we now only care about algorithm problems. So some problems are ignored.

Using built-in function will make it simple.

Solution:
# T:O(nlgn) S:O(1)
class Solution:
    # @param num, a list of integers
    # @return a string
    def largestNumber(self, num):
        num = [str(x) for x in num]
        num.sort(cmp=lambda x, y: cmp(y + x, x + y))
        largest = ''.join(num)
        return largest.lstrip('0') or '0'
Run Time: 64 ms

Leetcode 174. Dungeon Game

https://leetcode.com/problems/dungeon-game/

Interesting problem with classic DP solution. The better thought is start from end, and count each grid the min hp the hero needs to get through. The solution is using rolling DP with very elegant coding. Very impressive.

Solution:
# T:O(m*n) S:O(m+n)
class Solution:
    # @param dungeon, a list of lists of integers
    # @return a integer
    def calculateMinimumHP(self, dungeon):
        DP = [float("inf") for _ in dungeon[0]]
        DP[-1] = 1
        
        for i in reversed(xrange(len(dungeon))):
            DP[-1] = max(DP[-1] - dungeon[i][-1], 1)
            for j in reversed(xrange(len(dungeon[i]) - 1)):
                min_HP_on_exit = min(DP[j], DP[j + 1])
                DP[j] = max(min_HP_on_exit - dungeon[i][j], 1)
                
        return DP[0]
Run Time: 52 ms

Leetcode 173. Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/

The iterator consists of a tree and a stack. For BST, the smallest number is the most left node.

Solution:
# T:O(1) S:O(h)
class BSTIterator:
    # @param root, a binary search tree's root node
    def __init__(self, root):
        self.stack = []
        self.cur = root

    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        return self.stack or self.cur

    # @return an integer, the next smallest number
    def next(self):
        while self.cur:
            self.stack.append(self.cur)
            self.cur = self.cur.left
        
        self.cur = self.stack.pop()
        node = self.cur
        self.cur = self.cur.right
        
        return node.val
Run Time: 140 ms

Leetcode 172. Factorial Trailing Zeroes

https://leetcode.com/problems/factorial-trailing-zeroes/

We know that 2 x 5 =10 is the source of trailing zeroes. So do we need to count the numbers of 2 and 5 in the factorial? Actually no. Because when one 5 occurred, two 2 have occurred. Hence we only need to count the number of 5, for 2 must be more.

Solution:
# T:O(lgn) S:O(1)
class Solution:
    # @return an integer
    def trailingZeroes(self, n):
        result = 0
        while n > 0:
            result += n / 5
            n /= 5
        return result
Run Time: 52 ms

Leetcode 171. Excel Sheet Column Number

https://leetcode.com/problems/excel-sheet-column-number/

This is the reverse operation of problem 168.

Solution:
# T:O(n) S:O(1)
class Solution:
    # @param s, a string
    # @return an integer
    def titleToNumber(self, s):
        result = 0
        for i in xrange(len(s)):
            result *= 26
            result += ord(s[i]) - ord('A') + 1
        return result
Run Time: 60 ms

Monday, August 24, 2015

Leetcode 170. Two Sum III - Data structure design

[locked]

# Time:  O(n)
# Space: O(n)
#
# Design and implement a TwoSum class. It should support the following operations: add and find.
# 
# add - Add the number to an internal data structure.
# find - Find if there exists any pair of numbers which sum is equal to the value.
# 
# For example,
# add(1); add(3); add(5);
# find(4) -> true
# find(7) -> false
#

class TwoSum:

    # initialize your data structure here
    def __init__(self):
        self.lookup = {}
        

    # @return nothing
    def add(self, number):
        if number in self.lookup:
            self.lookup[number] += 1
        else:
            self.lookup[number] = 1

    # @param value, an integer
    # @return a Boolean
    def find(self, value):
        for key in self.lookup:
            num = value - key
            if num in self.lookup and (num != key or self.lookup[key] > 1):
                return True
        return False