fenghaolw

A common approach to use a vector to represent a binary tree is serialized representation. All LeetCode OJ use this kind of representation: the serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below. Here's an example:    1   / \  2   3     /    4     \      5 The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}". For testing propose, I tried to write transform functions between serialized tree and binary tree. Essentially we could use level order traversal. The following class provides several methods to implement this.

Given a linked list, reverse the nodes of a linked list  k  at a time and return its modified list. If the number of nodes is not a multiple of  k  then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed. For example, Given this linked list:  1->2->3->4->5 For  k  = 2, you should return:  2->1->4->3->5 For  k  = 3, you should return:  3->2->1->4->5 This problem is an extension of  Swap nodes in pairs . Similar approach could be used. 

Given an array with  n  objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library's sort function for this problem. Follow up: A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's. Could you come up with an one-pass algorithm using only constant space? Counting sort is straightforward... One-pass solution: keep two pointers; move 0 to the head and 2 to the tail.

Given a string  s1 , we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of  s1  =  "great" : great / \ gr eat / \ / \ g r e at / \ a t To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node  "gr"  and swap its two children, it produces a scrambled string  "rgeat" . rgeat / \ rg eat / \ / \ r g e at / \ a t We say that  "rgeat"  is a scrambled string of  "great" . Similarly, if we continue to swap the children of nodes  "eat"  and  "at" , it produces a scrambled string  "rgtae" . rgtae / \ rg tae / \ / \ r g ta e / \ t a We say that  "rgtae"  is a scrambled string of  "great" . Given two strings

Given a 2D board containing  'X'  and  'O' , capture all regions surrounded by  'X' . A region is captured by flipping all  'O' s into  'X' s in that surrounded region . For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X DFS from the edge, mark all 'O's to 'M'. Then scan the matrix again, 'M' cannot be surrounded regions. So change all other 'O's to 'X'. BUG FREE!

You are given an  n  x  n  2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? It is trivial when extra spaces are allowed. Without extra space, we need to rotate the matrix from the outer layer to inner layer. Still not difficult but take some time to think about it.

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3  →  1,3,2 3,2,1  →  1,2,3 1,1,5  →  1,5,1

Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL . Initially, all next pointers are set to  NULL . Note: You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children). For example, Given the following perfect binary tree, 1 / \ 2 3 / \ / \ 4 5 6 7 After calling your function, the tree should look like: 1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL Following code uses classic BFS but push right child first; before pushing, check the back of the queue to see whether it is in the same level. If the answer is yes, set the next pointer. This solution alway

The set  [1,2,3,…, n ]  contains a total of  n ! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for  n  = 3): "123" "132" "213" "231" "312" "321" Given  n  and  k , return the  k th  permutation sequence. Note:  Given  n  will be between 1 and 9 inclusive. Here I use a vector to record the remaining digits. The current factorial function is not optimized... it should be fine since n is between 1 and 9.

Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given  "25525511135" , return  ["255.255.11.135", "255.255.111.35"] . (Order does not matter) Here I use similar approach (DFS) to  Palindrome Partitioning  problem. Note that  1. we should pre-check the length of the string, if it is larger than 12 or less than 4, it cannot be a valid IP address. Without this pre-checking, the following code will not pass the large judge. 2. "00" is not a valid part of IP address.

Given a string  s , partition  s  such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of  s . For example, given  s  =  "aab" , Return  1  since the palindrome partitioning  ["aa","b"]  could be produced using 1 cut. DP: mincut[i, j] = 0, if the substring between i and j is a palindrome. Otherwise, mincut[i, j] = min (1 + mincut[i, k] + mincut[k+1, j]), i <= k < j. We need a two-dimensional array storing whether the substring between i and j is a palindrome. We assume that chk[i] is the minimum cuts needed for a palindrome partitioning of the substring between i and s.end(); essentially, chk[i] = min(1 + chk[j + 1]), if the substring in [i, j] is a palindrome, i <= j < s.end(). The tricky part is that we don't need to obtain the entire isP matrix. One-pass scan is enough for this problem.

Given a string  s , partition  s  such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of  s . For example, given  s  =  "aab" , Return [ ["aa","b"], ["a","a","b"] ] DFS.

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. This is a common question for Big Integer class. For me, it takes around one hour to fix all edge cases... and the code is messy.

Today I spent more than one hour to figure out this problem. Following steps might be helpful if you have similar problem. 1. Use :reg to check whether there is "+ register in your vim. If not, you need to update your vim. This happens if you got your vim from apt-get and did not install useful dependencies. See  this  for more details. 2. Once you have "+ register, you should be able to use  +"y instead of y when you are copying. 3. You can map a short key for this: for example, I use vmap <c-c> "+y (Ctrl+C for copy). Add this to .vimrc file. 4. Also, use set go+=a and set mouse+= a such that you could select the text using mouse and then click Ctrl+C to copy. Here  set go+=a  is used for avoiding the line number.

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. DP: O(n^2) in both time and space. chk[i, j] = true if and only if s[i] == s[j] and chk[i-1, j+1] = true. Also note that the loop should NOT be i from 0 to n-1 and j from 0 to n-1. Redo in 2014-01-15. O(1) in space and O(n^2) in time.

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following is not: 1 / \ 2 2 \ \ 3 3 Note: Bonus points if you could solve it both recursively and iteratively. Recursive version: Iterative version:

Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of  O (log  n ). If the target is not found in the array, return  [-1, -1] . For example, Given  [5, 7, 7, 8, 8, 10]  and target value 8, return  [3, 4] .

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.,  0 1 2 4 5 6 7  might become  4 5 6 7 0 1 2 ). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. In each iteration of binary search, at least one side should be correctly ordered. If the target located in that side, we can eliminate another side. Otherwise we can eliminate the ordered side. Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array. The only difference is, we need to consider the scenario where A[m] == A[e]. The simplest approach is to reduce e by 1.

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S  =  "ADOBECODEBANC" T  =  "ABC" Minimum window is  "BANC" . Note: If there is no such window in S that covers all characters in T, return the emtpy string  "" . If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. Use two hashtables to store the required number of chars, and the number of chars we have already found. Check  here  for more details. Generally, using array will be faster than hashtable. However, hashtable is more general which can be applied to any char sets.

TopCoder SRM 144 DIV 2 1100: Given a tree-structure graph (not necessary to be binary tree), and each edge has a weight. The graph is represented by an array of tuple: parent, child, weight. The object is to get the minimum cost for visiting all nodes, starting from the root node. The key is that each edge needs  to be visited twice, if we want to start from the root and stop at the root. However, this problem does not require that we stop at the root, i.e., we can stop at any leaf node, wherever minimizes our total cost. Obviously, the problem is equivalent to find the maximum root-to-leaf path sum. Following code passes system test.

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Recursive, easy to write, but inefficient. Still pass the large judge. Iterative: BFS. Should be faster than recursion but actually not in leetcode... Also pass the large judge.

Given a collection of intervals, merge all overlapping intervals. For example, Given  [1,3],[2,6],[8,10],[15,18] , return  [1,6],[8,10],[15,18] . If we can sort the Intervals, it is easy. Is it possible to do this without sorting?

Implement int sqrt(int x). Compute and return the square root of x. First thought: use long long, inefficient. Also, some conditions are unnecessary. However, the following code still passes the large judge. Modified version: Thanks 六根清净  for providing a helpful binary search framework!

Given a binary tree, determine if it is a valid binary search tree (BST). recursive version: iterative version: