Pony’s Stable

Leetcode battlefield:Some Python Codes

I collected a bunches of leetcode code solutions and now put them in one post. This post contains the following questions:

* BST Iterator
* Factorial Trailing Zeros
* Excel number
* Decimal
* Find Peak Element
* Min stack
* Majority elements
* Trailing zeros
* Tree Travel

Also, after realing leetcode online judge have numerous bug in python test case, I decided to turn to C++. So, here comes the solutions.

BST Iterator

Question:

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Basic logic:

The smallest value is will be on the left-most node, therefore the first thing to do is to dive to the deepest ad left-most of the tree. Next we can return the value of the middle node, then its left node. A list of nodes on path should be maintain to avoid return repeated value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class BSTIterator:
    # @param root, a binary search tree's root node
    def __init__(self, root):
        # ancestors of current node, 
        self.ancestors = []

        # current node, initialized by root
        self.current = None

        # current point to the  smallest value
        self.current = root
        self.dive()

    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        return self.current != None

    def hasLeft(self):
        return self.hasNext()

    def hasRight(self):
        return self.hasNext()

    # @return an integer, the next smallest number
    def next(self):
        # every time we dive first,
        # so the smallest value is the current node
        rval = self.current.val

        if not self.hasRight():
            # if no right nodes
            # the next smallest value will be current node's parent
            if len(self.ancestors) == 0:
                self.current = None
            else:
                self.current = self.ancestors.pop()
        else:
            # if there is right node,  it's value will smaller than parent's, 
            # so step into it, then dive to left-most
            self.current = self.current.right
            self.dive()

        return rval

    def dive(self):
        while self.hasLeft():
            self.ancestors.append( self.current )
            self.current = self.current.left

Excel column number

Qusetion

Given Excel column number, return the corresponding digit number

Basic logic

A conversion of number systems( thought not a typical one) . First we map characters to numbers, them multiply digit in the Nth location with 26^n, sum and get the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    # @param s, a string
    # @return an integer
    def __init__(self):
        self.map ='ABCDEFGHIJKLMNOPQRSTUVWXYZ'

    def titleToNumber(self, s):
        rval = 0
        for i in xrange(len(s)):
            # need to revese the string
            rval += self.char2Int(s[ len(s) - i -1])*(26**i)
        return rval

    def char2Int(self, char):
        return self.map.index(char)+1

Majority element

Question:

Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times.

Basic logic:

Use a counter(map) to calculate how many times each elements has occured and return if times > length/2.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    # @param num, a list of integers
    # @return an integer
    def majorityElement(self, num):
        map = {}
        length = float(len(num))
        for n in num:
            try:
                map[n] += 1
            except:
                map[n] = 1
            if map[n] >= length/2:
                return n

Trailing zeros.

Question:

Given an integer n, return the number of trailing zeroes in n!.

Basic logics:

This is more a math problem than a code problem. Notice that 1 x 2 x 3 ... x 5 ... x 10 ... with every 5( or n x 5 ) there must be a 2(ornx2). And the trailing zeros must be the result of (2x5)^n. Therefore, the problem becomes ‘How many 5 are there in it’s factors’. ( Need to rewrite this paragraph )

1
2
3
4
5
6
7
8
9

class Solution:
    # @return an integer
    def trailingZeroes(self, n):
        num = 0
        k = 1
        while 5**k <= n:
            num += int(n/(5**k))
            k += 1
        return num

Find peak elements

Questions

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

Basic logic

Easy problem, just iter over and compare each element with its neighbours. If the num[i] can equals num[i+], we first deduplicate, and then compare. Need some attentions on the conner case( length = 0,1 or the peak occurs on the head or tails)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        if len(num) == 1:
            return num[0]
        elif len(num) == 2:
            return min(num[0],num[1])
        else:
            # deduplicate
            while len(num) > 1 and num[0] == num[-1]:
                num.pop()
            for i in xrange(len(num)):
                try:
                    if num[i] == num[i+1]:
                        num.pop(i)
                except:
                    break
            return self.findMinNoRepeat(num)

    def findMinNoRepeat(self, num):
        if len(num) == 1:
            return num[0]
        elif len(num) == 2:
            return min(num[0],num[1])
        else:
            buf = []
            index = 0
            length = len(num)
            for i in xrange(3):
                buf.append(num[index])
                index += 1
            index -= 1

            while True:
                if self.isMax(buf):
                    return buf[1]
                else:
                    index += 1
                    index %= length
                    if num[index] != buf[-1]:
                        buf.pop(0)
                        buf.append(num[index])

    def isMax(self, buf):
        return buf[1]<buf[0] and buf[2]>buf[1]

Min Stack

question

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

* push(x) -- Push element x onto stack.
* pop() -- Removes the element on top of the stack.
* top() -- Get the top element.
* getMin() -- Retrieve the minimum element in the stack.
Basic logic

The key is to maintain double stack: one for normal push() and pop(), the other for the operation getMin(). When a new min value is pushed, we also push it to the min_stack, when it pops, we also pop it from min_stack. So the minimum value is always on the top of min_stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class MinStack:
    def __init__(self, node = None):
        self.stack = []
        self.minStack = []

    # @param x, an integer
    # @return an integer
    def push(self, x):
        self.stack.append(x)
        if self.minStack == [] or x <= self.minStack[-1]:
            self.minStack.append(x)

    # @return nothing
    def pop(self):
        val = self.stack.pop()
        if val == self.minStack[-1]:
            self.minStack.pop()

    # @return an integer
    def top(self):
        return self.stack[-1]

    # @return an integer
    def getMin(self):
        return self.minStack[-1]

Fraction to Recurring Decimal

Question
Basic logics.

Easy job, just a little bit tedious. By implementing a long divide, we can easily find the answer. Remember to store every ( quotient，remainder )pairs so that we can know when it starts repeat itself. The python test case is wrong. See this post. After this solution, I turned to C++, which should have better judge system.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

class Solution():
    def __init__(self):
        pass
    # @return a string
    def fractionToDecimal(self, numerator, denominator):
        # corner case
        if numerator == 0:
            return '0'

        # if no decimal number
        if numerator % denominator == 0:
            return str( numerator/denominator )
        else:
            # reduction of a fraction, not necessary
            fraction = 2
            while True:
                while fraction <= min( abs(numerator), abs(denominator) ):
                    if numerator % fraction == 0 and denominator % fraction == 0:
                        numerator /= fraction
                        denominator /= fraction
                        break
                    fraction += 1

                # if it's end, end it. else ,restart again
                if fraction >= min( abs(numerator), abs(denominator) ):
                    break
                fraction = 2

            # Decomposition quality factor to find if demimal repeated itself, not necessary.
            denom = abs(denominator)
            while denom % 2 == 0:
                    denom /= 2
            while denom % 5 == 0:
                    denom /=5
            repeated = denom != 1

            result_list = []
            # get the symbol of final result
            if numerator*denominator < 0:
                result_list += [('-','-')]
            numerator = abs(numerator)
            denominator = abs (denominator)

            # start long divide loop( core algo )
            add_dot = True
            index = 0
            while True:
                # long divide
                quotient = numerator / denominator
                remainder = numerator % denominator
                numerator = remainder

                # check if repreated, if not, ready for the next division
                if (remainder, quotient) in result_list:
                    repreat_start_locaation = result_list.index((remainder, quotient))
                    result_list.insert( repreat_start_locaation, ( '(', '(' ) )
                    result_list.append( ( ')' , ')' ) )
                    break

                # append this result of division
                result_list.append( (remainder, quotient) )
                # if remainder is 0, it's not a repreated number                    
                if remainder == 0:
                    break
                if add_dot:
                    result_list.append( ('.','.') )
                    add_dot = False
                numerator *= 10

                index += 1
                if index > 100:
                    break


            # construck result
            result_list.reverse()
            result_str = ''
            while len(result_list) > 0:
                remainder, quotient = result_list.pop()
                result_str += str(quotient)
            return result_str