#牛客堂直播视频#美团16笔试真题精讲（9.23）

牛课堂全新升级啦，本期开始将更加抓住热点，大家想听什么，我们就讲什么！本期就以刚刚出炉的美团笔试真题作为开始！

如果你对牛课堂的讲解范围有任何建议欢迎邮件yinglun.zhu@nowcoder.com

【本期题目】

题目一

给定一个数组arr，数组长度为len。求满足0<=a<=b<len的arr[b]-arr[a]最大值。

参数

arr：整型数组

len：数组长度，整型

返回值

最大差值：整型

示例参数

arr：[10，5]

len：2

示例返回值

题目二

给定一个字符串 str,返回 str 的最长无重复字符子串的长度。，举例，str="abcd"，返回 4。str="aabcb"，最长无重复字符子串为"abc",返回 3。

题目三

一个 char 类型的数组 chs,其中所有的字符都不同。

例如,chs=['A', 'B', 'C', ... 'Z'],则字符串与整数的对应关系如下:

A, B... Z, AA,AB...AZ,BA,BB...ZZ,AAA... ZZZ, AAAA...

1, 2...26,27, 28... 52,53,54...702,703...18278, 18279...

例如,chs=['A', 'B', 'C'],则字符串与整数的对应关系如下: A,B,C,AA,AB...CC,AAA...CCC,AAAA...

1, 2,3, 4, 5 ...12, 13 ... 39, 40...

给定一个数组 chs,实现根据对应关系完成字符串与整数相互转换的两个函数

题目四

已知某公司总人数为W，平均年龄为Y岁（每年3月末计算，同时每年3月初入职新员工），假设每年理智率为X，X>0&&X<1，每年保持所有员工总数不变进行招聘，招聘的新员工平均年龄为21岁。

以今年3月末未开始，请实现一个函数 avgage（Y,X,N），可以计算出第N年后公司员工的平均年龄(结果上请去整)。

题目五

最后一个字符

正在挑战一个CrackMe的你，把需要填写的前面几位密码都正确猜出了，可是这最后一位密码，好像藏得有点深。CrackMe的作者还挑衅般的在里面藏了一个.tar.pz文件，解压缩出来，里面写道，

你要的最后一个字符就在下面这个字符串里。这个字符是下面整个字符串中第一个只出现一个的字符。

（比如，串是abaccdeff，那么正确的字符就是b了）

然而下面给出来的字符串好像太长太长了，单靠人力完全无法找出来。于是，你需要写一个程序代劳了。

输入文件体积较大，请使用一些快速的输入输出手段，不推荐使用cin/cout，对Java并不推荐使用Scanner直接读写。

输入

第一行，一个正整数T(T<=20)，表示输入数据组数。

之后T行，每一行一个字符串S。（1<=S的长度<=，保证字符串中出现的字符的ASCII码在[0x21，0x7F）范围内，即均可显示的空白字符，同时保证一定有解）

输出

一共T行，每一行一个字符C，表示所给的相应字符串中第一个只出现一次的字符。

样例输入

abaccdeff

testtonline

样例输出

题目六

360员工桂最近申请了一个长假，一个人背着包出去自助游了。路上，他经过了一个小镇，发现小镇的人们都围在一棵树下争吵。桂上前询问情况，得知小镇的人们正缺一个镇长，他们希望能选一个知名又公正的镇长，即，大家希望能选出一个人，所有人都认识他，但同时他不认识镇上除自己以外的其他人（在此，我们默认每个人自己认识自己）。可是小镇里的人太多了，一下子大家谁也说服不了谁。 　　“这简单啊。”桂表示。于是他一下子统计出来了镇上人们相互之间的认识关系，并且一下子找到了合适的镇长人选。 　　现在你手上也拿到了这样一份认识关系的清单。其中上面给出的认识关系是单向的，即，A认识B与B认识A是相互独立的，只给出A认识B就不能认为B认识A，例如，我认识你，你不一定认识我。而且，这里的认识关系也不具有传递性，即，A认识B，B认识C，但这不代表A认识C。同时，为了方便处理，这份清单中，镇上的N个人依次编号为1到N。你能否像桂一样快速找到合适的镇长人选呢？

输入描述:

首先一个正整数T（T≤20），表示数据组数。

之后每组数据的第一行有2个整数n 和m (1≤n≤105 ,0≤m≤3×105 )，依次表示镇上的人数和相互之间的认识关系数。

之后m行，第 i 行每行两个数Ai和Bi (1≤Ai ,Bi ≤n )，表示Ai认识Bi。（保证没有重复的认识关系，但可能存在自己认识自己的认识关系）

保证所有数据中80%的数据满足n≤1000,m≤10000

输出描述:

一共2T 行，每组数据对应2行。

第一行，一个整数，表示你所找出来的合适的镇长人选人数num i 。

第二行，num i 个整数，每两个数中间用空格隔开，表示你所选的合适的镇长的编号。

特别的，如果并没有找到合适的镇长，第一行输出一个数0，第二行留空即可（参见样例）。

输入例子:

2 0