LeetCode Q332: Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Solution:

LeetCode Q315: Count of Smaller Numbers After Self (hard)

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Solution:

I refer to this post for a solution using  BST. The basic idea is to use node in a tree to save information about how many nodes met already are smaller. 

I actually tried several solutions and for both of them I use node to save the number of nodes that appear after current node. However, saving information in this way force you have to update subtree of current when a node that is smaller than current node. This results in a TLE.

Instead, we should use node to save how many nodes are in the left of current node, which will not require an update of subtree.

Using mergesort, please refer to this post, and also geeksforgeeks's post. Code is given below:


Using binary indexed tree:
可以使用BIT来解这道题。 假设我们的输入数组是nums={5, 6, 3, 2}, 我们同样从数组的最后一项开始处理。第一个拿出来的是[2]。 我们希望，可以通过BIT的add操作加一个数字1到所有在[2]左边且比[2]大的数中去。可是我们如何才能知道哪些数是比[2]大的呢？ 这个就需要我们对原数组先进行一次排序， 排序后我们得到sorted_nums={2, 3, 5, 6}, 而我们的目的是得到原数组元素在排序后数组的位置places={2, 3, 1, 0}。到此位置，sorted_nums的任务就结束了，我们在程序中就用不到它了。继续我们的操作，此时我们取出来的是[2]， 然后我们找到它在places中对应位置的数[0]。 我们对[0]调用一次add操作(意义在于，我们希望对排序后比[2]大的数据都加1。也就是对排序后排在1, 2, 4位的数都加1， 这里没有3是因为BIT add 操作的原理，之后在算range_query的时候3就等于1+2的内容）。 然后我们就可以调用sum操作计算[2]这个位置的答案了。 之后拿出来的[3], [6]，都可以作同样的操作。 下一位拿出来的是[5], 此时，[5]的places值是2， 那么要向排序后排在[5]之后的数字加1，也就是向排在第2位之后的数字加1。这样的话，我们可能会要向[6]这个位置的加1, 可是这个时候我们不用担心结果出错，因为[6]这个位置的数我们已经处理结束了，即使可能向它加1，我们在处理5的sum操作的时候也只会看[5]排序后位置之前的数字。

LeetCode Q300: Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Solution 1: O(N^2)

Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that arr[i] is part of LIS and arr[i] is the last element in LIS, then L(i) can be recursively written as. L(i) = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1 To get LIS of a given array, we need to return max(L(i)) where 0 < i < n So the LIS problem has optimal substructure property as the main problem can be solved using solutions to subproblems. 每个L(i)存着到i截至且包含i的之前LIS的长度。 所以之后的对比如果nums[i] < nums[j], ipost.


Solution 2: O(NlogN)
Please refer to this post.

LeetCode Q282: Expression Add Operators (hard)

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples: 

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

Solution:
In my first try, I try to save all intermediate results of all possible cut, which equivalent to a BFS soluton. However, it result in a overflow of memory. Because BFS has to record all cases.

The problem can be solved using DFS, which is much more efficient in terms of memory usage. To deal with priority of operator "*", we need to keep track the operator used in last round. Also, we need to rule out the case where nums get multiple leading "0"s.

LeetCode Q254: Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Solution:
The trick here is to iterate factor from i to n/i, and insert result immediately.

LeetCode Q233: Number of Digit One (hard*)

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

// 我的解法的基本思想就是考虑把某一个位数上的数字设成1后，看其他位置有多少种选择。然后把每个数字位取1而有的选择都加起来就可以了。比如，假设输入为392， 那么把个位设置成1之后，十位和百位的选择就有00~39共40种，所以个位上可以有40个1。然后把十位设置成1之后，百位和个位有 00 ~39共40中选择，注意这儿并不是32或者33种，因为当10位上的数设成1之后，319也是小于392的，所以个位可以取所有的0~9。然后百位设成1后，十位和个位有00~99，共100种选择。

所以加起来就是： 40 + 40 + 100 = 180 种可能性，也就是180 个 1。

// A number is divided into three parts, front, curDigit and rear. For example, if input is 123456789, when we are considering the situation if we set the digit 5 to 1, then:

front = 1234, curDigit = 5, rear = 6789, rearSize = 1000

LeetCode Q220: Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Solution:
Keep tracking the past k elements by forming a BST for these k numbers. When new element coming, search BST to see if a target number exist. Remove the furthest element out of BST and insert current element to BST. 

Here, we need to use some nice features provided by STL. In STL, a BST is implemented as a "set". In set, there exist a functionality that can search the smallest number that is greater than search key. by using this feature, we can determine if there exist a number that is in the range of [key-t, key+t].:

LeetCode Q214: Shortest Palindrome (hard)

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Solution:

We can construct the following string and run KMP algorithm on it: (s) + (some symbol not present in s) + (reversed string)

After running KMP on that string as result we get a vector p with values of a prefix function for each character (for definition of a prefix function see KMP algorithm description). We are only interested in the last value because it shows us the largest suffix of the reversed string that matches the prefix of the original string. So basically all we left to do is to add the first k characters of the reversed string to the original string, where k is a difference between original string size and the prefix function for the last character of a constructed string.

LeetCode Q145: Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Round 2 solution:

1.1 Create an empty stack
2.1 Do following while root is not NULL
    a) Push root's right child and then root to stack.
    b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
    a) If the popped item has a right child and the right child 
       is at top of stack, then remove the right child from stack,
       push the root back and set root as root's right child.
    b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

LeetCode Q132: Palindrome Partitioning II (hard)

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.

Solution:

Using DP. No need to check whether a sub-string is a palindrome or not. At each character, we check its two sides to see if characters are the same. Need to take into account odd length palindrome and even length palindrome.

I'd like to help explain this great algorithm. :-O

This divide-and-conquer algorithm utilize the symmetry of palindromes, so there is no need to cache the result of whether s[i:j) is a palindrome.

Say that it started at s[i] = 'b', and s[i-1,i+1] is a palindrome "aba":

.......aba...
|<-x-><-x->| ^
|<---y--><---y-->|

And we know the least cuts for s[0,i-1) is X, then the least cuts for s[0,i+1] Y is not greater than X+1. Last, we need to find out all the palindromes in s[0,i+1] so as to minimize the number of cuts.

LeetCode Q76: Minimum Window Substring (hard*)

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 empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

This is a typical "substring" problem. People gave many beautiful solutions. 

Solution 1

1. Initialize a vector called remaining, which contains the needed matching numbers of each character in s.
2. If there are still characters needed to be contained (increment i in this case), decrease the matching number of that character and check if it is still non-negative. If it is, then it is the character in t, so decrease the total required number required.
3. If there is no more characters required (increment start in this case), record min andleft if a smaller length is found. Recover the number of this character in the remainingand if it is a character in t increase required.

Solution 2 (Similar to solution 1, but more concise.)
Template that can solve almost all substring problems
The code of solving Longest Substring with At Most Two Distinct Characters is below:
The code of solving Longest Substring Without Repeating Characters is below:

LeetCode Q72: Edit Distance (hard)

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

A classic DP problem.

Suppose DP[ i ][ j ] save the steps needed by converting word1[ 0 : i ] to word2[ 0 : j ]. Let's consider the very last step needed before word1[ 0 : i ] can be converted to word2[ 0 : j ].

If the step is DELETE, means word1[ 0 : i-1 ] = word2[ 0 : j ]. Thus DP[ i ][ j ] = DP[ i -1 ][ j ] + 1.

If the step is INSERT,  means word1[ 0 : i ] = word2[ 0 : j-1]. Thus DP[ i ][ j ] = DP[ i ][ j-1 ] + 1.

if the step is REPLACE, there could be two possibilities.

    First, if word1[ i ] = word2[ j ], then DP[ i ][ j ] = DP[ i-1 ][ j-1 ].

    Second, if word[ i ] != word2[ j ], then DP[ i ][ j ] = DP[ i-1 ][ j-1 ] + 1.

So, by taking minimum of these three possibilities, we get the value of DP[ i ][ j ].

To, initialize the boundary case, from above examples we know, to get DP[ i ][ j ], we basically, need to solve the values on it up left, left, and up. So, we only need to initialize the first row and the first column of the table DP. 

LeetCode Q69: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Easy question at the first glimpse, however, some corner cases can stop you for a long time. Apparently, should solve it using binary search. However, need to change a bit in a few places than normal binary search. For example, in following code, from line 4 -- line 9, we don't wait until l>=h to stop recursion, because, in that case, we may miss a few right solutions. Also, in line 17 and line 19, we don't increase low bound by one or decrease upper bound by one to ensure the middle position is still included in the next recursion. 

Round 2 solution:
Using Newton's method, for details, refer to this post:

LeetCode Q44: Wildcard Matching

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

I implement a DP solution, but the code didn't pass all test cases of leetcode due to running over the memory limit of leetcode.

My code is given as below:

This question can actually be solved using greedy algorithm which takes only O(s.length()+p.length()) time and constant space. For exact solution please refer to leetcode forum at:
https://leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution.

The method, try to match as many common characters of s and p, and when match is failed at current location, it roll back and to last '*' location, and increment pointer of s by one. It will roll back again and make the increment if the match still can not be found.

For each element in s
If *s==*p or *p == ? which means this is a match, then goes to next element s++ p++.
If p=='*', this is also a match, but one or many chars may be available, so let us save this *'s position and the matched s position.
If not match, then we check if there is a * previously showed up,
       if there is no *,  return false;
       if there is an *,  we set current p to the next element of *, and set current s to the next saved s position.

For quick reference, the code is given in below:

LeetCode Q33: Search in Rotated Sorted Array (hard)

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.

The question looks very easy at the first glance, since we could easily restore the sorted array first followed by a binary search. However, to restore the array may either need extra space or O(n) to rearrange the elements in the array.

I guess the reason leetcode put a "hard" label for this question is because it is requested to be solved in O(logn) time and in space, which comes  a solution using binary search:

To use a binary search on a rotated array, we should understand when to get rid off half of the elements and which half to remove. Let's take removal of the left half for example, there are three cases in total:

case 1 --- (target)7 in:     (left)2, 3, 4, 5, (mid)6, 7, 0, (right)1

case 2 --- (target)0 in:     (left)2, 3, 4, 5, (mid)6, 7, 0, (right)1

case 3 --- (target)4 in:     (left)6, 7, 0, 1, (mid)2, 3, 4, (right)5

For case 1:  nums[mid]>=nums[left] && target>nums[mid]

For case 2:  nums[mid]>=nums[left] && target

For case 3:  nums[mid]nums[mid] && target<=nums[right]

That's all cases we have to get rid of the elements in the left half of the array and move left pointer to mid+1. For all other cases, we just move right pointer to mid-1.

So comes the following code:

This code runs 4ms for all test cases.

For curiosity, I also tried a linear search solution, with surprise to see it can also finish search in 4ms. Simple method works in this case.

Solution: Second round
Second round solution 2:
For such question, rememeber to use nums[mid] to compare with either nums[left] or nums[right] first, this will separate cases really fast.

LeetCode Q28: Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

This question is suppose to be very easy, however, I confuse this question with LeetCode Q3: Longest substring without repeating characters. Thus made many mistakes in the first several tries.

Basically, the simplest solution is brute force one which is similar to code below:

Yet, the optimal solution is KMP algorithm which I don't think most people can understand and are expected to finish during interview, so skip.



Rount 2.
Use Boyer-Moore algorithm which is easier to understand than KMP and 3-5 times faster than KMP.

LeetCode Q10: Regular Expression Matching

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution:

This problem has a typical solution using Dynamic Programming. We define the state P[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. Then the state equations are:

1. f[i][j] = f[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. f[i][j] = f[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3. f[i][j] = f[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

Putting these together, we will have the following code.