LeetCode | Learn for Master - Part 3
• ### LeetCode Recover Binary Search Tree (java)

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Java Solution

We can use a stack to do an in order traverse of the tree, as it can produce a sorted list of a binary search tree. In the process, we keep track of two pointers pre, cur:

If we encounter pre.val > cur.val the first time, we get the first error node p1 = pre,

• ### Leetcode Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Java Solution

• ### Leetcode Permutation Sequence

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):

1. “123”
2. “132”
3. “213”
4. “231”
5. “312”
6. “321”

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Java solution:

Refernce:

https://leetcode.com/problems/permutation-sequence/

http://fisherlei.blogspot.com/2013/04/leetcode-permutation-sequence-solution.html

• ### Leetcode Flatten Nested List Iterator (Java)

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

• ### LeetCode Shuffle an Array (Java)

Shuffle a set of numbers without duplicates.

Example:

Java Solution

• ### LeetCode Linked List Cycle (java)

Given a linked list, determine if it has a cycle in it.

Can you solve it without using extra space?

Java Solution

• ### LeetCode Ransom Note (Java)

Given  an  arbitrary  ransom  note  string  and  another  string  containing  letters from  all  the  magazines,  write  a  function  that  will  return  true  if  the  ransom   note  can  be  constructed  from  the  magazines ;  otherwise,  it  will  return  false.

Each  letter  in  the  magazine  string  can  only  be  used  once  in  your  ransom  note.

Note:
You may assume that both strings contain only lowercase letters.

Java Solution

• ### Leetcode Jump Game I & II (Java)

Jump Game I

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Analysis:
We maintain the max step can be reached so far.  If an index i is larger than the current max step that can be reached, it returns false.

Java Solution:

Jump Game II

Given an array of non-negative integers,

• ### Leetcode mini parser

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

• String is non-empty.
• String does not contain white spaces.
• String contains only digits 0-9, [, – ,, ].

Example 1:

Example 2:

Analysis

Define num to store the current number,

• ### Leetcode Expression Add Operators (Java)

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:

Analysis:

This problem can be solved using DFS algorithm. For example, given the input “123456“, suppose we encounter the last digit “6”, at which we already have the result of solve(“12345“). Then there are three cases:

solve(“123456”) = solve(“12345”) + 6

solve(“123456”) = solve(“12345”) – 6

solve(“123456”) = cal( solve(“12345”) ,