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;
}
|