Leetcode (Python): Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution:

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        nodeMap = {}
        return self.cloneNode(node, nodeMap)
    
    def cloneNode(self, node, nodeMap):
        if node == None:
            return None
        if node.label in nodeMap:
            return nodeMap[node.label]
        newNode = UndirectedGraphNode(node.label)
        nodeMap[node.label] = newNode
        for neighbor in node.neighbors:
            newNode.neighbors.append(self.cloneNode(neighbor, nodeMap))
        return newNode

Leetcode (Python): N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Solution:

class Solution:
    # @return an integer
    def totalNQueens(self, n):
        board = []
        for i in range(0,n):
            temp = []
            for j in range(0,n):
                temp.append(False)
            board.append(temp)
        return self.countQueens(board,0)
        
    def countQueens(self, board, row):
        if row == len(board):
            return 1
        solutions = 0
        for i in range(0,len(board)):
            if self.canPutQueen(board,row,i):
                board[row][i] = True
                solutions += self.countQueens(board, row+1)
                board[row][i] = False
        return solutions
        
    def canPutQueen(self, board, row,column):
        for i in range(0,row):
            if board[i][column]:
                return False
            if column-(row-i)>=0 and board[i][column-(row-i)]:
                return False
            if column+(row-i)<len(board) and board[i][column+(row-i)]:
                return False
        return True

Leetcode (Python): Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Solution:

Python can handle infinitely precision for integers, hence we can just convert the numbers to integers multiply them and convert to string

class Solution:
    # @param num1, a string
    # @param num2, a string
    # @return a string
    def multiply(self, num1, num2):
        return str(int(num1)*int(num2))

Leetcode (Python): Construct Binary Tree from Preorder and Inorder Traversal

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

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

Solution:

We implement the algorithm recursively, for instance given the tree to obtain


That corresponds to the lists:
preorder: A B D E C and inorder: D B E A C

We see that the first element of the preorder corresponds to the root value, A.
Note that by definition:

• All the elements in the inorder tree previous to this element (A) belong to the left tree and appear in the preorder tree just after the root.
• All the elements in the inorder tree after this element (A) belong to the right tree and appear in the preorder tree at the end.

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

class Solution:
    # @param preorder, a list of integers
    # @param inorder, a list of integers
    # @return a tree node
    def buildTree(self, preorder, inorder):
        return self.buildTreeRec(preorder, inorder, 0, 0, len(preorder))
        
    def buildTreeRec(self, preorder, inorder, indPre, indIn, element):
        if element==0:
            return None
        solution = TreeNode(preorder[indPre])
        numElementsLeftSubtree = 0;
        for i in range(indIn, indIn+element):
            if inorder[i] == preorder[indPre]:
                break
            numElementsLeftSubtree += 1
        solution.left = self.buildTreeRec(preorder, inorder, indPre+1, 
indIn, numElementsLeftSubtree)
        solution.right = self.buildTreeRec(preorder, inorder, indPre+numElementsLeftSubtree+1,
 indIn+numElementsLeftSubtree+1, element-1-numElementsLeftSubtree)
        return solution

Leetcode (Python): 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.

Solution:

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

class Solution:
    # @param root, a tree node
    # @return a boolean
    def isBalanced(self, root):
        return self.isBalancedInt(root)>=0
        
    def isBalancedInt(self, root):
        if root == None:
            return 0;
        left = self.isBalancedInt(root.left)
        right = self.isBalancedInt(root.right)
        if left<0 or right<0 or abs(left-right)>1:
            return -1
        return max(left,right)+1

Leetcode: 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.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return isBalancedInt(root)>=0;
    }
    
    private int isBalancedInt(TreeNode root)
    {
        if (root==null)
            return 0;
        if (root.left==null && root.right==null)
            return 1;
        int left = isBalancedInt(root.left);
        int right = isBalancedInt(root.right);
        if (left ==-1 || right==-1 || Math.abs(left-right)>1)
            return -1;
        return Math.max(left, right)+1;
        
    }
}

Leetcode (Python): Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution:

This problem's solution is straightforward, only having to be careful to check that you have not arrived to an end of a list. We reuse the nodes to create the solution in order to use constant space.

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

class Solution:
    # @return a ListNode
    def addTwoNumbers(self, l1, l2):
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        head = l1
        carryOn = (l1.val+l2.val) / 10;
        l1.val = (l1.val+l2.val) % 10;
        while l1.next != None and l2.next !=None:
            carryOn += l1.next.val
            carryOn += l2.next.val
            l1.next.val = carryOn % 10
            carryOn = carryOn // 10;
            l1 = l1.next;
            l2 = l2.next;
        if l1.next == None:
            l1.next = l2.next
        while l1.next != None:
            carryOn += l1.next.val
            l1.next.val = carryOn % 10
            carryOn = carryOn // 10;
            l1 = l1.next;
        if carryOn > 0:
            l1.next = ListNode(carryOn)
        return head