深信服软件开发笔试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

样例：

分析：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)

样例：

代码：

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

#笔试真题##笔试面经##笔试题解#