fenghaolw

Given a set of  non-overlapping  intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals  [1,3],[6,9] , insert and merge  [2,5]  in as  [1,5],[6,9] . Given  [1,2],[3,5],[6,7],[8,10],[12,16] , insert and merge  [4,9]  in as  [1,2],[3,10],[12,16] . Example 2: This is because the new interval  [4,9]  overlaps with  [3,5],[6,7],[8,10] . Solution: first check the intervals, if not intersected with the new interval, push it to the result; otherwise update the new interval (merge them). Finally, find the correct insert position and insert the new interval. Linear complexity.  

Given  n  non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height =  [2,1,5,6,2,3] . The largest rectangle is shown in the shaded area, which has area =  10  unit. For example, Given height =  [2,1,5,6,2,3] , return  10 . Solution: For each bar, we want to find the leftmost and the rightmost higher bar. Exhaustive search takes O(n^2). Use stack to reduce the time complexity: For search the leftmost higher bar, search from left to right. Use stack to store the position of leftmost bar which has smaller height than current bar. Then we can calculate the width to the left. Similarly, we can search the rightmost higher bar. For example, [2, 1, 5, 6, 2, 3]. First of all, for the first element, the leftmost bar is itself. Push the position 0 to the stack. The stack is [0]. For the second element 1, since 1

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Solution: Assume that the total number of operations is d. Pick letters from both strings: x1 and x2. If x1 = x2, remove both and pick next letters. If they are different, compare three operations: a) insert a character, i.e., remove x2 from word2 since we will insert x2 to word1. Then pick letters from word1 and word2 again. b) delete a character, i.e., remove x1 from word1. c) replace a character, i.e., remove both x1 and x2. All these cases we need one extra operation. So the recursion is: s1 = delete the first character of word1 s2 = delete the first character of word2 d(word1, word2) = d(s1, s2), if the first characters are the same. d(word1, word2) = 1 + min(d(s1, word2), d(word1, s2), d(s1, s2))

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Solution:  Not hard. Use recursion or iterative. The following code passes LeetCode Online Large Judge. 2013-05-19: iterative solution. Inefficient due to additional vector operations. Need to be optimized.

Given a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Bonus points if you could solve it both recursively and iteratively. Solution: The following codes pass LeetCode Online Large Judge. Recursive solution is trivial. class Solution { public : bool isSymmetric(TreeNode * root) { // Start typing your C/C++ solution below // DO NOT write int main() function if (root == NULL ) return true ; else return helper(root -> left, root -> right); } bool helper(TreeNode * left, TreeNode * right) { if (left != NULL && right != NULL ) return left -> val == right -> val && helper(left -> left, right -> right) && helper(left -> right, right -> left); else return left == NULL && right == NULL ; } }; Iterative solution: first use breadth first sear

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-space characters only. For example,  Given s = "Hello World", return 5. Solution: Really simple. Following code passes LeetCode Online Large Judge. class Solution { public : int lengthOfLastWord( const char * s) { // Start typing your C/C++ solution below // DO NOT write int main() function int len = 0 , prev = 0 ; for ( int i = 0 ; s[i] != '\0' ; i ++ ) { if (s[i] != ' ' ) { len ++ ; prev = len; } else len = 0 ; } return len == 0 ? prev : len; } };

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ... 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth sequence. Note: The sequence of integers will be represented as a string. Solution: Two approaches to concatenate string with integer 1. use #include<sstream>, and then define a stringstream class. 2. use method push_back to append the char (result.push_back('0' + count);). The following code passes LeetCode Online Large Judge. class Solution { public : string countAndSay( int n) { // Start typing your C/C++ solution below // DO NOT write int main() function string result, tmp; if (n < 1 ) return result; int i = 0 ; while (i < n) { tmp = result; result = helper(tmp);

Given a binary tree, find the maximum path sum.   The path may start and end at any node in the tree. Solution: For root node, first check two subtrees and figure out the path with maximum sum in each subtree (and the path must contains the root node). More precisely, we can compare root->val, root->val + leftsubtree, root->val + rightsubtree. But this is not enough since the maximum path might contains two subtrees. We have to compute the value of root->val + leftsubtree + rightsubtree as well. The problem is, we cannot directly return this value since this path cannot go to upper nodes anymore. So we also use another global variable to store the maximum sum in each recursion, and update this variable once we find any path with larger sum. The following code passes the LeetCode Online Large Judge. Thanks for the useful comments.

Given a binary tree, return the inorder traversal of its nodes' values. Solution: Recursive solution is trivial. Iterative solution: Traverse from root to the leftmost until you hit the bottom level, use a stack to store the previous nodes. Then go back by pop the stack and go to the right. See  here  to get a perfect explanation. The following codes pass the LeetCode Online Large Judge. Recursive version: /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public : vector < int > inorderTraversal(TreeNode * root) { // Start typing your C/C++ solution below // DO NOT write int main() function vector < int > list; TraversalHelper(root, list); return list; } void TraversalHelper(TreeNode * root, vector < int > & list) {

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. Solution: Simply using recursion. Use a vector called prefix to generate the combination of numbers. The following code passes the LeetCode Online Large Judge.

Given an array of strings, return all groups of strings that are anagrams.   Note: All inputs will be in lower-case. Solution: First use an array to represent each string such that we can use linear time to compare whether two strings are the anagrams. Then use map to quickly store and search the array. Use another map to make sure all anagrams will be pushed back to the results. The following code passes the LeetCode Online Large Judge. class Solution { public : vector < string > anagrams(vector < string > & strs) { // Start typing your C/C++ solution below // DO NOT write int main() function vector < string > result; map < vector < int > , string > chkstr; map < vector < int > , int > ctr; for ( int i = 0 ; i < strs.size(); i ++ ) { vector < int > array( 26 ); for ( int j = 0 ; j < strs[i].size(); j ++ )

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: Recursion. Check the left and right subtrees; store the height during recursion in order to compare the subtrees. However, the following code calls the depth() so many times, and it is inefficient. The following version is better: every time we found that the subtree is not balanced, we could return -1 and break the recursions.

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Solution: Similar to Trapping Rain Water  problem. First check from left to right to find the maximum profit between the start to the i-th day. Then check from right to left to find the maximum profit between the i-th day to the end. Add two arrays and find the maximum profit. The following code passes LeetCode Online Large Judge. Note: my code uses 2n extra spaces, which can be further reduced by n. The rightProfit array is not useful, we only need to store two temporary values.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.  Solution: Given: 0 1 0 2 1 0 1 3 2 1 2 1 First traverse from left to right and get the maximum water height Get A: 0 1 1 2 2 2 2 3 3 3 3 3 Then traverse from right to left to get the maximum water height on the other side Get B: 3 3 3 3 3 3 3 3 2 2 2 1 Compare A and B to get the minimum, which is maximum allowable water height on each bar Min(A, B): 0 1 1 2 2 2 2 3 2 2 2 1 Extract the height of each bar to get the allowable water level Water: 0 0 1 0 1 2 1 0 0 1 0 0 The sum is 6. The following codes pass LeetCode Online Large Judge.

Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [      [2],     [3,4],    [6,5,7],   [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. Solution: Viterbi algorithm. Starting from the bottom level and eliminate the paths with higher weight. No extra space needed if we can change the original triangle. O(n) extra space needed if we cannot change the original triangle. The following codes pass LeetCode Online Large Judge. No extra space needed: class Solution { public : int minimumTotal(vector < vector < int > > & triangle) { // Start typing your C/C++ solution below // DO NOT write int main() function for ( int i = tria

3Sum Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. Solution: First sort the array S. For each element, figure out the two-sum problem. Use hash table or something like that to avoid duplicate triplets. Complexity is sorting O(nlogn) plus n two-sum problem nO(n) = O(n^2). The following code passes LeetCode online large judge.