# 0797.All Paths From Source to Target

#### 797. All Paths From Source to Target

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], , , []]
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.
Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

• 时间复杂度 O(N)
• 空间复杂度 O(N)

• 执行用时: 12 ms
• 内存消耗: 2.4 MB

1.DFS
2.graph

#### 代码链接

all_paths_from_source_to_target

# 0706. Design HashMap

#### 706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // returns 1
hashMap.put(2, 1); // update the existing value
hashMap.get(2); // returns 1
hashMap.remove(2); // remove the mapping for 2

Note:

All keys and values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashMap library.

#### 思路

• 设计一个合适的散列函数；
• 定义装载因子阈值，并且设计动态扩容策略；
• 选择合适的散列冲突解决方法。

• 时间复杂度 O(N)
• 空间复杂度 O(N)

• 执行用时: 36 ms
• 内存消耗: 4.6 MB

1.哈希表

design_hashmap

# 0344. Reverse String

#### 344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]
Example 2:

Input: [“H”,”a”,”n”,”n”,”a”,”h”]
Output: [“h”,”a”,”n”,”n”,”a”,”H”]

• 时间复杂度 O(N)
• 空间复杂度 O(1)

• 执行用时: 28 ms
• 内存消耗: 5.3 MB

1.字符串
2.双指针

reverse_string

# 0232. Implement Queue using Stacks

#### 0232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.
Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false

Notes:

You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

#### 思路

• 时间复杂度 O(N)
• 空间复杂度 O(1)

• 时间复杂度 O(1) 最坏O(N)
• 空间复杂度 O(1)

• 执行用时: 0 ms
• 内存消耗: 2.1 MB

1.栈
2.队列

#### 代码链接

implement_queue_using_stacks

# 1037. Valid Boomerang

#### 1037. Valid Boomerang

A boomerang is a set of 3 points that are all distinct and not in a straight line.

Given a list of three points in the plane, return whether these points are a boomerang.

Example 1:

Input: [[1,1],[2,3],[3,2]]
Output: true

Example 2:

Input: [[1,1],[2,2],[3,3]]
Output: false

Note:
1.points.length == 3
2.points[i].length == 2

3.0 <= points[i][j] <= 100

#### 思路

`return K(AB) != K(BC)`