首页 > 2020/8/25晚七点深信服后台开发岗编程题
头像
Ember_Sky
编辑于 2020-08-25 23:27
+ 关注

2020/8/25晚七点深信服后台开发岗编程题

第一道题大意:
一次操作:指定一个树的高度不变,其他树加一
求多少次操作之后,所有树的高度一样

思路:
这题可以反过来看,
一次操作:将一个树的高度减一,其他树不变
求多少次操作之后,所有树的高度一样
这么问,就很简单了,让所有树都减去最低的那个树,剩下所有树的和就是答案了
写的时候,可以在输入的时候,记录最小值,同时统计所有树的和 sum。
其实 sum 只是比答案多了 n 个最小值
输入完成之后
答案 = sum -  (n * 最小值)

第二题大意:
给定一个只含数字的字符串,
输入 n 行 a 和 b
每行代表将 a 字符换成 b 字符


这题本来想着会用什么邻接表,建树,等等,后来发现,我是真的蠢
思路:
要是按照正常的操作:每输入一行就遍历一遍字符串,肯定超时,简单的有优化基本没用,没get到出题的点

其实你仔细研究几个样例就知道了
不管输入几行交换数据,针对最后的结果,只有十种情况,因为他只有十种数字
1. 原字符串中的 0 最后要换成什么
2. 原字符串中的 1 最后要换成什么
。。。
。。。
10. 原字符串中的 9 最后要换成什么

这么说的话,我们可以先将 n 行数据进行处理,处理之后,在对原字符串进行替换

可以定义一个大小为十的数组 s[10],,,    其中s[2]就表示最后要吧 2 换成 s[2]
初始让每个元素都等于自己的下标,因为自己换成自己嘛
接下来每输入一行 a b ,就遍历一遍这个数组
将对应存储的值为 a 的,全换成 b

例子:
假设:有4行输入(0,2)(3,0)(0,4)(4,1)
第一行之后,
s[0]的值等于0,所以
s[0]=2;
其他不变

第二行之后,
s[3]的值等于3,所以
s[3]=0

第三行之后
s[3]的值等于0,所以
s[3]=4

第四行之后
s[3]和s[4]的值都是4,所以
s[3]=1
s[4]=1

输入全部完成之后
遍历原字符串
针对每个字符
将他替换成s数组对应的就可以

看一下复杂度:
输入的同时遍历s数组,这个复杂度是在n的基础上乘10
n好像是1e6,乘10也就1e7

然后就是输出了,字符串的长度好像也是1e6

除此之外就没别的操作了
总复杂度11*n
1e7的复杂度,C++完全罩得住

深信服非要挑七夕笔试,我觉得可能是在明示:有对象的人不要来,我们不要

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐