ARST打卡第99周[99/521]

发表于 分类于 阅读次数：
lru实现 20岁，我们要明白的道理 memcpy与memmove的区别 前中后序非递归二叉树遍历

Algorithm-lru实现

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <unordered_map>
#include <list>
#include <algorithm>
#include <utility>

using namespace std;

class LRUCache {
   private:
    unordered_map<int, list<pair<int, int> >::iterator > cache_map;
    list<pair<int, int> > cache_list;
    int cap;
   public:
    LRUCache(int cap_v) : cap(cap_v) {}
    void put(int key, int val) {
        unordered_map<int, list<pair<int, int> >::iterator >::iterator it = cache_map.find(key);
        if (it != cache_map.end()) {
            // 利用del来赋值
            list<pair<int, int> >::iterator del = it->second;
            del->second = val;
            pair<int, int> tmp = *del;
            cache_list.erase(del);
            cache_list.push_front(tmp);

            cache_map[key] = cache_list.begin();

        } else {
            pair<int, int> tmp = make_pair(key, val);
            if (cache_map.size() >= cap) {
                int del_key = cache_list.back().first;
                cache_list.pop_back();
                unordered_map<int, list<pair<int, int> >::iterator>::iterator del_it = 
                    cache_map.find(del_key);
                cache_map.erase(del_it);
            }
            
            cache_list.push_front(tmp);
            cache_map[key] = cache_list.begin();
        }
    }
    
    int get(int key) {
        int ret_val = -1;
        unordered_map<int, list<pair<int, int> >::iterator >::iterator it = cache_map.find(key);
        // 找到则返回对应的val
        if (it != cache_map.end()) {
            ret_val = it->second->second;
            // 更新
            list<pair<int, int> >::iterator del = it->second;
            pair<int, int> tmp = *del;
            cache_list.erase(del);
            cache_list.push_front(tmp);
            cache_map[key] = cache_list.begin();
        }
        return ret_val;
    }
};

int main() {
    LRUCache cache( 2 /* 缓存容量 */ );
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 返回 1
    cache.put(3, 3); // 该操作会使得关键字 2 作废
    cout << cache.get(2) << endl; // 返回 -1 (未找到)
    cache.put(4, 4); // 该操作会使得关键字 1 作废
    cout << cache.get(1) << endl; // 返回 -1 (未找到)
    cout << cache.get(3) << endl; // 返回 3
    cout << cache.get(4) << endl; // 返回 4
    cout << "Hello World!" << endl;
}

Review

20岁，我们要明白的道理

相信自己求证的东西，相信自己一定能变得更好

不要相信任何人，包括自己，然后去保持疑惑，去求证疑惑，最终相信自己求证出来的东西，然后不断实践，让自己变得更好

Tips

memcpy与memmove的区别

Share-前中后序非递归二叉树遍历

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*
共同点：
- 用栈模拟递归
- 都是在为根时输出

 */
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <stack>

using namespace std;

typedef struct bt_node {
    int data;
    struct bt_node* lchild;
    struct bt_node* rchild;
} bt_node_t;

void pre_order_without_dfs(bt_node_t* root) {
    // 空树
    if (!root)
        return;

    bt_node_t* p = root;
    stack<bt_node_t*> s;
    while (!s.empty() || p) {
        if (p) {
            /* 根---后面的左，右变成根的时候也走这里 */
            cout << setw(4) << p->data;
            s.push(p);
            p = p->lchild;
        } else {
            /* 右 */
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    cout << endl;
}

void in_order_whitout_dfs(bt_node_t* root) {
    if (!root)
        return;

    bt_node_t* p = root;
    stack<bt_node_t*> s;
    while (!s.empty() || p) {
        // 左和根都放进去--先根后左，正好可以出栈先左后根
        if (p) {
            s.push(p);
            p = p->lchild;
        } else {
            p = s.top();
            s.pop();
            cout << setw(4) << p->data;
            p = p->rchild;
        }
    }
    cout << endl;
}

void last_order_whitout_dfs(bt_node_t* root) {
    if (!root)
        return;
    
    stack<bt_node_t*> s;
    /* 记录当前访问节点 和 上次访问节点 */
    bt_node_t* p_cur, * p_last_visit;

    p_cur = root;
    p_last_visit = NULL;

    /* 先把cur移动到最左边，并且把根都记录 */
    while (p_cur) {
        s.push(p_cur);
        p_cur = p_cur->lchild;
    }

    while (!s.empty()) {
        /* 每次都while到没有，所以这里的p_cur为空 */
        p_cur = s.top();
        s.pop();

        /* 左边访问完了，现在看右边没有 or 已经访问过的情况 */
        if (p_cur->rchild == NULL || p_cur->rchild == p_last_visit) {
            /* 现在可以输出根了 */
            cout << setw(4) << p_cur->data << endl;
            p_last_visit = p_cur;
        } else {
            /* 有右节点且未被访问 */
            s.push(p_cur);
            /* 进入右子树访问 */
            p_cur = p_cur->rchild;
            while (p_cur) {
                s.push(p_cur);
                p_cur = p_cur->lchild;
            }
        }
    }
    cout << endl;
}

int main() { 
    
    return 0; 
}