czxttkl

https://leetcode.com/problems/reverse-integer/

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

 

Code

import re

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        m = re.match('(^[\+\-]*)(\d+)', str(x))
        
        sign = 1
        if m and m.group(1):
            sign = -(ord(m.group(1)) - 44)         # '-' ascii: 45  '+' ascii: 43
        
        if m and m.group(2):
            num = int(m.group(2)[::-1])
            num = num * sign
            if num > 2147483647 or num < -2147483648:
                return 0
            return num
            
        return 0

 

Idea

Simply using regex to find the two parts in the original string: sign and digits. I am a little cheating by calling `int()` directly: it automatically handles the situations when `m.group(2)[::-1]` starts with multiple zeros.

Spoilers for the problem are really important. This is an easy problem but with some corner cases you need to consider.

https://leetcode.com/problems/string-to-integer-atoi/

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

spoilers alert… click to show requirements for atoi.

Code

import re

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.strip()
        str = re.findall("^[\+\-0]*\d+", str)
        
        try:
            num = int(''.join(str))
            if num > 2147483647:
                return 2147483647
            if num < -2147483648:
                return -2147483648
            return num
        except:
            return 0

 

Idea

`atoi` is a C library function that converts a string into an integer. Here I am using regex to find substring starting with +, – or 0 followed by multiple digits. Then just use `int()` to convert the string into integer.

 

 

 

https://leetcode.com/problems/reverse-nodes-in-k-group/

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

 

Code

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

class Solution(object):
    def rotate(self, pt1, k):
        '''
        # return:
        # pt1: the new head of the current k elements
        # pt2: the head of the next k elements
        # i: the number of elements just being rotated  
        '''
        i = 2
        pt2 = pt1.next        
        
        pt1.next = None
        while i<=k and pt2:
            pt3 = pt2.next
            pt2.next = pt1
            pt1 = pt2
            pt2 = pt3
            i += 1
        
        return pt1, pt2, i
            
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if k == 1 or head is None or head.next is None:
            return head
        
        new_head = None
        tail = ListNode(999)  # tail is the last k elements's last element.
                              # Dummy at the beginning. 
        pt1 = head            

        while pt1:
            # pt1 will become the new head in the current k elements
            # pt2 will become the head of the next k elements
            pt1, pt2, i = self.rotate(pt1, k)
            
            # rotation reaches the end but the elements in the rotation are less than k
            if pt2 is None and i<=k:
                pt1, pt2, _ = self.rotate(pt1, k)
            
            if not new_head:
                new_head = pt1
            
            tail.next = pt1
            tail = head
            head = pt2
            
            # Set pt1 to be the new head in the next k elements
            pt1 = pt2
            
        return new_head

 

Idea

What I implemented is pretty straightforward in iterative way: find the first k elements and rotate them, then start to rotate the next k elements, so on so forth. When we reach the last k’ elements (k’ <= k), we need to check if we need to rotate them or not.

More trick way is to implement the solution in a recursive way (ref: https://leetcode.com/discuss/21301/short-but-recursive-java-code-with-comments):

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode curr = head;
    int count = 0;
    while (curr != null && count != k) { // find the k+1 node
        curr = curr.next;
        count++;
    }
    if (count == k) { // if k+1 node is found
        curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
        // head - head-pointer to direct part, 
        // curr - head-pointer to reversed part;
        while (count-- > 0) { // reverse current k-group: 
            ListNode tmp = head.next; // tmp - next head in direct part
            head.next = curr; // preappending "direct" head to the reversed list 
            curr = head; // move head of reversed part to a new node
            head = tmp; // move "direct" head to the next node in direct part
        }
        head = curr;
    }
    return head;
}

 

 

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

 

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import *

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        q = deque()
        q.append((root, 1))
        
        res = []
        while q:
            tup = q.popleft()
            n, l = tup[0], tup[1]
            if n is not None:
                if len(res) < l:
                    res.append([])
                if l % 2:
                    res[l-1].append(n.val)
                else:
                    res[l-1].insert(0, n.val)
                q.append((n.left, l+1))
                q.append((n.right, l+1))
        
        return res

 

Idea

Use BFS to traverse nodes. Note that there may be one performance issue in my code: at line 29, left appending new element to a list may cause the whole list being copied again. We can pre-allocate a list for nodes in the same depth when `len(res) < l` by using: `res.append([0]*(len(q)+1))`.

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

 

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 sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        self.nums = nums
        return self.helper(0, len(nums))
    
    def helper(self, start, end):
        if end <= start:
            return None
        
        mid = start + (end-start)/2
        root = TreeNode(self.nums[mid])
        root.left = self.helper(start, mid)        
        root.right = self.helper(mid+1, end)
        return root

 

Idea

The same idea to https://czxttkl.com/?p=1366 but easier because you have full view of the whole list.

https://leetcode.com/problems/plus-one/

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

 

Code

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        for i in xrange(len(digits)-1, -1, -1):
            if digits[i] == 9:
                digits[i] = 0
                if i == 0:
                    digits.insert(0, 1)
            else:
                digits[i] = digits[i] + 1
                break
            
        return digits

 

Idea

Straightforward.

https://leetcode.com/problems/balanced-binary-tree/

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Please check the clear definition of this problem: https://leetcode.com/discuss/59/different-definitions-balanced-result-different-judgments

 

Code 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 isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.helper(root) != -1
    
    def helper(self, root):
        if not root:
            return 0
        
        left_depth = self.helper(root.left)
        right_depth = self.helper(root.right)
        if left_depth >= 0 and right_depth >= 0 and abs(left_depth-right_depth) <=1:
            return max(left_depth, right_depth)+1
        else:
            return -1

Idea

Use dfs to get depth of every node. Whenever one node has inbalancing left and right subtrees, it returns -1 as an indicator. Note how different code 1 is with code 2. In code 1, every node is traversed exactly once therefore code takes O(N) time. In code 2, O(NlogN) time is needed because the nodes on the same level of the binary tree need calling O(N)  times `self.getHeight(root)` in total.

 

Code 2:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param {TreeNode} root
    # @return {boolean}
    def isBalanced(self, root):
        if not root:
            return True

        return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)

    def getHeight(self, root):
        if not root:
            return 0

        return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

 

Reference

https://leetcode.com/discuss/22898/the-bottom-up-o-n-solution-would-be-better

https://leetcode.com/problems/text-justification/

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly Lcharacters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

click to show corner cases.

Code

class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        res = []
        cur = 0                   # number of characters (without spaces) in current line 
        cur_l = []                # word list for current line
        i = 0
        
        while i < len(words):
            w =  words[i]
            if len(w) <= maxWidth - cur - len(cur_l):       # More words can be included in current line
                cur_l += [w]
                cur += len(w)
                i += 1
                if  i != len(words):                        # continue if the word is not the last word
                    continue
            
            if len(cur_l)==1:                               # This line only contains one word
                 res += [cur_l[0] + ' '*(maxWidth-cur)]
            else:
                if i == len(words):              # only left justified
                    line = ' '.join(cur_l)  
                    line += ' ' * (maxWidth - len(line))
                else:
                    line = cur_l[0]              # left-right justified
                    for ii, ww in enumerate(cur_l[1:], start=1):
                        if i != len(words):  
                            line += ' ' * ((maxWidth-cur)/(len(cur_l)-1)) 
                            if (maxWidth-cur) % (len(cur_l)-1) >= ii:
                                line += ' '
                            line += ww

                res += [line]
                
            if i != len(words):
                cur_l = []
                cur = 0
    
        return res

 

Idea

Lots of conditions to be considered. See comments for explanation. To me there seems not to be an intelligently challenging problem.

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

 

Code

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

# 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 sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if head is None:
            return None
        
        prev_slow_pt = None    
        slow_pt = head
        fast_pt = head
        while fast_pt.next and fast_pt.next.next:
            fast_pt = fast_pt.next.next
            prev_slow_pt = slow_pt
            slow_pt = slow_pt.next
        
        root = TreeNode(slow_pt.val)
        root.right = self.sortedListToBST(slow_pt.next)
        if prev_slow_pt:
            prev_slow_pt.next = None
            root.left = self.sortedListToBST(head)
        
        return root
        

 

Idea

To find the middle element in a linkedlist, it is a typical way to set two pointers, a slow pointer and a fast pointer. Let the fast one moves two elements forward every time while the slow one only moves one element forward each time. When the fast one reaches the end of the linkedlist, the slow pointer stops at the middle element of the linkedlist.

The slow pointer becomes the root of the BST. Then, all elements before the slow pointer become the left tree and all elements after the slow pointer become the right tree. The problem thus can be solved by smaller problems.

Note that I also maintain `prev_slow_pt` as a pointer pointing to the element right before the `slow_pt`. This is useful when you want to process only the elements from `head` to `prev_slow_pt` to form the left tree. (See line 33 – 35). If `prev_slow_pt` is None, it means `slow_pt` hasn’t moved at all and stayed at the `head` element. In this case, the left tree should be None.

In total, the time complexity is O(NlogN) where N is the number of elements in the linkedlist.

 

Idea II

However, repeatedly scanning the linkedlist using two pointers causes some waste in time. Another version that is more thrift in time would be using inorder traversal to construct the BST.

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

# 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 sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        size = 0
        self.head = head
        while head is not None:
            size += 1
            head = head.next
        return self.helper(0, size)
        
    def helper(self, start, end):
        '''
        start: inclusive
        end: exclusive
        '''
        if start >= end:
            return None
        mid = start + (end-start-1) / 2
        left = self.helper(start, mid)
        root = TreeNode(self.head.val)
        self.head = self.head.next
        right = self.helper(mid+1, end)
        root.left = left
        root.right = right
        return root
        

Since, every node is traversed exactly once, the time complexity is O(N). If you consider stacks used in recursion, the space complexity is O(logN)

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

 

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 buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if inorder:
            root = TreeNode(postorder.pop(-1))
            idx = inorder.index(root.val)
            root.right = self.buildTree(inorder[idx+1:], postorder)
            root.left = self.buildTree(inorder[:idx], postorder)
            return root

 

Idea

It is similar to the last post (https://czxttkl.com/?p=1358). Since now you are given postorder list, the root is always at the last element of `postorder`. Besides, the second to the last element is the root of the right tree. Therefore, you should first process `root.right` then `root.left`.