魔のkyo的BLOG
0%

发表于 更新于 分类于 Valine： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

C++ STL 里实现了两个二分搜索，lower_bound和upper_bound，支持在已经排好序的并且有随机迭代器的容器上进行二分搜索。（事实上map、set、multimap、multiset容器通过成员函数也提供了lower_bound和upper_bound，语意是相同的，实现方式不同）

lower_bound 是返回[b, e)区间上首个大于等于x的元素的迭代器

upper_bound 是返回[b, e)区间上首个大于x的元素的迭代器

下闭上开，和STL里其他地方都是一致的，lower_bound返回的迭代器 p 保证 [p, e) 都是大于等于x的，而upper_bound返回的迭代器q保证[b, q)都是小于等于x的。

STL里的这俩函数基本上不能用在自定义的容器上，因为它们要求容器类型通过typdef定义了各种特定类型，我下面实现了两个替代品，只要求迭代器可以随机访问（即可以加减任意数，随机迭代器可以任意移动，顺序迭代器只能加1减1，链表就只有顺序迭代器），元素有小于运算（我特意把所有的比较都改写成了小于）

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
// 返回[b,e) 区间上首个大于等于x的元素的迭代器
template<typename Iter, typename VT>
Iter my_lower_bound(Iter b, Iter e, const VT& x)
{
    if(!(*b<x)) return b;
    if(*(e-1)<x) return e;
    while(b<e-2){
        Iter mid=b+(e-b)/2;
        if(*mid<x)
            b=mid;
        else
            e=mid+1;
    }
    return e-1;
}

// 返回[b,e) 区间上首个大于x的元素的迭代器
template<typename Iter, typename VT>
Iter my_upper_bound(Iter b, Iter e, const VT& x)
{
    if(x<*b) return b;
    if(!(x<*(e-1))) return e;
    while(b<e-2){
        Iter mid=b+(e-b)/2;
        if(!(x<*mid))
            b=mid;
        else
            e=mid+1;
    }
    return e-1;
}

二分算法看上去简单，如果不注意是很容易出错的，我觉得主要要注意2点：

1）循环不变性，比如lower_bound，我们找[b,e) 区间上首个大于等于x，在进入循环前我们排除了元素不在[b,e)上的情况，那么在循环内修改b或e的时候就要保证，修改后，要找的元素仍然在[b,e)上，e是开区间的，不要不小心就把元素丢到外面去了。

2）循环能终结，比如我们让b=mid，会不会搜索范围并没有变小呢？一般有几种方式可以调整终结条件，一种就是改while条件，一种就是改mid的计算，mid在偶数大小区间是有两个数可以选择的，mid = b + (e-b)/2 或 mid = b + (e-b+1)/2

有时候序列是降序的怎么办？通过反向迭代器

有时候我们想在一个范围内找满足某个条件的最大值或最小值

1
2
3
4
5
6
7
8
9
10
11
12
// f满足存在一个k值得对于i<k有f(i)=False, 对于i>=k有f(i)=True
// 返回上述的k
template<typename I>
int lower_bound(I b, I e, function<bool(I)> f) {
    if(b >= e) return e;
    while(b < e - 1) {
        auto m = b + (e-1-b) / 2;
        if(!f(m)) b = m + 1;
        else e = m + 1;
    }
    return f(b) ? b : e;
}

相反的，我们可以用lower_bound来实现upper_bound

1
2
3
4
5
6
7
8
// f满足存在一个k值得对于i>=k有f(i)=False, 对于i<k有f(i)=True
// 返回上述的k
template<typename I>
int upper_bound(I b, I e, function<bool(I)> f) {
    return lower_bound(b, e, (function<bool(I)>)[&](I i){
        return !f(i);
    });
}

实际使用时写在模板里做了一些改进写成了下面的样子，把b、e的类型写成ll可以避免传参是一个是int一个是unsigned int或者一个ll的情况会编译报错，f的类型写成F而没有用function也是避免要写强制类型转换，使用时可以直接传lambda表达式。

1
2
3
4
template<typename F>
ll lb(ll b, ll e, F f) {if(b>=e) return e; while(b<e-1) {auto m=b+(e-1-b)/2; if(!f(m)) b=m+1; else e=m+1;} return f(b)?b:e;}
template<typename F>
ll ub(ll b, ll e, F f) {return lb(b, e, [&](ll i){return !f(i);});}

发表于 更新于 分类于 Valine： 本文字数： 2.9k 阅读时长 ≈ 3 分钟

切片

和python中的定义一致，习惯了，比按长度取字串方便，而且负下标也很方便

1
2
3
4
5
string slice(const string& s, int b, int e) {
    if(b<0) b += s.size();
    if(e<0) e += s.size();
    return s.substr(b, e-b);
}

去掉字符串前后的空白

python里叫strip，其他语言多叫trim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string strip(const string& s, const string& space=" ") {
    const char* p = &s[0];
    const char* q = &s[0]+s.size();
    for(; p<q; p++) {
        if(space.find(*p) == -1) break;
    }
    if(p<q) q--;
    for(; p<q; q--) {
        if(space.find(*q) == -1) {
            q++;
            break;
        }
    }
    return string(p, q);
}

切开(split)和拼接(join)

支持切开同时strip掉空白字符，比先切开再strip要快，还可以选择是否丢弃切开后空的元素。

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
vector<string> split(const string& s, const string& delim, const string& stripchars="", bool drop_empty=false) {
    vector<string> result;
    int b = 0;
    int e = 0;
    int i = b;
    int state = 0;
    do {
        bool isspace = (stripchars.find(s[i]) != -1);
        bool isdelim = (s[i]=='\0' || delim.find(s[i]) != -1);
        if(isdelim) {
            if(e != b || !drop_empty) {
                result.emplace_back(string(&s[b], &s[e]));
            }
            state = 0;
            e = b = i + 1;
        } else if(isspace) {
            if(state == 0) {
                e = b = i + 1;
            }
        } else {
            state = 1;
            e = i + 1;
        }
        if(s[i]=='\0') break;
        i++;
    } while(true);
    return result;
}

string join(vector<string> arr, const string& delim) {
    if(arr.empty()) return "";
    stringstream ss;
    ss << arr[0];
    for(int i=1;i<arr.size();i++) {
        ss << delim << arr[i];
    }
    return ss.str();
}

有限状态机

竞赛中字符串的题目可以考虑先画出状态转换图，然后基于有限状态自动机求解，包括上面的split函数，找不到之前的模板了，我重写的时候就是基于有限状态自动机

刚写出来是下面这样，很多重复代码，一共四个状态，完全就是按状态转移写的，非常清晰。

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
vector<string> split(const string& s, const string& delim, const string& stripchars="", bool drop_empty=false) {
    vector<string> result;
    int b = 0;
    int e = 0;
    int i = b;
    int state = 0;
    do {
        bool isspace = (stripchars.find(s[i]) != -1);
        bool isdelim = (s[i]=='\0' || delim.find(s[i]) != -1);
        switch(state) {
        case 0:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 1;
                e = b = i + 1;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        case 1:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 1;
                e = b = i + 1;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        case 2:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 3;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        default:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 3;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        }
        if(s[i]=='\0') break;
        i++;
    } while(true);
    return result;
}

当然还有可能表面是个字符串的问题，实际上是个动态规划问题或者搜索问题。

发表于 更新于 分类于 Valine： 本文字数： 12k 阅读时长 ≈ 10 分钟

最近在LeetCode刷题，又开始复习算法和数据结构，打算写一些东西，记录一些有通用价值的算法和数据结构。

先拿Treap开刀。

什么是Treap？

Treap是一种二叉搜索树（BST），我的本科毕业论文课题就是就是关于二叉搜索树（BST）的研究，Treap在各种操作的效率上不算优秀，全面优秀的是红黑树（RBT），红黑树也是实现起来最复杂的，各种语言的dict，map，set，大概率是基于红黑树实现的，那为什么我讲Treap不讲红黑树呢，因为Treap可能是最易理解且实现起来最简单的且效率还不错的BST，所以经常被用在竞赛中。

Treap支持的操作

1）插入

2）删除

3）查询存在或查询个数

4）查询元素的排名（即元素是第几小，或者说统计 小于/大于 指定元素的个数）

5）查询第 k 小元素

以上5个操作的平均时间复杂度都是O(logn)，

朴素BST的实现

我们先实现一个朴素的BST，为了简化起见：

1）仅支持3种基本操作，insert，erase，count。（名字按C++ STL容器的命名规则取的）

2）只存key而没有value，像set，而不是map。

3）不能插入重复的key，像set，而不是multiset。

4）没写销毁时的内存释放（那并不困难）

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
struct TreeNode {
    int key;
    TreeNode* left;
    TreeNode* right;

    TreeNode():TreeNode(0){}
    TreeNode(int key):key(key),left(NULL),right(NULL){}
};

class BST {
public:
    void insert(int key) {
        _insert(root, new TreeNode(key));
    }

    int count(int key) const {
        return _count(root, key);
    }

    void erase(int key) {
        return _erase(root, key);
    }

private:
    void _insert(TreeNode* &root, TreeNode* p) {
        if(root == NULL) {
            root = p;
        } else {
            if(p->key == root->key) return;
            if(p->key < root->key) _insert(root->left, p);
            else _insert(root->right, p);
        }
    }

    bool _count(TreeNode* root, int key) const {
        if(root == NULL) return 0;
        if(key == root->key) return 1;
        if(key < root->key) return _count(root->left, key);
        else return _count(root->right, key);
    }

    void _erase(TreeNode* &root, int key) {
        if(root == NULL) return;
        if(key == root->key) {
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            if(left == NULL) {
                delete root;
                root = right; // 因为左子树为空，直接用右子树当根就可以了
            } else if(right == NULL) {
                delete root;
                root = left;
            } else { // 左右子树都不空，把右孩子作为新根
                delete root;
                root = right;
                TreeNode* p = right; // 找到右子树中最小的节点，把左子树接上去
                while(p->left) { 
                    p = p->left;
                }
                p->left = left;
            }
        } else if(key < root->key) {
            _erase(root->left, key);
        } else {
            _erase(root->right, key);
        }
    }

private:
    TreeNode* root = NULL;
};

其中插入insert和查询count都比较简单，主要讲一下erase操作，当删除的是一个非叶子节点，要考虑如何把删除节点的左右子树接上，如果只有左子树或只有右子树，那么直接取代删除节点作为根就可以了，当左右子树都存在时，左右孩子都可以作为新根，这里选择右孩子作为新根，那么要把左子树接上，接到哪里呢，因为整个左子树都key都是小于右子树的，所以可以接在右子树最小的key的left上，而最小的key就是沿left一直下沉到的叶子。

这种删除处理方式虽然是满足BST的性质的，但是显然容易导致树越来越深，因为每次删除操作都会把一棵子树接到叶子节点上，而且总是接到左测最深处，以至于向链表退化，如果改成每次随机选择左右孩子作为新根都会比这好很多。再来看插入操作，只要升序或降序插入，就相当于一直朝着BST的最右或者最左节点插入，这会导致BST退化成链表，那么它的插入、删除、查询等操作的时间复杂度将退化成O(n)，这是不能接受的。各种不同的BST，其实都是通过增加约束条件，使用额外的维护操作维护约束的满足，来减小BST的最大深度，把平均甚至最坏的深度维持在O(logn)。

Treap是如何克服上述朴素BST的问题的呢？

Treap由二叉树和二叉堆组合形成，名字也因此为 tree 和 heap 的组合，除了记录key之外，它还额外记录一个priority来维持最大堆的性质，即父节点的priority大于等于两个子节点的priority，priority一般随机生成，正因为引入了最大堆的约束，和随机的priority，这棵树就不会在某种精心构造的插入删除序列下退化的很深，期望的深度是O(logn)，插入、删除、查询的期望复杂度也是O(logn)，最坏情况O(n)，依赖于priority的生成，因为priority是随机的所以最坏情况基本不会发生。

那么如何维护最大堆约束的满足呢？

我们要引入旋转操作，分左旋和右旋，如图所示：

容易看出旋转是不破坏BST性质的，对root右旋用文字描述就是，把root的左孩子作为新根，左孩子的右子树作为旧根的左子树，旧根作为新根的右子树，说起来绕来绕去不好理解，右旋就是把左孩子拎起来成为根，左旋就是把右孩子拎起来成为根，子树的切换是要维持BST性质，想搞错也不容易。

有了不破坏BST性质的旋转操作我们就可以维护堆的性质了，如果左孩子的priority比根大，我们就右旋，让左孩子成为根，如果右孩子的priority比根大，我们就左旋，让右孩子成为根。

Treap的实现

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
struct TreeNode {
    int key;
    int priority;
    TreeNode* left;
    TreeNode* right;

    TreeNode():TreeNode(0){}
    TreeNode(int key):key(key),priority(rand()),left(NULL),right(NULL){}
};

class Treap {
public:
    void insert(int key) {
        _insert(root, new TreeNode(key));
    }

    int count(int key) const {
        return _count(root, key);
    }

    void erase(int key) {
        return _erase(root, key);
    }

private:
    void lrotate(TreeNode* &root) {
        TreeNode* right = root->right;
        //if(right==NULL) return; // 右子树为空不能左旋
        TreeNode* rightleft = right->left;
        root->right = rightleft;
        right->left = root;
        root = right;
    }

    void rrotate(TreeNode* &root) {
        TreeNode* left = root->left;
        //if(left==NULL) return; // 左子树为空不能右旋
        TreeNode* leftright = left->right;
        root->left = leftright;
        left->right = root;
        root = left;   
    }

    void _insert(TreeNode* &root, TreeNode* p) {
        if(root == NULL) {
            root = p;
        } else {
            if(p->key == root->key) return;
            if(p->key < root->key) {
                _insert(root->left, p);
                if(root->left->priority > root->priority){
                    rrotate(root);
                }
            }
            else {
                _insert(root->right, p);
                if(root->right->priority > root->priority){
                    lrotate(root);
                }
            }
        }
    }

    int _count(TreeNode* root, int key) const {
        if(root == NULL) return 0;
        if(key == root->key) return 1;
        if(key < root->key) return _count(root->left, key);
        else return _count(root->right, key);
    }

    void _erase(TreeNode* &root, int key) {
        if(root == NULL) return;
        if(key == root->key) {
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            if(left == NULL) {
                delete root;
                root = right; // 因为左子树为空，直接用右子树当根就可以了
            } else if(right == NULL) {
                delete root;
                root = left;
            } else {
                if(left->priority < right->priority) {
                    rrotate(root); // 把优先级大的孩子转成根
                    _erase(root->right, key);
                } else {
                    lrotate(root);
                    _erase(root->left, key);
                }
            }
        } else if(key < root->key) {
            _erase(root->left, key);
        } else {
            _erase(root->right, key);
        }
    }

private:
    TreeNode* root = NULL;
};

先看插入操作，比朴素BST仅仅多了递归insert后的判断旋转，我们只需关注当前root是否需要旋转，因为这是在递归插入的回退过程中进行的旋转，事实上每次插入都是发生在叶子的，在递归插入回退的过程中新插入的节点会逐层地通过旋转被上推到合适的高度。

再看删除操作，甚至比朴素BST很简洁，在找到需要删除的节点后，我们总是先通过旋转把它下沉，直到它只有一个孩子或者没有孩子，然后再删掉它把孩子接上来。

Treap的完整实现

下面增加了销毁代码，并对动态空间申请释放做了优化，支持插入重复元素，并且实现了另外两个操作：

1）查询元素的排名（即元素是第几小，或者说有多少元素小于指定元素）

2）查询第 k 小元素

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
#include <iostream>
#include <cassert>
#include <vector>
#include <queue>

using namespace std;

namespace detail {

template <typename T>
struct TreeNode {
    T key;
    int priority;
    int size;
    TreeNode* left;
    TreeNode* right;

    TreeNode():TreeNode(0){}
    TreeNode(T key, int multi=1):key(key),priority(rand()),size(multi),left(NULL),right(NULL){}
};

template <typename T>
class TreeNodePool {
    int batchsize = 1024;
    vector<char*> memchunks;
    queue<char*> blocks;
public:
    ~TreeNodePool() {
        for(int i=0;i<memchunks.size();i++) {
            free(memchunks[i]);
        }
    }

    TreeNode<T>* create(int key, int multi=1) {
        if(blocks.empty()) {
            char* p = (char*)malloc(sizeof(TreeNode<T>)*batchsize);
            memchunks.emplace_back(p);
            for(int i=0;i<batchsize;i++) {
                blocks.push(p+sizeof(TreeNode<T>)*i);
            }
            batchsize *= 2;
        }
        char* p = blocks.front(); blocks.pop();
        return new (p)TreeNode<T>(key, multi);
    }

    void release(TreeNode<T>* p) {
        blocks.push((char*)p);
    }
};
} // namespace detail

template<typename T>
class Treap {
public:
    // key: 插入的元素
    // multi: 插入元素的重数
    int insert(T key, int multi=1) {
        return _insert(root, create_tree_node(key, multi));
    }

    // 返回等于key的元素个数
    int count(T key) const {
        return _count(root, key);
    }

    // key: 删除的元素
    // all: 如果有重复元素是否删除所有
    void erase(T key, bool all=false) {
        _erase(root, key, all);
    }

    // 返回树中元素个数
    int size() const {
        return _size(root);
    }

    // 返回第n小元素，从0起算
    T nth_element(int n) {
        assert(0<=n && n<size());
        return _nth_element(root, n)->key;
    }

    // 返回小于key的元素个数
    int cnt_less(T key) const {
        return _cnt_less(root, key);
    }

    // 返回小于等于key的元素个数
    int cnt_lesseq(T key) const {
        return cnt_less(key) + count(key);
    }

    // 返回大于key的元素个数
    int cnt_greater(T key) {
        return size() - cnt_lesseq(key);
    }

private:
    detail::TreeNode<T>* create_tree_node(T key, int multi=1) {
        return pool.create(key, multi);
    }
    void release_tree_node(detail::TreeNode<T>* root) {
        pool.release(root);
    }

    static int _size(detail::TreeNode<T>* root) {
        return (root != NULL ? root->size : 0);
    }
    // 返回root子树的size减去左右子树的size
    static int _count(detail::TreeNode<T>* root) {
        if(root == NULL) return 0;
        return _size(root) - _size(root->left) - _size(root->right);
    }

    static void lrotate(detail::TreeNode<T>* &root) {
        auto right = root->right;
        assert(right!=NULL);
        auto rightleft = right->left;
        root->right = rightleft;
        right->left = root;
        int root_size = root->size;
        root->size += _size(rightleft) - _size(right);
        right->size = root_size;
        root = right;
    }

    static void rrotate(detail::TreeNode<T>* &root) {
        auto left = root->left;
        assert(left!=NULL);
        auto leftright = left->right;
        root->left = leftright;
        left->right = root;
        int root_size = root->size;
        root->size += _size(leftright) - _size(left);
        left->size = root_size;
        root = left;   
    }

    int _insert(detail::TreeNode<T>* &root, detail::TreeNode<T>* p) {
        if(root == NULL) {
            root = p;
            return p->size;
        } else {
            if(p->key < root->key) {
                int r = _insert(root->left, p);
                root->size += r;
                if(root->left->priority > root->priority){
                    rrotate(root);
                }
                return r;
            } else if(root->key < p->key) {
                int r = _insert(root->right, p);
                root->size += r;
                if(root->right->priority > root->priority){
                    lrotate(root);
                }
                return r;
            } else {
                root->size += p->size;
                release_tree_node(p);
                return p->size;
            }
        }
    }

    static int _count(detail::TreeNode<T>* root, T key) {
        if(root == NULL) return 0;
        if(key < root->key) return _count(root->left, key);
        else if(root->key < key) return _count(root->right, key);
        else return _count(root);
    }

    int _erase(detail::TreeNode<T>* &root, T key, bool all) {
        if(root == NULL) return 0;
        if(key == root->key) {
            auto left = root->left;
            auto right = root->right;
            if(left == NULL) {
                int root_count = _count(root);
                if(!all && root_count > 1) {
                    root->size--;
                    return 1;
                } else {
                    release_tree_node(root);
                    root = right;
                    return root_count;
                }
            } else if(right == NULL) {
                int root_count = _count(root);
                if(!all && root_count > 1) {
                    root->size--;
                    return 1;
                } else {
                    release_tree_node(root);
                    root = left;
                    return root_count;
                }
            } else {
                int root_count = _count(root);
                if(!all && root_count > 1) {
                    root->size--;
                    return 1;
                } else {
                    int r = 0;
                    if(left->priority < right->priority) {
                        lrotate(root); // 把优先级大的孩子转成根
                        r = _erase(root->left, key, all);
                    } else {
                        rrotate(root);
                        r = _erase(root->right, key, all);
                    }
                    root->size -= r;
                    return r;
                }
            }
        } else if(key < root->key) {
            int r = _erase(root->left, key, all);
            root->size -= r;
            return r;
        } else {
            int r = _erase(root->right, key, all);
            root->size -= r;
            return r;
        }
    }

    static int _cnt_less(detail::TreeNode<T>* root, T key) {
        if(root == NULL) return 0;
        if(key < root->key) return _cnt_less(root->left, key);
        else if(root->key < key) return _size(root) - _size(root->right) + _cnt_less(root->right, key);
        else return _size(root->left);
    }

    static detail::TreeNode<T>* _nth_element(detail::TreeNode<T>* root, int n) {
        if(root == NULL) return NULL;
        int left_size = _size(root->left);
        int right_size = _size(root->right);
        if(n < left_size) return _nth_element(root->left, n);
        else if(n < _size(root) - right_size) return root;
        else return _nth_element(root->right, n - (_size(root) - right_size));
    }

private:
    detail::TreeNodePool<T> pool;
    detail::TreeNode<T>* root = NULL;
};

发表于 分类于 Valine： 本文字数： 691 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
# .tar.gz / .tgz 
alias tgzc='_tgzc(){ tar -zcvf `basename $1`.tar.gz $1; };_tgzc'
alias tgzx='tar -zxvf'
# .tar.bz2 / .tbz2
alias tbz2c='_tbz2c(){ tar -jcvf `basename $1`.tar.bz2 $1; };_tbz2c'
alias tbz2x='tar -jxvf'
# .tar.xz / .txz
alias txzc='_txzc(){ tar -Jcvf `basename $1`.tar.xz $1; };_txzc'
alias txzx='tar -Jxvf'
# .7z
alias 7zc='_7zc(){ 7za a -r `basename $1`.7z $1; };_7zc'
alias 7zx='_7zx(){ 7za x $1 -r -o./; };_7zx'

统一了不同格式的压缩解压命令，省略了参数，只支持最常用的情况，即：

· 压缩当前路径下的指定目录形成同名的压缩文件

· 提取当前路径下的指定压缩文件的内容到当前路径

压缩用法，压缩当前路径下的 foo 目录

1
tgzc foo
1
tgzc foo/
1
tgzc ./foo

都可以在当前目录生成 foo.tar.gz

解压用法，解压当前路径下的 foo.7z 文件到当前路径下

1
7zx foo.7z

发表于 更新于 分类于 Valine： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

Ubuntu

添加源，默认的稳定源里最新只有gcc8，如果需要更高的版本需要添加这个测试源，这一步不是必须做，可以先看看默认的源里是否已经有了你想要的版本

1
sudo add-apt-repository ppa:ubuntu-toolchain-r/test

更新软件列表

1
sudo apt-get update

安装想要升级的gcc/g++版本

1
sudo apt-get install gcc-9 g++-9

查看目前存在的版本

1
2
sudo updatedb && sudo ldconfig
locate gcc | grep -E "/usr/bin/gcc-[0-9]"

通过update-alternatives切换默认版本（本质是修改软连接，最后的数字是优先级，优先级高的自动为默认版本）

1
2
3
4
5
sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-7 20
sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-9 50

sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-7 20
sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-9 50

现在就升级好了，可以通过命令查看

1
2
gcc --version
g++ --version

BTW：

之后可以随时通过

1
sudo update-alternatives --config gcc

手动切换默认版本

而删除一个版本使用下面的命令

1
sudo update-alternatives --remove gcc /usr/bin/gcc-9

CentOS

安装scl源

1
yum install -y centos-release-scl scl-utils-build

查看可以安装的gcc版本

1
yum list all --enablerepo='centos-sclo-rh' | grep gcc

安装 devtoolset-9

1
yum install -y devtoolset-9-gcc.x86_64 devtoolset-9-gcc-c++.x86_64 devtoolset-9-gcc-gdb-plugin.x86_64

开启一个指定gcc/g++版本的bash

1
scl enable devtoolset-9 bash

可以在/etc/profile 中加入，这样每次登录就自动切换到gcc-9的环境了

指定cmake时的gcc版本

执行cmake生成Makefile时，cmake会去发现系统上的gcc

我实际使用时，在centos上系统存在gcc时，通过

1
scl enable devtoolset-9 bash

切换gcc版本后，使用cmake生成Makefile会出现仍然使用系统默认gcc的情况

解决方式：切换gcc版本后指定CC和CXX环境变量指向需要使用的gcc和g++，再执行cmake

1
2
export CC=`which gcc`
export CXX=`which g++`

发表于 分类于 Valine： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

/bin 存放基础命令的可执行文件和符号连接，包括cat, cp, ls, touch, rm等

/sbin 存放超级用户使用的基础的管理程序，包括ifup, iptables, mkfs, route, swapon等

/usr Unix Software Resource的缩写， 也就是系统软件资源所放置的目录，全部软件都安装在这里
/usr/bin 存放很多应用程序的可执行文件，包括akw, vim, gcc, go, cmake等
/usr/local/bin 存放安装出来的可执行文件，包括ipython, jupyter-notebook, pip, wheel等
/usr/sbin 存放一些非核心的管理程序和一些安装出来的daemon程序，包括useradd, nginx, netplan, mysqld, sshd等
/usr/include Linux下开发和编译应用程序需要的头文件
/usr/lib 动态链接共享库和静态档案库目录
/usr/src 源代码目录
/usr/doc 文档目录
/usr/man 帮助文档目录

/var variable的缩写，包含可变的数据文件
/var/log/ 各种程序的日志文件
/var/www/ nginx网站目录，相当于nginx的数据文件
/var/lib/ 各种程序运行时会改变的数据文件
/var/lib/docker/ docker的镜像和容器数据
/var/lib/mysql/ mysql数据库的数据
/var/lib/mongodb/ mongodb数据库的数据

/etc 包含所有系统管理和维护方面的配置文件
/etc/hosts 域名解析配置
/etc/resolv.conf 域名解析服务器配置
/etc/init.d/ 自启动脚本，详见 配置Linux开机启动脚本（基于initd）
/etc/rc?.d/ 自启动脚本的软连接，?表示系统的运行级
/etc/profile 所有用户登录Shell时执行
/etc/profile.d/ 所有用户登录Shell时遍历目录下的脚本执行
/etc/issue Linux版本信息
/etc/sudoers 配置允许sudo的用户
/etc/passwd 用户列表 username:原密码占位符x:uid:gid:描述性信息:家目录:默认Shell
/etc/apt/sources.list apt软件源配置，详见 替换Ubuntu 18.04软件源
/etc/network/interfaces 网卡配置文件
/etc/netplan/*.yaml 网卡配置文件
/etc/fstab 系统启动时自动执行的挂载路径，也是mount -a时挂载的路径，详见 Linux NFS共享目录配置及开机自动挂载
/etc/exports 配置通过nfs共享的目录，详见 Linux NFS共享目录配置及开机自动挂载
/etc/samba/smb.conf 配置通过samba共享的目录
/etc/systemd/system/*.service 自启动的服务配置文件的符号连接，详见 配置Linux开机启动脚本（基于systemd）
/etc/docker/daemon.json docker配置文件
/etc/nginx/nginx.conf /etc/nginx/sites-enabled/default nginx配置文件，详见 nginx配置
/etc/mysql/my.cnf /etc/mysql/mysql.conf.d/mysqld.cnf mysql配置文件
/etc/redis/redis.conf redis配置文件

/lib 包含系统引导和在root用户执行命令时候所必需用到的共享库

/home 所有普通用户家目录的父目录

/root root用户的家目录

/opt 用户级的程序目录，自己下载解压的软件可以放在这个目录下，然后将可执行文件的符号连接创建到 /usr/local/bin

/boot 目录存放系统核心文件以及启动时必须读取的文件，包括Linux内核的二进制映像

/tmp 临时文件目录

/mnt 该目录是默认的文件系统临时装载点

/media 挂在多媒体设备的目录，如默认情况下软盘、光盘、U盘设备都挂在在此目录

/dev 目录保存着外部设备代码的文件，这些文件比较特殊，实际上它们都指向所代表的外围设备，如终端、磁盘驱动器、光驱、打印机等。

/proc 进程文件系统proc的根目录，其中的部分文件分别对应正在运行的进程，可用于访问当前进程的地址空间。它是一个非常特殊的虚拟文件系统，其中并不包含“实际的”文件，而是可用以引用当前运行系统的系统信息，如CPU、内存、运行时间、软件配置以及硬件配置的信息，这些信息是在内存中由系统自己产生的。

/sys 是一个类似于proc文件系统的特殊文件系统，用于将系统中的设备组织成层次结构，并向用户模式程序提供详细的内核数据结构信息。其实，就是在用户态可以通过对sys文件系统的访问，来看内核态的一些驱动或者设备等。

/run 目录中存放的是自系统启动以来描述系统信息的文件。比较常见的用途是daemon进程将自己的pid保存到这个目录。标准要求这个文件夹中的文件必须是在系统启动的时候清空，以便建立新的文件。

发表于 分类于 Valine： 本文字数： 784 阅读时长 ≈ 1 分钟

本文的操作在我的Ubuntu 18.04上并不能正常工作，我觉得这和系统启动是使用initd还是systemd有关

检查根进程是initd还是systemd

通过

1
pstree -p|head -1

或

1
ps -ef|awk '($2==1)'

可以看到系统的1号进程，也就是启动全部进程的根进程是initd还是systemd。

systemd参考 配置Linux开机启动脚本（基于systemd）

创建开机启动脚本

先将脚本放在 /etc/init.d/ 下，例如脚本名为 new_service.sh

执行如下指令，在这里90表明一个优先级，越高表示执行的越晚

1
2
cd /etc/init.d/
sudo update-rc.d new_service.sh defaults 90

创建完成会在 /etc/rc*.d/ 下生成相应的软连接

rc后面的数字含义

  • 0 Halt the system 停机（千万不要把 initdefault 设置为0），机器关闭
  • 1 Single user mode 单用户模式，与 Win9x 下的安全模式类似
  • 2 Basic multi user mode 基本多用户模式，没有 NFS 支持
  • 3 Multi user mode 完整的多用户模式，是标准的运行级
  • 4 None 一般不用，在一些特殊情况下可以用它来做一些事情。例如在笔记本电脑的电池用尽时，可以切换到这个模式来做一些设置。
  • 5 Multi user mode with GUI 就是X11，进到XWindow系统了
  • 6 Reboot the system 重新启动（千万不要把initdefault 设置为6），运行 init 6 机器就会重启
  • S, s Single user mode

软连接开头为Kxx或Sxx，Kxx表示不启动（似乎和这个文件不存在一样），Sxx表示启动，xx是启动顺序，01~99。

移除开机启动脚本

1
sudo update-rc.d -f new_service.sh remove

发表于 分类于 Valine： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

检查根进程是initd还是systemd

通过

1
pstree -p|head -1

或

1
ps -ef|awk '($2==1)'

可以看到系统的1号进程，也就是启动全部进程的根进程是initd还是systemd。

initd参考 配置Linux开机启动脚本（基于initd）

基于systemd的自启动首先需要创建服务，在服务配置文件中配置调用需要自启动的脚本，然后设置服务自启动。

创建服务

在 /lib/systemd/system/ 下新建.service文件，例如 kafka.service

1
2
3
4
5
6
7
8
9
10
[Unit]
Description=Kafka Server
After=network.target zookeeper.service

[Service]
Type=simple
ExecStart=/opt/kafka_2.12-2.3.1/bin/kafka-server-start.sh /opt/kafka_2.12-2.3.1/config/server.properties

[Install]
WantedBy=multi-user.target

配置自启动脚本

其中最重要的，运行脚本，配置在ExecStart，如果脚本里面启动的程序是常驻内存的，这里不用设置后台运行。

After 用来配置服务的依赖项，表示服务器希望在哪些服务后启动。

WantedBy 类似系统的运行级别，如果只希望在图形界面自启动可以配置成 graphical.target ，默认配置成 multi-user.target 即可。

配置简单服务以上就够了，更详细的说明可以参考 Systemd 入门教程：实战篇 - 阮一峰的网络日志 (ruanyifeng.com)

修改服务配置文件后需要重新载入服务配置文件.

最后不要忘了设置服务自启动 systemctl enable kafka.service ，随便给出服务相关的常用命令。

都以kafka为例，清自行替换成其他服务。

常用服务配置命令

重新载入服务配置文件

1
systemctl daemon-reload

设置服务自启动

1
systemctl enable kafka.service

查询是否自启动服务

1
systemctl is-enabled kafka.service

取消服务自启动

1
systemctl disable kafka.service

常用服务控制命令

查询服务状态

1
service kafka status

启动服务

1
service kafka start

停止服务

1
service kafka stop

重启服务器

1
service kafka status

发表于 更新于 分类于 Valine： 本文字数： 428 阅读时长 ≈ 1 分钟

大学时候，尤其大二大三，因为参加ACM ICPC的关系，沉迷于在各大高校的OJ刷题（主要在 ZJU, PKU, HDU），回想起那时，写DP状态转移方程，编码，提交，AC一气呵成的爽快感至今仍然鲜活，以至于刚毕业那几年还时不时的做几道玩。

后来也许是工作忙了，也许是其他事情多了，也许是兴趣转移了（向投资），……，总之算来已经好久没有做题了。

今天从B站一个UP主那边发现了这个网站
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 https://leetcode.cn

（从我的邀请连接注册学习可以帮我拿点积分）

似乎主要面向在职人群，我看还提供了面试求职之类的功能

新注册会询问你是在职还是学生，工作领域是前端、后端还是移动端等等。

然后就给我推了个新手专属题单

这我就忍不了了啊，水了一把

支持的语言有C++、Java、Python、JavaScript、Go、Rust等等，基本上传统主流和新兴主流语言都支持。

我发现答这种题我竟然还是倾向于用C++大于Python。

发表于 更新于 分类于 Valine： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

代码库地址

https://code.aliyun.com/daimingzhuang/flask-restful.git

目录结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
.
├── README.md             # 说明文件
├── config.yml            # 全局配置文件
├── foo.db                # 测试用的SQLite数据库，可以删掉
├── resources             # RESTful资源目录
│   ├── BaseResource.py   # 定义了几个资源的基类，通用的CRUD接口，并实现了列表的条件查询、排序和分页。
│   ├── IndexResource.py  # 示例主页，可以删掉
│   ├── TokenResource.py  # Token示例，用来查询登录（GET）、登录（POST）、登出（DELETE），可根据实际情况改写
│   ├── UserResource.py   # 用户资源示例
│   └── __init__.py       # 统一绑定资源到URI
├── rest_server.py        # 服务器主程序
└── utils
    ├── __init__.py
    ├── common.py         # 定义了一些通用的工具
    ├── config.py         # 读取全局配置文件
    ├── db.py             # 数据库模型定义、关系映射等
    ├── db_base.py        # SQLAlchemy ORM 框架基类
    ├── logger.py         # 日志
    ├── mutex.py          # 基于Redis的跨进程锁，实现了互斥锁和读写锁
    ├── redis_pool.py     # Redis连接池
    └── redis_session.py  # 基于Redis的HttpSession

环境依赖

python3

pip3 install -r requirements.txt

1
2
3
4
5
flask
flask-restful
sqlalchemy
redis
pyyaml

开发指南

根据项目情况配置 config.yml

修改 utils/db.py ，对数据模型（即数据库的表）进行定义。

在 resources 下新建资源，继承 BaseResource 中的某个基类，有需要时可重写get/post/put/delete方法实现自定义的业务逻辑。

在 resources/__init__.py 中添加资源的URI映射。

utils文件夹除了db.py，其他代码通用性都比较强，一般都只需使用无需修改。

resources文件夹除了BaseResource.py，其他代码可以认为都是示例，应该根据需要修改和删除。

httpsession存储在redis服务器中，前端的登录标识通过登录返回的header中的token字段和数据的{“data”: {“token”: “xxx”}}同时返回，前端后续的请求应该在header携带token字段（或token参数）以表明身份，具体可以看后面的请求示例。

启动方式

开发环境

1
python3 reset_server.py

Linux上的生产环境

1
gunicorn -b 0.0.0.0:8088 rest_server:app

请求示例

查询当前登录状态

1
GET http://localhost:8088/Token

response text

1
2
3
4
5
{
    "result_code": "fail",
    "err_code": "LOGIN_FAILED",
    "err_code_des": "用户未登录"
}

登录

1
2
POST http://localhost:8088/Token
body {"username":"admin", "password":"123456"}

response text

1
2
3
4
5
6
7
8
9
10
11
{
    "result_code": "success",
    "data": {
        "token": "66007530da1e424ba35006afad746fa9",
        "user": {
            "id": 1,
            "username": "admin",
        },
        "create_time": 1651989903.466016
    }
}

查看登录后的测试主页

1
2
GET http://localhost:8088/
header token: 66007530da1e424ba35006afad746fa9

response text

1
"Hello, admin."

查询列表指定条件、分页、排序

1
2
http://localhost:8088/Users?page=1&page_size=15&sort=username&order=asc&username_like=a%n
header token: 66007530da1e424ba35006afad746fa9

response text

1
2
3
4
5
6
7
8
9
10
11
12
13
{
    "result_code": "success",
    "data": [
        {
            "id": 1,
            "username": "admin"
        }
    ],
    "total": 1,
    "page": 1,
    "page_size": 15,
    "page_num": 1
}

更多的查询条件使用方法，可以阅读 resources/BaseResource.py 中 ROPluralResource 类的 get 方法的源码