czxttkl

https://leetcode.com/problems/fraction-to-recurring-decimal/

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return “0.5”.
• Given numerator = 2, denominator = 1, return “2”.
• Given numerator = 2, denominator = 3, return “0.(6)”.

 

Code

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        if numerator == 0:
            return "0"
            
        res = ''
        if (numerator < 0) ^ (denominator < 0): # if either or numerator or denominator is negative
            res += "-"
            
        numerator, denominator = abs(numerator), abs(denominator)
            
        quot = numerator / denominator
        res += str(quot)    
        rem = numerator % denominator
        if rem == 0:
            return res
        
        res += "."
        rems = {}     # key is the last remainder and the value is the length of the result
                      # after filled with the quotient of the last remainder * 10 / denominator
        while True:
            rem_new = rem * 10
            quot = rem_new / denominator
            rem_new = rem_new % denominator
            
            if rem_new == 0:
                return res + str(quot) 
                
            if rems.get(rem):
                idx = rems.get(rem)-1
                return res[:idx] + "(" + res[idx:] + ")"
            
            res += str(quot)
            rems[rem] = len(res)
            rem = rem_new
           

 

Idea

We use the basic idea of division to calculate every digit of the result. Besides many corner cases to be considered, the most difficult part is to determine if there is any recurrent part in the result:

I use a dictionary, `rems`, where key is the last remainder and the value is the length of the result after filled with the quotient of the last remainder * 10 / denominator. For example, given numerator=1 and denominator=6, the first digit after the decimal point is 1, which is the quotient of 1*10 by the denominator 6. At this time, we store (1, 3) in `rems` because 1 is the last remainder and 3 is the length of “0.1”. After generating the first digit, we have 4 as the remainder.

The second digit after the decimal point is 6. At this time, we add (4, 4) to `rems` due to the same manner. When we compute the next digit (the third digit after the decimal point), `rem` has set to the last remainder 4. `rem` is checked to be already a key in `rems` (line 34), we conclude we will start to get recurrent quotient(s). Therefore, we start to add parenthesis and output the result.

 

https://leetcode.com/problems/scramble-string/

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

 

Code

class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2):
            return False
        elif not s1:
            return True
        
        n = len(s1)
        res = [[[False for _ in xrange(n)] for _ in xrange(n)] for _ in xrange(n+1)]  # the size of the first dim is n+1
                                                                                      # easy for indexing
        for j in xrange(n):
            for m in xrange(n):
                res[1][j][m] = (s1[j] == s2[m])
            
        for i in xrange(2, n+1):
            for j in xrange(n-i+1):
                for m in xrange(n-i+1):
                    for k in xrange(1,i):
                        res[i][j][m] |= (res[k][j][m] and res[i-k][j+k][m+k]) \
                                        or (res[k][j][m+i-k] and res[i-k][j+k][m])
                        
        return res[n][0][0]

 

Idea

See here: http://tianmaying.com/tutorial/LC87

One note is that we put for i in xrange(2, n+1)  at the outmost loop (line 20), where `i` is the length of the two substrings, `s1[j:j+i] and s2[m:m+i]`, under comparison. When we calculate `res[i][j][m]`, we always need some `res[k’][j’][m’]` where `k’ < i`. Therefore, we need to calculate `res` in ascending order of `i`, the first dimension of `res`.

https://leetcode.com/problems/insertion-sort-list/

Sort a linked list using insertion sort.

 

Code 

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

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = ListNode(0)
        cur = head
        while cur:
            isrt = new_head
            next = cur.next
            
            while isrt.next and isrt.next.val < cur.val:
                isrt = isrt.next
            
            cur.next = isrt.next
            isrt.next = cur
            cur = next
            
        return new_head
            

 

Idea

By definition, insertion sort is inserting each element to the current sorted array by comparing it to the elements in the current sorted array. It requires O(N^2) time asymptotically. In my code, `isrt` is used to locate the correct position to insert the new element. It is set to the head every time a new element needs to be inserted (Line 16).  

However, the code above can’t pass the leetcode OJ. One way to circumvent it is to set `isrt` more passively (set `isrt` only when very necessary) instead of setting it to head for every new element to be inserted.

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

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = ListNode(0)
        cur = head
        isrt = new_head
        
        while cur:
            next = cur.next
            
            if not isrt or not isrt.next or isrt.next.val>=cur.val:
                isrt = new_head
            
            while isrt.next and isrt.next.val < cur.val:
                isrt = isrt.next
            
            cur.next = isrt.next
            isrt.next = cur
            cur = next
            
            
        return new_head.next

 

https://leetcode.com/problems/zigzag-conversion/

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

 

Code

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if s is None or len(s) <= numRows or numRows==1:
            return s
        
        res = ""
        for i in xrange(numRows):
            if i == 0 or i == (numRows-1):
                res += s[i::(2*numRows-2)]
            else:
                s1 = s[i::(2*numRows-2)]
                s2 = s[(2*numRows-2-i)::(2*numRows-2)]
                for c1, c2 in zip(s1, s2):
                    res += c1 + c2
                if len(s1) > len(s2):  # s1 is at most longer than s2 by one character
                    res += s1[-1]
        return res
                    
                    

 

Idea

Every `2*numRows-2` characters in `s` will form one zigzag. You can find the rules when outputing the zigzag horizontally:

https://leetcode.com/problems/maximum-gap/

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

 

Code

import sys
import math

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) < 2:
            return 0
        
        # find max and min in nums
        max_num = -sys.maxint
        min_num = sys.maxint
        for i in nums:
            if i > max_num:
                max_num = i
            if i < min_num:
                min_num = i
        
        if max_num == min_num:
            return 0
        
        bucket_max = [None for _ in xrange(len(nums)+2)]  
        bucket_min = [None for _ in xrange(len(nums)+2)] 
        for i in nums:
            # max_num is actually assigned to n+2-th bucket  
            bucket = ((i-min_num) * (len(nums)+1)) / (max_num - min_num)  
            bucket_max[bucket] = max(bucket_max[bucket], i) if bucket_max[bucket] is not None else i
            bucket_min[bucket] = min(bucket_min[bucket], i) if bucket_min[bucket] is not None else i
        
        max_gap = 0
        prev_max = bucket_max[0]       # the first bucket must have one element
        for i in xrange(1, len(bucket_min)):
            if bucket_min[i] is not None:
                max_gap = max(bucket_min[i] - prev_max, max_gap)
                prev_max = bucket_max[i]
            
        return max_gap

 

Idea

This is a problem using the classic ideas of bucketing and pigeon hole principle. The logic is that, we create `n+1` buckets between `max_num` and `min_num`, where `max_num` and `min_num` of the array can be found in O(N) time. Since there are only `n` numbers in the array, there must be at least one bucket without any number landing in it. This important factor indicates that the max distance of two consecutive numbers in the sorted form must happen between the maximal number in one previous bucket and the minimal number in one latter bucket and the two buckets have at least one empty bucket between them. Any numbers falling into the same bucket will not have the difference exceeding the bucket range, which is `(max_num-min_num)/(n+1)`. 

https://leetcode.com/problems/simplify-path/

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Code

class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        paths = path.split("/")
        fs = []
        for p in paths:
            if p == "..":
                # when fs is empty, ".." has no effect
                if fs:
                    fs.pop()
            elif p == ".":
                pass
            elif p == "":
                pass
            else:
                fs.append(p)
        return "/" + "/".join(fs)
                
        

 

Idea

Since there could be “..” (the up level folder) and “.” (the current folder) in the path, it is natural to maintain a stack to record  folder hierarchy. The crux of this problem is to consider all possible corner cases, such as paths with two or more consecutive backslashes, or paths ending with backslashes, or paths already landing in “/” but with more “..” followed.  

https://leetcode.com/problems/gray-code/

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

 

Code

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n<0:
            return []
        
        res = [0]
        for i in xrange(n):
            for j in xrange(len(res)-1, -1, -1):
                res.append(res[j] + (1 << i))
        return res

 

Idea

Say we have already had the gray codes for n. Then, the gray codes for n+1 are constituted from:

1. ‘0’ followed by the gray codes for n
2. ‘1’ followed by the gray codes for n in the reversed order

 

https://leetcode.com/problems/unique-binary-search-trees-ii/

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

 

Code

# 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 copy(self, root, bias):
        if not root:
            return root
        
        new_root = TreeNode(root.val + bias)
        new_root.left = self.copy(root.left, bias)
        new_root.right = self.copy(root.right, bias)
        return new_root
        
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
            
        ans = [[] for _ in xrange(n+1)]
        ans[0] = [None]
        
        for i in xrange(1, n+1):
            for j in xrange(1, i+1):    # j is the root value
                for lt in ans[j-1]:
                    for rt in ans[i-j]:
                        root = TreeNode(j)
                        root.left = self.copy(lt, 0)
                        root.right = self.copy(rt, j)
                        ans[i] += [root]
        return ans[-1]

 

Idea

To extend the idea of Leetcode 96, when you are given `n`, you can put `1~n` as roots. When you put `i` (`1<=i<=n`) as the root, the left tree is depending on the result of `i-1` and the right tree is depending on the result of `n-i`. For this problem, the right tree is not solely copy of the trees of `n-i`. Every node in the trees of `n-i` should be added a bias of `i`. Therefore, we create a recursive function `copy(self, root, bias)` to copy trees with biases. 

https://leetcode.com/problems/unique-binary-search-trees/

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

 

Code

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if not n:
            return 0
            
        numOfTrees = [0] * (n+1)     # for easier indexing. Using numOfTrees[1:]
        numOfTrees[0] = 1
        
        for i in xrange(1, n+1):
            for j in xrange(1, i+1):
                numOfTrees[i] += numOfTrees[j-1] * numOfTrees[i-j] 
            
        return numOfTrees[n]

 

Idea

When you are given `n` (`n` is the size of sorted numbers to be placed in BST), there are multiple ways to construct unique BSTs depending on which element is placed as the root: you can put the first element as the root, then place the remaining `n-1` elements in the right tree. You can put the second element as the root, then place the first element as the left tree and the remaining `n-2` elements in the right tree. So on and so forth. 

Therefore, you can use an array, `numOfTrees` in my code, to store the number of unique BSTs. The final result, `numOfTrees[n]`, will be based on `numOfTrees[n’]` where `n’ < n`: You can put 1~n as root. When you put element `i` (`1<=i<=n`) as the root, its left tree can have `numOfTrees[i-1]` different unique ways of construction and its right tree can have `numOfTrees[n-i]` ways of construction. So the total number of unique trees when root equal to `i` is `numOfTrees[i-1] *numOfTrees[n-i]`.

A more mathematical way is to directly solve this problem using Catalan Number. Then you only need O(N) time and O(1) space. Please find introduction to Catalan Number below:

catalan 

https://leetcode.com/problems/interleaving-string/

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

 

Code

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) + len(s2) != len(s3):
            return False
        if not s1:
            return s3 == s2
        if not s2:
            return s3 == s1
        
        res = [[False] * (len(s1)+1) for _ in xrange(len(s2)+1)]
        
        for i in xrange(len(s1)+1):
            res[0][i] = (s1[:i] == s3[:i])
        for j in xrange(len(s2)+1):
            res[j][0] = (s2[:j] == s3[:j])
        
        for j in xrange(1, len(s2)+1):
            for i in xrange(1, len(s1)+1):
                res[j][i] = (res[j][i-1] and (s3[i+j-1] == s1[i-1])) or (res[j-1][i] and (s3[i+j-1]==s2[j-1]))
        
        return res[-1][-1]
        

 

Idea

Use DP. `res[j][i]` is the boolean indicator of whether `s3[:i+j]` is an interleaving string of `s1[:i]` and `s2[:j]`. It can be written recursively as `res[j][i] = (res[j][i-1] and (s3[i+j-1] == s1[i-1])) or (res[j-1][i] and (s3[i+j-1]==s2[j-1]))`. 

 

Reference

http://tianmaying.com/tutorial/LC97