Sample-based Learning Methods Week2 Notes

Code

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

auto ii = [](){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  return 0;
} ();

class RandomizedSet {
public:
    /** Initialize your data structure here. */
    RandomizedSet() {

    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(mp.count(val)) return false;
        v.push_back(val);
        mp[val] = v.size() - 1;
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(!mp.count(val)) return false;
        mp[v.back()] = mp[val];
        v[mp[val]] = v.back();
        v.pop_back();
        mp.erase(val);
        return true;
    }

    /** Get a random element from the set. */
    int getRandom() {
        return v[rand() % v.size()];
    }
private:
    unordered_map<int, int> mp;
    vector<int> v;
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

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.

Code

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
    unordered_map<string, vector<pair<string, bool>>> ump;
    int tot = 0;
    
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> ret;
        tot = tickets.size();
        if(!tot) return ret;
        ret.push_back("JFK");
        for(auto &t: tickets) {
            if(!ump.count(t[0])) ump[t[0]] = vector<pair<string, bool>>();
            ump[t[0]].push_back({t[1], false});
        }
        for(auto it = ump.begin(); it != ump.end(); ++it) {
            sort(it->second.begin(), it->second.end());
        }
        dfs(ret, 0);
        return ret;
    }
    
    bool dfs(vector<string> &v, int n) {
        if(n == tot) return true;
        string s = v.back();
        if(!ump.count(s)) return false;
        for(auto it = ump[s].begin(); it != ump[s].end(); ++it) {
            if(!it->second) {
                it->second = true;
                v.push_back(it->first);
                if(dfs(v, n + 1)) return true;
                v.pop_back();
                it->second = false;
            }
        }
        return false;
    }
};

Another one is from the web.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        vector<string> res;
        stack<string> st{{"JFK"}};
        unordered_map<string, multiset<string>> m;
        for (auto t : tickets) {
            m[t.first].insert(t.second);
        }
        while (!st.empty()) {
            string t = st.top();
            if (m[t].empty()) {
                res.insert(res.begin(), t);
                st.pop();
            } else {
                st.push(*m[t].begin());
                m[t].erase(m[t].begin());
            }
        }
        return res;
    }
};

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.

Code

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

My solution

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

class Solution {
public:
    int findComplement(int num) {
        int ret = 0, cnt = 0;
        while(num) {
            ret |= ((num & 1) ^ 1) << cnt;
            num >>= 1;
            ++cnt;
        }
        return ret;
    }
};

A solution on Leetcode:

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int findComplement(int num) {
        int mask = 1;
        while(mask < num)
            mask = (mask << 1) + 1;
        return num ^ mask;        
    }
};

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.

Fundamentals of Reinforcement Learning Week4 Notes

Fundamentals of Reinforcement Learning Week3 Notes

Fundamentals of Reinforcement Learning Week2 Notes

Fundamentals of Reinforcement Learning Week1 Notes

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.

Code

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

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

class Solution {
public:
    string strWithout3a3b(int A, int B) {
        string s = "";
        int a = 0, b = 0;
        while( A || B ) {
            int ta = 0, tb = 0;
            while( ta < 2 && B <= 2 * A && A > 0 ) { s += "a"; ++ta; --A; }
            while( tb < 2 && A <= 2 * B && B > 0 ) { s += "b"; ++tb; --B; }
        }
        return s;
    }
};

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.