LeetCode 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.

LeetCode Additive Number Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. For example: "112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

1 + 99 = 100, 99 + 100 = 199

LeetCode Increasing Subsequences Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 . Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

1. The length of the given array will not exceed 15.
2. The range of integer in the given array is [-100,100].
3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

LeetCode Minesweeper Let’s play the minesweeper game (Wikipedia, online game)! You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine. Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

1. If a mine (‘M’) is revealed, then the game is over – change it to ‘X’.
2. If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
3. If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
4. Return the board when no more squares will be revealed.

Input:
[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
Output:
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
Explanation:

Input:
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
Output:
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
Explanation:

1. The range of the input matrix’s height and width is [1,50].
2. The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
3. The input board won’t be a stage when game is over (some mines have been revealed).
4. For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

1. 如果周围（上下左右和四个对角）没有雷，则该位置写’B’，并且递归的在周围模拟点击
2. 如果周围有雷，则在该位置写上周围有雷的数目
3. 如果点中了雷，则写上’X’，游戏结束

LeetCode Beautiful Arrangement Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the i_th position (1 ≤ i ≤ N) in this array:

1. The number at the i_th position is divisible by i.
2. i is divisible by the number at the i_th position.

Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

1. N is a positive integer and will not exceed 15.

1. A[i]能整除i
2. i能整除A[i]

106. Construct Binary Tree from Inorder and Postorder Traversal

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

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

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

本题要根据树的中序和后序遍历结果，重构出树的结构。 有了之前LeetCode Construct Binary Tree from Preorder and Inorder Traversal根据前序和中序重构树的算法，这一题就是照猫画虎了。因为后序遍历是最后一个数为根节点，和前序遍历其实没本质差别。找准inorder和postorder下标的起止位置就可以开始写代码了：

class Solution {
private:
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int inL, int inR, int postL, int postR, unordered_map<int, int>& hash)
    {
        if (inL > inR || postL > postR)
            return NULL;
        TreeNode* root = new TreeNode(postorder[postR]);
        int idx = hash[root->val];
        root->right = dfs(inorder, postorder, inL + 1, inR, postR – (inR – idx), postR – 1, hash);
        root->left = dfs(inorder, postorder, inL, idx – 1, postL, postR – (inR – idx) – 1, hash);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        if (inorder.size() == 0)
            return NULL;
        unordered_map<int, int> hash;
        for (int i = 0; i < inorder.size(); ++i) {
            hash[inorder[i]] = i;
        }
        return dfs(inorder, postorder, 0, inorder.size() – 1, 0, postorder.size() – 1, hash);
    }
};

本代码提交AC，用时16MS。