fenghaolw

Given a string containing just the characters  '('  and  ')' , find the length of the longest valid (well-formed) parentheses substring. For  "(()" , the longest valid parentheses substring is  "()" , which has length = 2. Another example is  ")()())" , where the longest valid parentheses substring is  "()()" , which has length = 4. Solution: use stack.

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given  [100, 4, 200, 1, 3, 2] , The longest consecutive elements sequence is  [1, 2, 3, 4] . Return its length:  4 . Your algorithm should run in O( n ) complexity. Solution: intuitively, use hash table to get O(n) complexity. However, the following code is stupid since it continues search duplicated items and the complexity becomes O(n^2). In order to avoid additional searching, the following code deletes items from the hash table once it has been checked. Since each element will only be accessed once, and the amortized cost of insert/delete/find operations for hash table is O(1), the overall time complexity is linear.

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. Solution: recursive version (does not pass large judge) DP version (passes large judge)

Given a binary tree, flatten it to a linked list in-place. Solution: Note that the requirement is to do it in-place. The key is to use pre-order traversal (root->left->right). Each time, we linked the left subtree and the right subtree. Recursive: Iterative:

Given an unsorted integer array, find the first missing positive integer. For example, Given  [1,2,0]  return  3 , and  [3,4,-1,1]  return  2 . Your algorithm should run in  O ( n ) time and uses constant space. Solution: hash-table solution (intuitive approach, O(n) in time and space...) The following code satisfies the constant space requirement. The key idea is: the first missed positive integer must in [1, n+1]. If we swap the integers and make sure and A[i] = i, we can easily check that which integer is missed.  Revised it at 2013-09-23:

Divide two integers without using multiplication, division and mod operator. Solution: having trouble to do this one by bitwise operations... Following code is kind of cheating... Following code correctly did the bitwise operations. T_T

Given a string  S  and a string  T , count the number of distinct subsequences of  T  in  S . A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,  "ACE"  is a subsequence of  "ABCDE" while  "AEC"  is not). Here is an example: S  =  "rabbbit" ,  T  =  "rabbit" Return  3 . Solution: recursion (does not pass large judge) DP (passes large judge)

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. Solution: Recursion. Bottom-up approach.

Given preorder and inorder traversal of a tree, construct the binary tree.  Solution: The first element in prevector is the root. The root divides the inorder vector into two parts.

Given inorder and postorder traversal of a tree, construct the binary tree. Solution: The last element in postorder vector is the root. The root divides the inorder vector into two parts.

Given a collection of candidate numbers ( C ) and a target number ( T ), find all unique combinations in   C   where the candidate numbers sums to   T . Each number in  C  may only be used  once  in the combination. Solution:  Use set to handle duplicates. Better idea is to use a previous number to mark whether duplicates exist. The following solution works for num = [1, 1] and target = 2; since each time we call dfs() and the target is still great than 0, the previous is set to be -1. But if the target is less or equal to 0, we will not reset previous to -1, and the duplicates can be detected.

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] ] Solution: BFS. Similar to  level order traversal . The following code passes LeetCode Large Online Judge.

Given a binary tree, return the  level order  traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree  {3,9,20,#,#,15,7} , 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] Solution: BFS. The following code passes LeetCode Large OJ. For  Binary Tree Level Order Traversal II , either reverse, or insert in the beginning.