**Sample-based Learning Methods Week2 Notes**

## LeetCode 380 Insert Delete GetRandom O(1)

# Code

Solution of problem 380 is showed below. You can also find it here.

1 | auto ii = [](){ |

# Solution

The hard point of the problem is the **random** operation. The `insert`

and `remove`

operator can be easily done by **dictionary** structure, like `std:map`

or `std:unordered_map`

. To implement the **random** operator, **array-like** stucture is necessary. But it is hard to add or delete in `O(1)`

time. To combine them, we can save the data in a array-like structure and save their position in a dictionary structure. To remove a element, we can find the position from the dictionary structure and swap it with the last one so that we can remove it in both structure in `O(1)`

time.

# VAluable Method

To recall the problem, it is not that hard. But it took me long time on the random operator. It’s weird. When inserting or deleting elements in a heap, you add an element to the last position or swap the top element with the last element, and then follow the heap rules to adjust it. Here, it uses the same method.

## LeetCode 332 Reconstruct Itinerary

# Code

Solution of problem 332 is showed below. You can also find it here.

1 | class Solution { |

Another one is from the web.

1 | class Solution { |

# Solution

It is an example of Eulerian path finding. The first solution is just a regular DFS. It tries every possible way and save the current result. However, it obviously records more information it needs. The reason it needs to reset failed path is that it meets a **dead end** but not all edges are visited. But, there must exists an Eulerian path. Thus, if we meet a dead end, it tells us that we **just need to visit other points and there must be a way to go back to the start point of the dead end path**. As a result, we can record the dead end path and output them at last. It is the method of Hierholzer’s algorithm. The second solution is the Hierholzer’s algorithm.

# Valuable Method

It is not hard to write the first method and also not hard to think about the second method even we don’t know Hierholzer’s algorithm before. If you know the Hierholzer’s algorithm, you can realize it immediately and solve the problem. But if not, just dig more from the Eulerian path rather than submitting a passable solution and you will learn more from the problem.

## LeetCode 476 Number Complement

# Code

Solution of problem 476 is showed below. You can also find it here.

My solution

1 | class Solution { |

A solution on Leetcode:

1 | class Solution { |

# Solution

This is a simple and easy problem. Just flip each bit and it’s all solved. You can iterate each bit or handle them all together.

# Valueable Method

When seeing this kind of problem, I used to handle each bit and assemble them together. However, vectorize them (create a number and XOR with the original number) is a better way. Also, I ignore the feature that the all 1 bits sequence is the largest number at the sequence length.

Think more and code less all the time.

## Dynamic Programming

**Fundamentals of Reinforcement Learning Week4 Notes**

## Finite Markov Decision Processess Notes (Cont.)

**Fundamentals of Reinforcement Learning Week3 Notes**

## Finite Markov Decision Processes Notes

**Fundamentals of Reinforcement Learning Week2 Notes**

## The K-Armed Bandit Problem Notes

**Fundamentals of Reinforcement Learning Week1 Notes**

## Dialog Response Prediction Related Paper Read

Multi-turn Question-Answering/Chatbot problems are one of the hottest topics in NLP field recently. The blog sum up some tradition papers and several recent papers.

## LeetCode 984 String Without AAA or BBB

# Code

The solution of problem 984 is showed below. You can also find it here.

1 | class Solution { |

# Solution

The core method of the problem is to make sure that the number of each character is no less than half of another character and no exceed two consecutively.

# Valuable Method

I’ve tried to find pattern at first time, such as “aab”, “abb”, and etc. Finally, I find that if we want to prevent those “aaa” and “bbb” appear, we just need to keep the ratio of number of two characters. It’s easier to apply a simple rule rather than setting many patterns and it looks clean and beautiful.