9.1 深信服笔试
算法工程师岗位，感觉难度在最近做过的其它笔试中算是比较难的一次了。以下代码均为全A通过，可供参考。
第一题：日志分析
一组攻击先后包含 s w r。现有 T 份日志，每份是一个小写字母字符串，需要从每份日志里，统计有多少种可能的潜在攻击。
输入：正整数 T，紧接着是 T 行日志
输出：T 行，每个日志的潜在攻击数。需要对 1e9+7 取模
解法：这题相当于查找字符串中有多少个 "swr" 子序列。用动态规划比较高效，否则有些大测试点估计过不了
考虑如下三个动态规划函数：
- dp_s。其中 dp_s[i] 代表字符串的前 i 个字符，有多少个子序列 "s"。
- dp_sw。其中 dp_sw[i] 代表字符串的前 i 个字符，有多少个子序列 "sw"。
- dp_swr。其中 dp_swr[i] 代表字符串的前 i 个字符，有多少个子序列 "swr"。
状态转移，需要看字符串的第 i 位是什么。比如是 'r'，那么它可以额外提供的 "swr" 子序列数量即为 dp_sw[i]。其余同理，因此状态转移函数总结如下：
- 如果字符串的第 i 位是 's'，则 dp_s[i] = dp_s[i - 1] + 1，否则 dp_s[i] = dp_s[i - 1]
- 如果字符串的第 i 位是 'w'，则 dp_sw[i] = dp_sw[i - 1] + dp_s[i]，否则 dp_sw[i] = dp_sw[i - 1]
- 如果字符串的第 i 位是 'r'，则 dp_swr[i] = dp_swr[i - 1] + dp_sw[i]，否则 dp_swr[i] = dp_swr[i - 1]
我只用了 s w r 三个变量表示循环中的三个函数值。最终输出 dp_swr[n] % (1e9+7) 的值即可。
T = int(input()) for _ in range(T): info = input() s = w = r = 0 for i in range(len(info)): if info[i] == 's': s += 1 # 遍历到第i位时，s表示 dp_s[i]的值，下同 elif info[i] == 'w': w += s elif info[i] == 'r': r += w print(int(r % (1e9+7)))
第二题：深信服旅游
有 T 组测试数据。每组包含正整数 n，表示员工数。之后是 n 行，每行两个正整数a, b，表示一位员工方便旅游的时间段为 [a, b]。问最多可以同时让多少位员工觉得方便。
输入：正整数 T。之后 T 组数据，每组先输入正整数 n；然后是 n 行，每行两个正整数
输出：T行，每组测试数据的结果
备注：O(n^2)的算法可得一半分，O(nlogn)的算法可得满分
解法：贪心算法
对于每组数据，分别用数组A， B记下来所有的开始时间和所有的结束时间，并不需要考虑它们来自于哪位员工。将它们升序排列。
为什么不需要考虑它们来自哪个员工呢？
因为我们只关注每个区间的进入和退出。比如两个区间 (1,4)+(2,3)，实际上和 (1,3)+(2,4) 是没有区别的。
我们要做的，是给定这些区间的首尾值，判断最多有多少个区间重合。
遍历数组A，每次找到 A[i]，相当于有一个区间开始。我们还要查看这时有多少区间已经结束。因此需要在数组B中维护一个动态指针p（p表示当前有多少个区间已经结束）。如果当前p指向的结束时间小于 A[i]，说明当前的区间已经结束，需要不断将p右移。操作完成后，p 和 i 的下标差加1即为当前区间的重合数。
最后，每步中找到的区间重合数去一个最大值即为所求。
T = int(input()) for _ in range(T): # T组测试数据 n = int(input()) A, B = [], [] for __ in range(n): # 每组数据n个员工 a, b = [int(x) for x in input().split()] A.append(a) B.append(b) A.sort() B.sort() p = ans = 0 for i in range(n): while p < n and A[i] > B[p]: p += 1 ans = max(ans, i - p + 1) print(ans)
第三题：五进制
设定一种五进制，其中 o, y, e, a, s 分别代表 0, 1, 2, 3, 4。例如五进制 ya 代表十进制 8。
有 T 组测试数据。每组包含一个数字，或字母oyeas组成的字符串。实现进制的相互转换，并输出每个测试数据的转换结果。
输入：正整数 T。之后 T 行，每行一个【五进制字母串】或【十进制数】
输出： T 行，给定测试如果是五进制，则输出十进制数；给定测试如果是十进制，则输出五进制字符串
压轴题反而是最简单的，跟二进制转化没啥区别。
十进制转五进制，每次对5取模，得到最低位，然后将数字除以5，直到数字变为零；
五进制转十进制，遍历字符串。长度为 n 的字符串，第 i 位是x，则它的贡献为 x * 5 ^ (n - i - 1)。循环求和即可
import math
T = int(input())
for _ in range(T):
ipt = input()
if ipt.isdigit():
if ipt == '0':
print('o')
continue
ans = ''
ipt = int(ipt)
while ipt > 0:
ans = 'oyeas'[ipt % 5] + ans
ipt //= 5
print(ans)
else:
ans = 0
for i in range(len(ipt)):
ans += 'oyeas'.index(ipt[i]) * math.pow(5, len(ipt) - i - 1)
print(int(ans)) 可能有些地方写得不是很明白，有问题欢迎留言讨论，一起进步！
#深信服##深信服笔试题#
当时用优先队列a的 （PS：没给用java语言。差点死了（指用cpp头文件都忘记咋写了））
查看8道真题和解析
