深信服秋招8.23笔试-后端开发（AK）

1、填空题（42分：14题 * 3）

一部分简单八股（链表、哈希表、计算时间空间复杂度）＋智商测评（找规律，逻辑推理）

总体简单

2、编程题（58分：8 + 15 + 15 + 20）

（1）给定两个数x, y、 求 x 的 y 次方的最后一位

做法：快速幂求，过程对10取模，题目没说数据范围，开 long long 才能过。

（2）判断一个字符串是否满足DNS格式，具体限制不记得了，还蛮复杂

做法：模拟判断，仔细看看还有哪种情况漏算，（最后10分钟才调到满分，前面一直96%）

（3）给定一个字符串 s 和字符串数组 st[], 问 st[] 中有多少个字符串是 s 的字串

做法：这题也没说数据范围，想着总不能出个 n^2 的题，所以一开始就往 nlogn 想了

先把 s 的每种字符下标存进 map<char, vector<int>>里面,

对于每个 st[i] 遍历每个字符 st[i][j]，二分找到当前 st[i][j] 字符在vector中最小且满足大于前一个字符的下标并更新，如果最后一个字符能找到满足的说明该字符串是 s 字串。

（4）给定一个 n * m二维数组地图，-1 表示不能走，0 ~ 5 表示当前位置的金币数量，A从左上角出发，同时具有一个能力，能将一个 -1 变成 0 （只能用一次），问能收集到的最大金币数量为多少？(不设终点)

数据范围：1<= n, m <= 100

首先这题输入特别抽象， 样例输入 [1, -1]

[-1, 1]

连n, m不给就算了，还要用getline读入自己拆分，这里就花了不少时间

做法：这题显然用一次宽搜（类似普通走迷宫）能做，但是当时用了另外一种（以为比较简单但实际也挺麻烦）

首先把每个连通块用多次宽搜跑出来，顺便算出每个连通块的金币和

当出发点是 -1 时： 答案为出发点右边和下面两个点所属连通块总和的和，记得判断是否是一个连通块

当出发点不为 -1 时：重新扫一遍地图，对于每个 -1 点， 算出这个点上下左右四个点分别所属联通块的总和的和，答案取max, 同样记得判断是否有相同的联通块（可以用set）, 这里还需要判断四个联通块中是否有联通块能通向起点！不然没用，比较好写的办法是用类似于并查集的写法，将一个联通块中的所有点的 father 都指向这个联通块最左上角的点（这样起点一定是被指向的点）。

总结：选择题总体简单，编程题不难想，但是满分需要注意很多细节，特别第二第四题。希望给个面吧球球了