B站2019秋招编程题

B站在牛客网（ https://www.nowcoder.com/test/16519291/summary ）
上发了一套自己秋招的编程题，恰好今年被老师忽悠着去再参加一次蓝桥杯（我参加C++组，所以下面的题都是用C++做的，没用我熟悉的python），虽然那个比赛很水，但是还是要提高我的编程能力才是。于是准备做点题练习下，B站这个题挺好，题目很新颖（仅限题目描述），不过内容和那个比赛一样水，所以给大家解析下。

1.扭蛋机 answer

时间限制：1秒
空间限制：32768K

22娘和33娘接到了小电视君的扭蛋任务：
一共有两台扭蛋机，编号分别为扭蛋机2号和扭蛋机3号，22娘使用扭蛋机2号，33娘使用扭蛋机3号。
扭蛋机都不需要投币，但有一项特殊能力：
扭蛋机2号：如果塞x（x范围为>=0正整数）个扭蛋进去，然后就可以扭到2x+1个
扭蛋机3号：如果塞x（x范围为>=0正整数）个扭蛋进去，然后就可以扭到2x+2个
22娘和33娘手中没有扭蛋，需要你帮她们设计一个方案，两人“轮流扭”（谁先开始不限，扭到的蛋可以交给对方使用），用“最少”的次数，使她们能够最后恰好扭到N个交给小电视君。

输入描述:

输入一个正整数，表示小电视君需要的N个扭蛋。

输出描述:

输出一个字符串，每个字符表示扭蛋机，字符只能包含”2”和”3”。

输入例子1:

10

输出例子1:

233

思路有两种，一种是BFS，一种是通过二叉树（其实你看到2x+1和2x+2就差不多知道了），因为这个题是这样的：

可以看到，n是奇数都是最后22扭的，n是偶数都是最后33扭的，那么我们就可以倒着找出最终的顺序。找到下一层之后返回上一层，如果是奇数就是(n-1)/2,偶数就是(n-2)/2，具体可自行验证。给出C++的示例代码：

2.脸滚键盘 answer

时间限制：1秒
空间限制：32768K

av394281 中，充满威严的蕾米莉亚大小姐因为触犯某条禁忌，被隙间妖怪八云紫（紫m……èi）按住头在键盘上滚动。
同样在弹幕里乱刷梗被紫姐姐做成罪袋的你被指派找到大小姐脸滚键盘打出的一行字中的第 k 个仅出现一次的字。
(为简化问题，大小姐没有滚出 ascii 字符集以外的字)

输入描述:

每个输入都有若干行，每行的第一个数字为k，表示求第k个仅出现一次的字。然后间隔一个半角空格，之后直到行尾的所有字符表示大小姐滚出的字符串S。

输出描述:

输出的每一行对应输入的每一行的答案，如果无解，输出字符串Myon~

(请不要输出多余的空行）

为了方便评测，如果答案存在且为c，请输出[c]

输入例子1:

2 misakamikotodaisuki
3 !bakabaka~ bakabaka~ 1~2~9!
3 3.1415926535897932384626433832795028841971693993751o582097494459211451488946419191919l91919hmmhmmahhhhhhhhhh
7 www.bilibili.com/av170001\
1 111

输出例子1:

[d]
[9]
[l]
[7]
Myon~

这个题有几种思路，最简单的还是使用映射(map)，让出现的每个字符对应到0上。扫描整个字符串，如果碰到一个字符，就让他对应的数+1，同时记录每个字符出现的顺序。然后扫描记录的顺序，找到第k个对应数是1的字符。但是我们看到题目说的是不超过ASCII，所以直接用ASCII来映射就好了，给出示例C++代码：

3.简单表达式计算 answer

时间限制：1秒
空间限制：32768K

给定一个合法的表达式字符串，其中只包含非负整数、加法、减法以及乘法符号（不会有括号），例如7+3*4*5+2+4-3-1，请写程序计算该表达式的结果并输出；

输入描述:

输入有多行，每行是一个表达式，输入以END作为结束

输出描述:

每行表达式的计算结果

输入例子1:

7+3*4*5+2+4-3-1
2-3*1
END

输出例子1:

69
-1

4.小A最多会新认识的多少人 answer

时间限制：1秒
空间限制：32768K

小A参加了一个n人的活动，每个人都有一个唯一编号i(i>=0 & i<n)，其中m对相互认识，在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后，小A最多会认识多少人？

输入描述:

第一行聚会的人数：n（n>=3 & n<10000）；
第二行小A的编号: ai（ai >= 0 & ai < n)；
第三互相认识的数目: m（m>=1 & m
< n(n-1)/2）；
第4到m+3行为互相认识的对，以’,’分割的编号。

输出描述:

输出小A最多会新认识的多少人？

输入例子1:

7
5
6
1,0
3,1
4,1
5,3
6,1
6,5

输出例子1:

3

这个题很明显的并查集，但是据其他人说用邻接表+BFS也能做，但是这里我就不尝试了，给出并查集（最后要记得减去小A本来就认识的人）的C++示例代码：

5.山寨金闪闪 answer

时间限制：3秒
空间限制：262144K

金闪闪死后，红A拿到了王之财宝，里面有n个武器，长度各不相同。红A发现，拿其中三件武器首尾相接，组成一个三角形，进行召唤仪式，就可以召唤出一个山寨金闪闪。（例如，三件武器长度为10、15、20，可以召唤成功。若长度为10、11、30，首尾相接无法组成三角形，召唤失败。）红A于是开了一个金闪闪专卖店。他把王之财宝排成一排，每个客人会随机抽取到一个区间[l,r],客人可以选取区间里的三件武器进行召唤（客人都很聪慧，如果能找出来合适的武器，一定不会放过）。召唤结束后，客人要把武器原样放回去。m个客人光顾以后，红A害怕过多的金闪闪愉悦太多男人，于是找到了你，希望你帮他统计出有多少山寨金闪闪被召唤出来。

输入描述:

第一行武器数量:n <= 1*10^7
第二行空格分隔的n个int，表示每件武器的长度。
第三行顾客数量：m <= 1*10^6
后面m行，每行两个int l，r，表示每个客人被分配到的区间。（l<r）

输出描述:

山寨金闪闪数量。

输入例子1:

5
1 10 100 95 101
4
1 3
2 4
2 5
3 5

输出例子1:

3

我知道这是《Fate》系列作品的衍生题目，我不玩游戏，但是咱也知道金闪闪是男的，为什么偷♂税男人啦。不过这个题很有说头，思路可以分为这几步：

1，首先，判断三个正整数a,b,c是否能组成三角形，判断方法是：将abc升序排列，然后如果a+b>c,则可以构成三角形。其次，判断一个区间[L,R]内是否能找到三个数使其构成三角形，可以将这R-L+1个元素取出并排序，然后从前往后三个三个判断。查询每次区间长度都在1~1e7之间，当然不能每次都暴力找，不然有1e6次查询，时间复杂度肯定爆炸，那么怎么处理呢？实际上，如果数一多，是非常容易构成三角形的，如果要刚好卡到边界，刚好不能构造成三角形（a+b==c），则要构造这样的数据：1，1，2，3，5，8……。
巧了，其实就是斐波那契数列，题目的数据给出的数据在int范围内，然后我们发现大概在40多项的时候就不能构造出全都不满足构成三角形的数据了，下面是打表的出的结果。

int 的范围最大是2的32次方，也就是4294967296，到48项就超了，所以区间超过47必出金闪闪

所以，只要在给出的区间长度较大的，一定能构成三角形，区间长度较小的，则可以存下来排序后判断，下面给出C++示例代码：

作者：高玩梁
https://www.bilibili.com/read/cv3831139
出处： bilibili

6.比较两个版本字符串version1和version2 answer

时间限制：1秒
空间限制：32768K

如果version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.

输入的version字符串非空，只包含数字和字符.。.字符不代表通常意义上的小数点，只是用来区分数字序列。例如字符串2.5并不代表二点五，只是代表版本是第一级版本号是2，第二级版本号是5.

输入描述:

两个字符串，用空格分割。
每个字符串为一个version字符串，非空，只包含数字和字符.

输出描述:

只能输出1, -1，或0

输入例子1:

0.1 1.1

输出例子1:

-1

7.精灵鼠从入口到出口的最少减少速度 answer

时间限制：2秒
空间限制：131072K

猛兽侠中精灵鼠在利剑飞船的追逐下逃到一个n*n的建筑群中，精灵鼠从（0,0）的位置进入建筑群，建筑群的出口位置为（n-1,n-1），建筑群的每个位置都有阻碍，每个位置上都会相当于给了精灵鼠一个固定值减速，因为精灵鼠正在逃命所以不能回头只能向前或者向下逃跑，现在问精灵鼠最少在减速多少的情况下逃出迷宫？

输入描述:

第一行迷宫的大小: n >=2 & n <= 10000；
第2到n+1行，每行输入为以’,’分割的该位置的减速,减速f >=1 & f < 10。

输出描述:

精灵鼠从入口到出口的最少减少速度？

输入例子1:

3
5,5,7
6,7,8
2,2,4

输出例子1:

19

8.顺时针打印数字矩阵 answer

时间限制：1秒
空间限制：32768K

给定一个数字矩阵，请设计一个算法从左上角开始顺时针打印矩阵元素

输入描述:

输入第一行是两个数字，分别代表行数M和列数N；接下来是M行，每行N个数字，表示这个矩阵的所有元素；当读到M=-1，N=-1时，输入终止。

输出描述:

请按逗号分割顺时针打印矩阵元素（注意最后一个元素末尾不要有逗号！例如输出“1，2，3”，而不是“1，2，
3，”），每个矩阵输出完成后记得换行

输入例子1:

3 3
1 2 3
4 5 6
7 8 9
-1 -1

输出例子1:

1,2,3,6,9,8,7,4,5

9.写一段程序判断IP字符串是否属于内网IP answer

时间限制：1秒
空间限制：32768K

从业 666 年的 BILIBILI 网络安全工程师 KindMo 最近很困惑，公司有一个业务总是受到 SSRF 攻击。请帮他写一个程序，判断输入的字符串是否属于内网IP，用于防御该漏洞。
我们知道常见的内网IP有，127.0.0.1，192.168.0.1 等。

输入描述:

每次输入仅包含一个IP字符串，即一个测试样例

输出描述:

对于每个测试实例输出整数1或0，1代表True，即输入属于内网IP，0代表False，即输入不属于内网IP或不是IP字符串。

输入例子1:

42.96.146.169

输出例子1:

0

10.给定一个整数数组,判断其中是否有3个数和为N answer

时间限制：1秒
空间限制：131072K

给定一个整数数组,判断其中是否有3个数和为N

输入描述:

输入为一行
逗号前为一个整数数组，每个元素间用空格隔开；逗号后为N

输出描述:

输出bool值
True表示存在3个和为N的数
False表示不存在3个和为N的数\

输入例子1:

1 2 3 4 5,10

输出例子1:

True

11.实现一个HTML语法检查器 answer

时间限制：1秒
空间限制：32768K

实现一个HTML语法检查器。HTML语法规则简化如下：标签必须闭合，可以由开始和结束两个标签闭合，如<div></div>，也可以自闭合，
如<div />
标签可以嵌套如<div><a></a></div>或者 <div><a/></div>，但是标签不能交叉：<div><a></div></a>是不允许的标签里可以有属性
如<div id="a<1"></div>
属性的规则是name=”任意非引号字符”，多属性声明之间必须有空格，属性声明不符合规则时，整段HTML都算语法错误
输入文本只会出现字母a-z和<>”=
请用任意语言实现一个HTML语法检查器函数，有语法错误返回1，没有语法错误返回0

输入描述:

一行，一个HTML字符串

输出描述:

有语法错误返回1，没有语法错误返回0

12.孙悟空的徒弟 answer

时间限制：3秒
空间限制：131072K

打败魔人布欧以后，孙悟空收了n个徒弟，每个徒弟战斗力各不相同。他教导所有的徒弟和体术，合体后战斗力为原战斗力相乘。任何两个徒弟都可以合体，所以一共有n*(n-1)/2种合体徒弟。有一天，他想考验一下孙悟天战斗力如何，希望在所有n*(n-1)/2种合体徒弟中选择战斗力第k高的，与孙悟天对战。可是孙悟空徒弟太多了，他已然懵逼，于是找到了你，请你帮他找到对的人。

输入描述:

第一行两个int。徒弟数量：n <= 1*10^6；战斗力排名:k <= n*(n-1)/2
第二行空格分隔n个int，表示每个徒弟的战斗力。

输出描述:

战斗力排名k的合体徒弟战斗力。

输入例子1:

5 2
1 3 4 5 9

输出例子1:

36

13.翻转链表 answer

时间限制：1秒
空间限制：32768K

对于一个链表 L: L0→L1→…→Ln-1→Ln,
将其翻转成 L0→Ln→L1→Ln-1→L2→Ln-2→…

输入是一串数字，请将其转换成单链表格式之后，再进行操作

输入描述:

一串数字，用逗号分隔

输出描述:

一串数字，用逗号分隔

输入例子1:

1,2,3,4,5

输出例子1:

1,5,2,4,3

14.ん…红茶？answer

时间限制：1秒
空间限制：131072K

高贵的蕾米莉亚大小姐每天需要饮用定量 B 型血的红茶以保持威严，并且要分两杯在不同时段饮用。
女仆长十六夜咲夜每天可以制作很多杯不同剂量 B 型血的红茶供蕾米莉亚大小姐饮用。
某日，你和天才妖精琪露诺偷偷潜入红魔馆被咲夜抓住，要求在今日份的红茶中挑出所有满足大小姐要求的茶杯，否则……

输入描述:

每个样例有三行输入，第一行输入表示茶杯个数，第二行输入表示每份茶杯里的 B 型血剂量，第三行表示大小姐今天的定量

输出描述:

对每一个样例，输出所有可能的搭配方案，如果有多种方案，请按每个方案的第一杯 B 型血剂量的大小升序排列。
如果无法找到任何一种满足大小姐的方案，输出”NO”(不包括引号)并换行。

输入例子1:

7
2 4 6 1 3 5 7
7

输出例子1:

1 6
2 5
3 4