You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example

Given an example n=3 , 1+1+1=2+1=1+2=3

return 3

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Example

There is one obstacle in the middle of a 3x3 grid as illustrated below.

1
2
3
4
5

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

• Only one letter can be changed at a time
• Each intermediate word must exist in the dictionary
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Example

1
2
3
4
5
6
7
8
9

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
]

Given a list of numbers, return all possible permutations.

Example

For nums = [1,2,3], the permutations are:

1
2
3
4
5
6
7
8

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Given a list of numbers with duplicate number in it. Find all unique permutations.

Example

For numbers [1,2,2] the unique permutations are:

1
2
3
4
5

[
  [1,2,2],
  [2,1,2],
  [2,2,1]
]

Given a list of numbers that may has duplicate numbers, return all possible subsets

Each element in a subset must be in non-descending order. The ordering between two subsets is free. The solution set must not contain duplicate subsets.

Example

If S = [1,2,2], a solution is:

1
2
3
4
5
6
7
8

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Example

If S = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

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.

Example

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

Notice

Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.

Example

Given: start = “hit”

end = “cog”

dict = [“hot”,“dot”,“dog”,“lot”,“log”]

As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list. The first node in the order can be any node in the graph with no nodes direct to it. Find any topological order for the given graph

Notice

You can assume that there is at least one topological order in the graph.