Pow(x, n) (Java)

LeetCode:

Implement pow(x, n).

Solution: Binary Search

N-Queens (Java)

Leetcode

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Slution: DFS

Insertion Sort List (Java)

LeetCode

Sort a linked list using insertion sort.

Add Binary (Java)

LeetCode

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Letter Combinations of a Phone Number (Java)

Leetcode

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.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Solution: DFS, Helper table

Construct Binary Tree from Inorder and Postorder Traversal (Java)

LeetCode

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Validate Binary Search Tree (Java)

LeetCode

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Construct Binary Tree from Preorder and Inorder Traversal (Java)

LeetCode

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution: Divide and Conquer

According to the rule of preorder traversal,  the first item in the preorder array must be the root. and the question also told us "You may assume that duplicates do not exist in the tree." so we can go through inorder array find the root's position, then  we got left tree and right tree. finally we can apply recursion to got the tree we want base on above logic.

Reverse Linked List II (Java)

LeetCode

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Next Permutation (Java)

LeetCode

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




Permutations II (Java)

LeetCode

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Best Time to Buy and Sell Stock III (Java)

LeetCode

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: Divide and Conquer, DP

O(n^2) solution is easy came out, we can use O(n) time to get max profit depend on the solution of Best Time to Buy and Sell Stock I. so we can just dived the whole prices array at every point , try to calculate current max profit from left and right and then add them together is what we want. However, there are many repeat calculation when calculate left max profit and right max profit. So we can apply DP to record max profits for each left side and right side. then add them together at each point use one for loop

Remove Duplicates from Sorted List II (Java)

LeetCode

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution: 

The logic is pretty straight, however, the corner cases need pay more attention.
check the comments in the code.