深信服软件开发笔试A卷 编程题题解
代码都是事后写的，没有数据验证 代码仅供参考 主要讨论思路。
第一题：实现LRU缓存
题意：实现一个基于LRU算法容量为n的缓存，对外提供int get(int key), void set(int key, int val)两种操作。
输入：第一行输入n,m代表缓存容量n和m次操作。接下来m行输入m次操作，每次操作为两种类型其中一种。
- g key
- s key val
样例：
3 13 s 1 1 s 2 2 s 3 3 g 1 s 4 4 g 2 g 3 s 5 5 g 1 g 4 g 3 s 5 5 g 2
1 -1 3 -1 4 3 -1
分析：LRU很简单，这里提供一个O(1)的思路。即用hash表+链表，使用链表存储缓存节点真实数据，使用hash表<key, Node>每个key指向对于链表的节点。
查询：通过key查询hash表得到Node，然后得到val 复杂度O(1)
更新：同上，覆盖val 复杂度O(1)
删除：删除链表头元素（这里我用的头，用尾一样的），然后删除hash表对应的key 复杂度O(1)
增加：若无容量，先删除。然后将新元素插入到链表尾，同时新增hash表<key, Node> 复杂度O(1)
代码（笔试完重新写的，没有数据验证，可能会存在问题。不过可以参考）：
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key,val;
Node* nxt;
Node* pre;
Node() = default;
Node(int key, int val) : key(key), val(val) {}
};
struct List {
Node* head;
Node* tail;
List() {
head = new Node();
tail = new Node();
head -> nxt = tail;
tail -> pre = head;
}
};
struct LRU {
LRU(int cap_) : cap_(cap_) {
size_ = 0;
}
void toTail(int key) {
auto node = mp_[key];
node -> pre -> nxt = node -> nxt;
node -> nxt -> pre = node -> pre;
node -> nxt = list.tail;
node -> pre = list.tail -> pre;
list.tail -> pre -> nxt = node;
list.tail -> pre = node;
}
int get(int key) {
if(mp_[key]) {
toTail(key);
return mp_[key]->val;
}
return -1;
}
void set(int key, int val) {
if(mp_[key]) {
mp_[key] -> val = val;
toTail(key);
return;
}
if(size_ >= cap_) {
auto oldNode = list.head -> nxt;
oldNode -> nxt -> pre = list.head;
list.head -> nxt = oldNode -> nxt;
mp_.erase(oldNode -> key);
size_--;
delete oldNode;
}
Node* newNode = new Node(key, val);
newNode -> nxt = list.tail;
newNode -> pre = list.tail -> pre;
list.tail -> pre -> nxt = newNode;
list.tail -> pre = newNode;
mp_[key] = newNode;
size_++;
}
private:
unordered_map<int, Node*>mp_;
List list;
int size_;
int cap_;
};
int main() {
int n, m;
cin >> n >> m;
LRU lru(n);
while(m--) {
string op;
cin >> op;
if(op == "g") {
int key;
cin >> key;
cout << lru.get(key) << endl;
} else {
int key, val;
cin >> key >> val;
lru.set(key, val);
}
}
}
第二题：二分查最大值
题意：主角想要建立一个游戏公会，他想捞自己n个朋友的一些人加入公会，朋友有角色等级L、对主角的好感度F两种属性。但是公会内若存在两个等级差大于等于d的朋友，则等级低的朋友好感度会降为0。现在他想捞一些朋友进入公会使得公会整体对主角的好感度和最大。
数据范围：n大概为1e5数量级。L,F大概为[0,1e9]
分析：一眼想到因为等级低的会被影响，只要我们确定最高级MaxLevel以后把所有大于MaxLevel - d且小于MaxLevel的朋友全部捞进来就行。因此先对等级L排序，然后对好感F做一个前缀和用于后面计算等级区间(MaxLevel - d, MaxLevel]用户的和。
因此后续就很简单了，从后往前遍历然后二分查询到大于MaxLevel - d的第一个位置就行。时间复杂度O(nlogn)
样例：
6 3 4 5 3 2 8 6 7 4 2 5 1 3
12
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
int main() {
int n, d;
cin >> n >> d;
vector<pll>f(n+1);
for(int i = 1; i <= n; i ++) {
cin >> f[i].first >> f[i].second;
}
sort(f.begin(), f.end());
for(int i = 1; i <= n; i ++) {
f[i].second += f[i-1].second;
}
ll maxVal = 0;
for(int i = n; i >= 1; i --) {
int minLevel = f[i].first - d + 1;
pll pi = {minLevel, 0LL};
auto p = lower_bound(f.begin() +1, f.end(), pi) - f.begin();
maxVal = max(maxVal, f[i].second - f[p-1].second);
}
cout << maxVal << endl;
}
第三题：hash、前缀树、线段树匹配IP地址
题意：给n(1e4)个IP匹配规则，规则一共有3类
- 相等：即10.10.10.10与10.10.10.10相等
- ip范围内：如10.10.10.10 在10.10.10.0,11.11.11.11内
- 同一个网段下：即前缀相同，如10.10.1.1. 匹配 10.10.0.0/16
现输入m(1e6)个IP地址，输出每个IP共匹配多少个规则。
分析：首先我们可以把string的ip转换成一个uint32，我这里用uint64方便计算。
- 对于相等，我们可以直接用hash表计数即可。
- 对于ip范围，因为n数据范围达到了(1e4)若硬匹配则需要nm的复杂度。考虑区间我们想到使用线段树，每个节点代表一个区间，不难发现对于一个匹配规则代表的区间，在线段树上最多被划分32个子区间（这里不证明），因此线段树节点数最多不会超过32n，线段树的高度最多为32，此时匹配一次时间复杂度为O(log(MAXVAL))即最大次数为32。对于线段树的构造和匹配参考代码即可。
- 对于网段，同理我们构造一个前缀树即可。一个规则结束后计数，匹配时记录路径的总和。路径长度一样为32。
综上时间复杂度为O(1)+O(log(MAXVAL))满打满算就是32m。
#include <iostream>
#include <unordered_map>
using namespace std;
using u64 = uint64_t;
// n = 1e4, m = 1e6
u64 string2u64(const string &ip) {
u64 intIp = 0;
for (int i = 0; i < ip.size(); i++) {
int j = i;
while (j < ip.size() && ip[j] != '.')
j++;
// 提取每个字节
int seg = 0;
// cout << i << " " << j << endl;
for (int k = i; k < j; k++) {
seg *= 10;
seg += ip[k] - '0';
}
// cout << seg << endl;
// 倒序
for (int k = 1; k <= 8; k++) {
intIp <<= 1;
intIp |= (seg >> (8 - k) & 1);
}
i = j;
}
return intIp;
}
// Type 1 use hash
unordered_map<u64, int> t1_map;
void setType1(u64 ip) {
t1_map[ip]++;
}
int getType1(u64 ip) {
if (t1_map.find(ip) != t1_map.end())
return t1_map[ip];
return 0;
}
// Type 2 use segment tree
struct Node {
int cnt;
Node *left;
Node *right;
Node() : left(nullptr), right(nullptr), cnt(0) {}
~Node() {
delete left;
delete right;
}
} *root = new Node();
void insert(Node *&root, u64 l, u64 r, u64 L, u64 R) {
if (L <= l && R >= r) {
root->cnt++;
return;
}
auto m = (l + r) >> 1;
if (L <= m) {
if (root->left == nullptr) {
root->left = new Node();
}
insert(root->left, l, m, L, R);
}
if (R > m) {
if (root->right == nullptr) {
root->right = new Node();
}
insert(root->right, m + 1, r, L, R);
}
}
int find(Node *root, u64 l, u64 r, u64 ip) {
int ans = 0;
if (ip >= l && ip <= r) {
ans += root->cnt;
}
auto m = (l + r) >> 1;
if (root->left && ip <= m) {
ans += find(root->left, l, m, ip);
}
if (root->right && ip > m) {
ans += find(root->right, m + 1, r, ip);
}
return ans;
}
void setType2(u64 lt, u64 rt) {
insert(root, 0, (1ULL << 32) - 1, lt, rt);
}
int getType2(u64 ip) {
return find(root, 0, (1ULL << 32) - 1, ip);
}
// Type 3 use prefix-tree
const int N = 1e4 * 32 * 2;
int trie[N][2], cnt;
int res[N];
void setType3(u64 ip, int prefix) {
int p = 0;
for (int i = 1; i <= prefix; i++) {
auto x = (ip >> (32 - i)) & 1;
if (!trie[p][x]) {
trie[p][x] = ++cnt;
}
p = trie[p][x];
}
res[p]++;
}
int getType3(u64 ip) {
int as = 0;
int p = 0;
for (int i = 1; i <= 32; i++) {
as += res[p];
auto x = (ip >> (32 - i)) & 1;
if (!trie[p][x]) {
return as;
}
p = trie[p][x];
}
return as;
}
/*
8 10
1 10.10.0.1
1 9.9.9.9
2 10.0.0.0 11.0.0.0
2 0.0.0.0 10.5.5.5
2 10.0.0.0 192.0.0.1
2 127.0.0.1 196.168.1.1
3 10.10.0.0/16
3 11.0.0.0/8
10.10.0.1
11.1.1.1
*/
int main() {
int n, m;
cin >> n >> m;
while (n--) {
int op;
cin >> op;
if (op == 1) {
string ip;
cin >> ip;
setType1(string2u64(ip));
} else if (op == 2) {
string lt, rt;
cin >> lt >> rt;
// cout << string2u64(lt) << " " << string2u64(rt) << endl;
setType2(string2u64(lt), string2u64(rt));
// TODO
} else {
int prefix = 0;
string s;
cin >> s;
int i = 0;
while (i < s.size() && s[i] != '/')
i++;
for (int j = i + 1; j < s.size(); j++) {
prefix *= 10;
prefix += s[j] - '0';
}
// cout << s.substr(0, i) << " " << prefix << endl;
setType3(string2u64(s.substr(0, i)), prefix);
}
}
while (m--) {
string ip;
cin >> ip;
u64 IP = string2u64(ip);
cout << getType1(IP) << " " << getType2(IP) << " " << getType3(IP) << endl;;
}
}
第四题：主席树？
题意：给一个长度为n的数组，现要求取一个长度为k的子序列（序列可以不连续，即1 1 4 5 1 4 可以取一个子序列4 4）。然后将这个子序列分为两半，前一半的和与后一半和取最大值。现在要最小化这个最大值。
Example：8 1 1 1 7 7 8 k=5，此时我们需要取8 1 1 1 7，答案为9（此时能发现不能用贪心，即1 1 1 7 7）
思路：开始做这道题我知道时间不够了，我就用贪心骗了60分。贪心思路也很简单，取n个数中最小的k个数出来，并枚举位置。思路很简单，直接看代码。
真实解法？：枚举前半段和后半段数组边界，二分前半段序列长度x(x <= k)，使得前半段最小x个元素和与后半段最小k-x个元素和差值最小。枚举的时间复杂度是O(n)，群友说最小的x个元素可以用主席树log拿出来，因此总体时间复杂度是nlognlogn。但是我不想写了。
贪心代码如下：
#include<iostream>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
int main() {
int n, k;
cin >> n >> k;
vector<pll> v(n + 1);
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> v[i].first;
v[i].second = i;
}
sort(v.begin() + 1, v.end());
for (int i = 1; i <= k; i++) {
a[v[i].second] = v[i].first;
}
for (int i = 1; i <= n; i++) {
a[i] += a[i - 1];
}
ll minVal = 0x3f3f3f3f3f3f3f3f;
for (int i = 1; i <= n; i++) {
minVal = min(minVal, max(a[i] - a[0], a[n] - a[i]));
}
cout << minVal << endl;
}
#笔试真题##笔试面经##笔试题解#
