fenghaolw

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 Bug free. Could done better if we add more error handling (instead of checking +-*/, we could have more invalid inputs)

Sort a linked list using insertion sort. Bug free. Probably could do better.

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

Given a singly linked list  L :  L 0 → L 1 →…→ L n -1 → L n , reorder it to:  L 0 → L n → L 1 → L n -1 → L 2 → L n -2 →… You must do this in-place without altering the nodes' values. For example, Given  {1,2,3,4} , reorder it to  {1,4,2,3} . Here I use a double queue to achieve O(n) complexity.

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. The intuitive approach is to use a hash map to store the mapping between the original nodes and the copied nodes. The following code requires O(2n) in time and O(n) in space. If we do not want to use extra memory, the following approach could be applied:  Copy the list nodes and insert the copied node right after the original node. For example, A->B->C->... becomes A->copyA->B->copyB->C->copyC->... If A has a non-null random pointer, we can simply set A->next->random = A->random->next . Split the list into two separate lists. O(3n) in time and O(1) in space.

There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once, otherwise return -1. Note: The solution is guaranteed to be unique. 1. If the sum of gas[i] is less than the sum of cost[i], for sure we should return -1. However, is it possible that we cannot travel around the circuit from any starting gas stations, even if the sum of gas[i] is greater than the sum of cost[i]? The answer is no since we have unlimited gas tank. 2. If we cannot travel from station i to station j, is it possible that the available starting point is located between i and j?

Given an array of integers, every element appears  twice  except for one. Find that single one. Could you implement it without using extra memory? Intuitive answer: using hash set Without extra space: use bit XOR. All numbers which occur twice will be cancelled out by themselves.

Clone an undirected graph. Each node in the graph contains a  label  and a list of its  neighbors . OJ's undirected graph serialization: Nodes are labeled uniquely. We use  #  as a separator for each node, and  ,  as a separator for node label and each neighbor of the node. As an example, consider the serialized graph  { 0 ,1,2# 1 ,2# 2 ,2} . The graph has a total of three nodes, and therefore contains three parts as separated by  # . First node is labeled as  0 . Connect node  0  to both nodes  1  and  2 . Second node is labeled as  1 . Connect node  1  to node  2 . Third node is labeled as  2 . Connect node  2  to node  2  (itself), thus forming a self-cycle. Visually, the graph looks like the following: 1 / \ / \ 0 --- 2 / \ \_/ BFS

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left justified and no extra space is inserted between words. For example, words: ["This", "is", "an", "example", "of", "text", "justification."] L: 16. Return the formatted lines as: [    "This    is    an",    "example  of text",    "justification.  " ] Note: Each word is guarante

There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy.  Children with a higher rating get more candies than their neighbors.  What is the minimum candies you must give?

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.