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 1:**

**Input:** 2

**Output:** 2

**Explanation:** There are two ways to climb to the top.

1. 1 step + 1 step

2. 2 steps

**Example 2:**

**Input:** 3

**Output:** 3

**Explanation:** There are three ways to climb to the top.

1. 1 step + 1 step + 1 step

2. 1 step + 2 steps

3. 2 steps + 1 step

Given a **non-empty** string *s* and a dictionary *wordDict* containing a list of **non-empty** words, add spaces in *s* to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

**Note:**

- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.

**Example 1:**

**Input:**

s = "catsanddog"

wordDict = ["cat", "cats", "and", "sand", "dog"]

**Output:**

[

"cats and dog",

"cat sand dog"

]

**Example 2:**

**Input:**

s = "pineapplepenapple"

wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

**Output:**

[

"pine apple pen apple",

"pineapple pen apple",

"pine applepen apple"

]

**Explanation:** Note that you are allowed to reuse a dictionary word.

**Example 3:**

**Input:**

s = "catsandog"

wordDict = ["cats", "dog", "sand", "and", "cat"]

**Output:**

[]

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

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
- After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

**Example:**

**Input:** [1,2,3,0,2]

**Output: **3

**Explanation:** transactions = [buy, sell, cooldown, buy, sell]

You are given a char array representing tasks CPU need to do. It contains capital letters A to Z where each letter represents a different task. Tasks could be done without the original order of the array. Each task is done in one unit of time. …

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

Suppose an array sorted in ascending order 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]`

).

Find the minimum element.

The array may contain duplicates.

**Example 1:**

**Input:** [1,3,5]

**Output:** 1

**Example 2:**

**Input:** [2,2,2,0,1]

**Output:** 0

**Note:**

- This is a follow up problem to Find Minimum in Rotated Sorted Array.
- Would allow duplicates affect the run-time complexity? How and why?

Given a non-negative integer `num`

, repeatedly add all its digits until the result has only one digit.

**Example:**

**Input:** 38

**Output:** 2

**Explanation: **The process is like: 3 + 8 = 11, 1 + 1 = 2.

Since 2 has only one digit, return it.

**Follow up:**

Could you do it without any loop/recursion in O(1) runtime?

Given a directed, acyclic graph of `N`

nodes. Find all possible paths from node `0`

to node `N-1`

, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length — 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

**Example:**

**Input:** [[1,2], [3], [3], []]

**Output:** [[0,1,3],[0,2,3]]

**Explanation:** The graph looks like this:

0--->1

| |

v v

2--->3

There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3

Given an array of numbers `nums`

, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

**Example:**

**Input:** [1,2,1,3,2,5]

**Output:** [3,5]

**Note**:

- The order of the result is not important. So in the above example,
`[5, 3]`

is also correct. - Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Given a binary tree, return the *zigzag level order* traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree `[3,9,20,null,null,15,7]`

,

`3`

/ \

9 20

/ \

15 7

return its zigzag level order traversal as:

`[`

[3],

[20,9],

[15,7]

]