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

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); ...