Tuesday, September 30, 2014

Index of My Own Notes

LeetCode questions:


Title

Java

Python

Reverse Words in a String Java Python
Evaluate Reverse Polish Notation Java Python
Max Points on a Line Java Coming soon
Sort List Java Python
Insertion Sort List Java Python
LRU Cache Java Python
Binary Tree Postorder Traversal Java Python
Binary Tree Preorder Traversal Java Python
Reorder List Java Python
Linked List Cycle II Java Python
Linked List Cycle Java Python
Word Break II Java Coming soon
Word Break I Java Python
Copy List with Random Pointer Java Python
Single Number II Java Python
Single Number I Java Python
Candy Java Python
Gas Station Java Python
Clone Graph Java Python
Clone Graph Java Python
Palindrome Partitioning II Java Python
Palindrome Partitioning Java Python
Surrounded Regions Java Python
Sum Root to Leaf Numbers Java Python
Longest Consecutive Sequence Java Python
Word Ladder II Java Coming soon
Word Ladder Java Coming soon
Valid Palindrome Java Python
Binary Tree Maximum Path Sum Java Python
Best Time to Buy and Sell Stock III Java Python
Best Time to Buy and Sell Stock II Java Python
Best Time to Buy and Sell Stock Java Python
Triangle Java Python
Pascal's Triangle II Java Python
Pascal's Triangle Java Python
Populating Next Right Pointers in Each Node II Java Python
Populating Next Right Pointers in Each Node I Java Python
Distinct subsequences Java Python
Flatten Binary Tree to Linked List Java Python
Path Sum II Java Python
Path Sum I Java Python
Minimum Depth of Binary Tree Java Python
Balanced Binary Tree Java Python
Convert Sorted List to Binary Search Tree Java Python
Convert Sorted Array to Binary Search Tree Java Python
Binary Tree Level Order Traversal II Java Python
Construct Binary Tree from Inorder and Postorder Traversal Java Coming soon
Construct Binary Tree from Preorder and Inorder Traversal Java Python
Maximum Depth of Binary Tree Java Python
Binary Tree Zigzag Level Order Traversal Java Python
Binary Tree Level Order Traversal Java Python
Symmetric Tree Coming soon Coming soon
Same Tree Java Python
Recover Binary Search Tree Java Python
Validate Binary Search Tree Java Python
Interleaving String Java Python
Unique Binary Search Trees II Java Python
Unique Binary Search Trees Java Python
Binary Tree Inorder Traversal Coming soon Coming soon
Restore IP Addresses Java Python
Reverse Linked List II Java Coming soon
Subsets II Java Python
Decode Ways Java Python
Gray Code Java Python
Merge Sorted Array Java Python
Scramble String Java Python
Partition List Java Python
Maximal Rectangle Java Python
Largest Rectangle in Histogram Java Coming soon
Remove Duplicates from Sorted List II Java Python
Remove Duplicates from Sorted List I Java Python
Search in Rotated Sorted Array II Java Python
Remove Duplicates from Sorted Array II Java Python
Word Search Java Python
Subsets Java Python
Combinations Java Coming soon
Minimum Window Substring Java Coming soon
Sort Colors Java Python
Search a 2D Matrix Java Python
Set Matrix Zeroes Java Python
Edit distance Java Coming soon
Simplify Path Java Python
Climbing Stairs Java Python
Sqrt(x) Java Python
Text Justification Java Python
Plus One Java Python
Valid Number Java Python
Add Binary Java Python
Merge Two Sorted Lists Java Python
Minimum Path Sum Java Python
Unique Paths II Java Python
Unique Paths Java Python
Rotate List Java Python
Permutation Sequence Java Python
Spiral Matrix II Java Python
Length of Last Word Java Coming soon
Insert Interval Java Coming soon
Merge Interval Java Python
Jump Game Java Python
Spiral Matrix Java Python
Maximum Subarray Java Python
N-Queens II Java Python
N-Queens Java Python
Pow(x, n) Java Python
Anagrams Java Coming soon
Rotate Image Java Coming soon
Permutations II Java Coming soon
Permutations Java Coming soon
Jump Game II Coming soon Coming soon
Wildcard Matching Java Coming soon
Multiply Strings Java Python
Trapping Rain Water Java Python
First Missing Positive Java Coming soon
Combination Sum II Java Python
Combination Sum Java Python
Count and Say Java Python
Sudoku Solver Java Python
Valid Sudoku Java Python
Search Insert Position Coming soon Coming soon
Search for a Range Java Python
Search in Rotated Sorted Array Java Python
Longest Valid Parentheses Java Python
Next Permutation Coming soon Coming soon
Substring with Concatenation of All Words Java Coming soon
Divide Two Integers Java Python
Implement strStr() Java Python
Remove Element Java Python
Remove Duplicates from Sorted Array Java Python
Reverse Nodes in k-Group Java Python
Swap Nodes in Pairs Java Python
Merge k Sorted Lists Java Python
Generate Parentheses Java Python
Valid Parentheses Java Python
Remove Nth Node From End of List Java Python
Letter Combinations of a Phone Number Java Python
4Sum Coming soon Coming soon
3Sum Closest Java Python
3Sum Java Coming soon
Longest Common Prefix Java Python
Roman to Integer Coming soon Coming soon
Integer to Roman Java Python
Container With Most Water Java Python
Regular Expression Matching Java Python
Palindrome Number Java Python
String to Integer (atoi) Java Python
Reverse Integer Java Python
Zigzag Conversion Java Python
Longest Palindromic Substring Java Coming soon
Add Two Numbers Java Python
Longest Substring Without Repeating Characters Java Python
Median of Two Sorted Arrays Java Coming soon
Two Sum Java Python

 Others:

Sunday, September 14, 2014

Leetcode (Python): Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
  • You may only use constant extra space.
For example,
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Solution:

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

class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        firstNodeLevel = root
        while firstNodeLevel != None:
            firstNodeNextLevel = None
            tempNextLevel = None
            pointer = firstNodeLevel
            while pointer != None:
                if pointer.left != None:
                    if firstNodeNextLevel == None:
                        firstNodeNextLevel = pointer.left
                    else:
                        tempNextLevel.next = pointer.left
                    tempNextLevel = pointer.left
                if pointer.right != None:
                    if firstNodeNextLevel == None:
                        firstNodeNextLevel = pointer.right
                    else:
                        tempNextLevel.next = pointer.right
                    tempNextLevel = pointer.right
                pointer = pointer.next
            firstNodeLevel = firstNodeNextLevel

Leetcode (Python): Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

Solution:

class Solution:
    # @param s, a string
    # @return a boolean
    def isPalindrome(self, s):
        start = 0;
        end = len(s)-1
        while start<end:
            while start<end and not s[start].isalnum():
                start +=1
            while start<end and not s[end].isalnum():
                end -=1
            if start<end and s[start].lower() != s[end].lower():
                return False
            start +=1
            end -= 1
        return True

Leetcode: Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

Solution:

public class Solution {
    public boolean isPalindrome(String s) {
        int start = 0;
        int end = s.length()-1;
        while(start<end)
        {
            while(start<end && ! Character.isLetterOrDigit(s.charAt(start)))
                start++;
            while(start<end && ! Character.isLetterOrDigit(s.charAt(end)))
                end--;
            if (start<end && Character.toLowerCase(s.charAt(start))!= Character.toLowerCase(s.charAt(end)))
                return false;
            start++;
            end--;
        }
        return true;
    }
}

Leetcode (Python): Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
    1
   / \
  2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

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 an integer
    
    def sumNumbers(self, root):
        self.sum = 0;
        self.sumNumbersRec(root,0)
        return self.sum
        
    def sumNumbersRec(self, root, partialSum):
        if root == None:
            return
        partialSum = partialSum *10 + root.val;
        if root.left == None and root.right == None:
            self.sum += partialSum
        else:
            self.sumNumbersRec(root.left, partialSum)
            self.sumNumbersRec(root.right, partialSum)

Leetcode: Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
    1
   / \
  2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int sum;
    public int sumNumbers(TreeNode root) {
        sum = 0;
        sumNumbers(root, 0);
        return sum;
    }
    public void sumNumbers(TreeNode root, int partialSum) 
    {
        if(root == null)
            return;
        partialSum = partialSum*10 + root.val;
        if (root.left==null && root.right == null)
            sum += partialSum;
        else
        {
            sumNumbers(root.left, partialSum);
            sumNumbers(root.right, partialSum);
        }
    }
}

Saturday, September 13, 2014

Leetcode (Python): Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree
   1
    \
     2
    /
   3
return [1,2,3].

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 list of integers
    def preorderTraversal(self, root):
        solution = []
        stack = []
        node = root
        while node != None or len(stack)>0:
            if node != None:
                solution.append(node.val)
                stack.append(node)
                node = node.left
            else:
                node = stack.pop().right
        return solution

Leetcode (Python): Insertion Sort List

Sort a linked list using insertion sort.

Solution:

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

class Solution:
# @param head, a ListNode
# @return a ListNode
    def insertionSortList(self, head):
        if not head:
            return head
        dummy = ListNode(0)                       
        dummy.next = head
        lastSorted = head
        while lastSorted.next:
            if lastSorted.next.val < lastSorted.val:          
                tmp = dummy                       
                while tmp.next.val < lastSorted.next.val: 
                    tmp = tmp.next
                nextToSort = lastSorted.next                 
                lastSorted.next = nextToSort.next
                nextToSort.next = tmp.next
                tmp.next = nextToSort
            else:
                lastSorted = lastSorted.next
        return dummy.next

Thursday, September 11, 2014

Leetcode (Python): Evaluate Reverse Polish Notation



Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +-*/. Each operand may be an integer or another expression.
Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:

class Solution:
    # @param tokens, a list of string
    # @return an integer
    def evalRPN(self, tokens):
        if tokens == None:
            return 0
        stack = []
        for token in tokens:
            if token =="+" or token =="-" or token =="*" or token =="/":
                operand2 = stack.pop()
                operand1 = stack.pop()
                if token == "+":
                    stack.append(operand1+operand2)
                elif token == "-":
                    stack.append(operand1-operand2)
                elif token == "*":
                    stack.append(operand1*operand2)
                else:
                    stack.append(int(float(operand1)/operand2))
            else:
                stack.append(int(token))
        return stack.pop()