美团算法题真题（去年秋招的，可以参考一下）

前言：

据我了解，美团笔试的算法题是比较简单的，大家要查漏补缺，尽量全部做出来，不然可能很难拿到面试（如果题目简单的话）。

我的其它帖子还有不少题目，可以看看。

如果对你有帮助，请点赞收藏，助我早日成为红名大佬

小美买零食

时间限制: 2000**/1000** MS (Java/Others)

内存限制: 524288**/524288** K (Java/Others)

问题描述

到周末了，小美为了犒劳辛苦了一周得自己，打算去超市买点自己喜欢的零食吃。由于各个超市的备货情况不同，小美可能需要多走几个超市才能买完自己想要的零食。

小美有 种心仪的零食，小区附近有 家超市，第家超市售卖 种零食，分别为第 种，小美想要知道至少要需要访问几家超市，才能买齐这 种零食？

输入描述

第一行，两个正整数 。

接下来 行，第 行第一个正整数为 ，接下来 个正整数 。

输出描述

仅一行，一个正整数，表示至少要访问几家超市，如果所有超市都缺少某种零食，输出 -1。

输入样例

5 4

1 2

3 1 3 5

2 2 4

1 4

输出样例

2

---------------------

字符串解压

时间限制: 2**000/1000** MS (Java/Others)

内存限制: 524288**/524288** K (Java/Others)

问题描述

给出一个仅包含小写字母和‘-’的字符串，按如下规则输出解压后的字符串。

\1. 如果‘-’连接了多个相同的字符，则只输出第一个字符，‘-’和之后的相同字符不输出。例如‘a-a-a’替换为‘a’，‘a-aa-a’替换为‘aa’。

\2. 如果‘-’连接了两个不同的字符，则将连接符及其前后的字符替换为递增或递减的字符串。例如‘a-c’替换为‘abc’，‘g-c’替换为‘gfedc’，‘a-e-c’替换为‘abcdedc’。

\3. 其他字符原样输出。

输入描述

仅一行，表示输入的字符串，字符串长度不超过 ，保证开头和结尾是小写字母，保证不出现两个相连的‘-’。

输出描述

仅一行，代表解压后的字符串

输入样例

a-fzs-o-o-q

输出样例

abcdefzsrqpopq

------------------

小美的字符串

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

小美有一个字符串，她想把这个字符串变成一个“三重串”。一个长度为n的字符串s[1…n]是一个“三重串”当且仅当：（1）n为3的倍数；（2）对于所有的0<=i<n/3满足s[3i+1] = s[3i+2] = s[3*i+3]。例如，”aaabbb”、”bbbcccbbb”、”zzzaaaaaa”都是“三重串”，而”aaz”、”aaabb”、”aaabbccdd”都不是“三重串”。特别地，空串也为“三重串”。

小美可以删除当前字符串中的一些字符，使剩下的字符不改变相对顺序形成一个新的字符串。例如，对于串”aaabbca”，若删除第三个字符’a’，则形成的新字符串为”aabbca”。

小美想知道对于自己的字符串，最少删除多少个字符，可以使新形成的字符串是一个“三重串”？

输入描述

一个字符串s，表示小美的字符串。

输出描述

一个数字，表示问题描述中所描述的最少需要删除的字符数。

输入样例**1**

abaabbccdca

输出样例**1**

5

样例解释1

新字符串可以为”aaaccc”或”bbbccc”，这样需要删除5个字符，可以证明没有更优的删除方式。

数据范围和说明

30%的数据保证：1<=|s|<=100

80%的数据保证：1<=|s|<=1000

100%的数据保证 ：1<=|s|<=100000

-----------------------

小美的礼盒包装

时间限制: 2000/1000 MS (Java/Others)

内存限制: 524288/524288 K (Java/Others)

问题描述

小美开的西点屋举办一周年活动，她准备制作一批礼盒作为对消费者的回馈，每个礼盒中都有三枚西点屋的招牌点心。西点屋共有A和B两种招牌点心，为了让消费者都能品尝到两种点心，因此每个礼盒中都要包含至少一枚A点心和一枚B点心。现在小美的西点屋内共有x枚A点心和y枚B点心，请问小美最多可以制作多少个礼盒。

输入描述

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

然后有T行，每行包含两个整数x和y，表示有x枚A点心和y枚B点心。(1<=x,y<=10^9)

输出描述

输出包含T行，每行一个整数，表示最多可以制作的礼盒数量。

输入样例

2

44 85

9 49

输出样例

43

9

---------------------------

小团的栈

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

小团有一个栈，初始时为空，然后小团会对这个栈进行若干次操作，每次操作是如下三种指令之一：

l -1: 表示将栈顶元素弹出。

l 0: 表示将栈中元素重排，使元素从栈顶到栈底按从小到大的顺序排列。

l x: 将元素x(x>0且为整数)入栈。

现在给你小团的所有操作，请你在每次进行出栈操作(指令为-1)时输出出栈的元素。

输入描述

第一行是一个正整数n，表示小团会进行的操作次数。

接下来一行n个整数，第i个整数ai(-1<=ai<=10^6)表示第i次操作所对应的指令（与问题描述中相同，若为-1则表示出栈，0则表示对栈中元素排序，若为大于0的整数则将该数入栈），保证在进行出栈操作时栈不为空。

输出描述

对于每一个出栈操作，输出出栈的元素，输出时相邻两个出栈元素用空格隔开。

输入样例**1**

10

3 1 2 4 -1 0 -1 -1 1 -1

输出样例**1**

4 1 2 1

样例**解释1**

每次操作完栈中情况如下（最左边为栈底，最右边为栈顶）：

[3]->[3, 1]->[3, 1, 2]->[3, 1, 2, 4]->[3, 1, 2]->[3, 2, 1]->[3, 2]->[3]->[3, 1]->[3]

数据范围和说明

30%的数据保证：1<=n<=100

80%的数据保证：1<=n<=5000

100%的数据保证 ：1<=n<=200000

-------------------------

数据拆分

时间限制: 2000/1000 MS (Java/Others)

内存限制: 524288/524288 K (Java/Others)

问题描述

小美非常热衷于数据竞赛，数据竞赛是当下非常流行的一种比赛形式，在这种比赛中往往会给出一个训练集和一个测试集，由于测试集是没有标注的，因此大家为了线下评测模型的性能，通常会将测试集拆分成两个部分，即自建的训练集和测试集。

现在给出某比赛的一个训练集，小美需要按照如下规则将其拆分为训练集和测试集。

已知该训练集包含n个样本，每个样本有一个样本编号和一个类别编号。假设某一类别的样本共有m个，则将编号最小的m/2(向上取整)个样本作为训练集，将其他样本作为测试集。

输入描述

输入第一行包含两个正整数n和k，分别表示样本数量和类别数量。(1<=n<=10000,1<=k<=100)

输入第二行包含n个正整数，第i个正整数j表示第i个样本的类别编号是j。

输出描述

输出包含两行，第一行是训练集样本编号，编号从小到大输出，中间用空格隔开。第二行是测试集的样本编号，编号从小到大输出，中间用空格隔开。

输入样例

10 3

3 2 2 1 2 3 1 3 3 3

输出样例

1 2 3 4 6 8

5 7 9 10

-----------------------------

小美的魔法石共鸣

时间限制: 2000/1000 MS (Java/Others)

内存限制: 524288/524288 K (Java/Others)

问题描述

​ 小美有n块魔法石，每块魔法石都有正反两面，每一面上都刻有一个魔法阵，初始状态下，n块魔法石都是正面向上。这n块魔法石的能量刚好可以构建一个大型魔法阵，但是需要至少一半的魔法石向上的一面铭刻的阵法相同才能触发大型魔法阵的效果。

​ 小美希望翻转最少数量的魔法石，使得这个大型魔法阵被触发，请问她最少需要翻转多少块魔法石。

输入描述

输入第一行包含一个正整数n，表示魔法石的数量。(1<=n<=100000)

​ 输入第二行包含n个正整数，表示n块魔法石正面铭刻的魔法阵种类，由于魔法书上记载的魔法阵数量太多，所以魔法阵编号可能是从1到10^9中的任何一个正整数。

​ 输入第三行包含n个正整数，表示n块魔法石反面铭刻的魔法阵种类，魔法阵编号同样在1-10^9之间。

输出描述

输出仅包含一个整数，如果有解则输出最少翻转的魔法石数量，如果无解则输出-1。

输入样例

5

1 5 7 5 5

10 5 5 9 10

输出样例

0

----------------------------------

游戏

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

某天，小美在玩一款游戏，游戏开始时，有n台机器，每台机器都有一个能量水平，分别为a1、a2、…、an，小美每次操作可以选其中的一台机器，假设选的是第i台，那小美可以将其变成 ai+10k（k为正整数且0≤k≤9），由于能量过高会有安全隐患，所以机器会在小美每次操作后会自动释放过高的能量，即变成 (ai+10k)%m，其中%m表示对m取模，由于小美还有工作没有完成，所以她想请你帮她计算一下，对于每台机器，将其调节至能量水平为0至少需要多少次操作（机器自动释放能量不计入小美的操作次数）。

输入描述

第一行两个正整数n和m，表示数字个数和取模数值。

第二行为n个正整数a1, a2,...... an，其中ai表示第i台机器初始的能量水平。

输出描述

输出一行共n个整数，其中第i个表示将第i台机器能量水平调节至0需要的最少操作次数。

输入样例1

4 4

0 1 2 3

输出样例1

0 2 1 1

数据范围和说明

对于80%的数据，1 ≤ n ≤ 500，2 ≤ m ≤ 500。

对于100%的数据，1 ≤ n ≤ 30000，2 ≤ m ≤ 30000, 0 ≤ ai < m。

样例说明

0无需操作即为0。

1通过+1+10两次操作可以变为0，变化过程为1->(1+1)%4->(2+10)%4=0。

2通过+10一次操作可以变为0，变化过程为2->(2+10)%4=0。

3通过+1一次操作可以变为0，变化过程为3->(3+1)%4=0。

还可以+100、+1000等操作，但在样例情况下不是最优操作。

------------------------------

小美玩游戏

时间限制: 2000/1000 MS (Java/Others)

内存限制: 524288/524288 K (Java/Others)

问题描述

小美最近在玩一款回合制游戏，该游戏中的一个人机关卡共有n个回合，小美所使用的角色并没有主动攻击技能，有且只有一个防御技能——圣光!圣光总共可以使用k次，每回合最多使用一次，如果在某一个回合使用了圣光，那么小美的角色会免疫该回合受到的所有伤害，并且在之后没有释放圣光的回合中每回合恢复1点HP，效果可以叠加，例如在前两个回合都释放了一次圣光，那么第三个回合就会恢复2点HP。

小美只需要在n个回合后HP大于等于0，即可通关，请问小美角色初始最少需要多少HP。（初始HP应该大于等于1，游戏过程中允许部分时刻HP小于0）

输入描述

输入第一行包含两个整数n和k，分别表示回合数和圣光使用次数。(1<=n,k<=10000)

输入第二行包含n个整数，分别表示在第1个回合到第n个回合中，npc对角色造成的伤害，每回合造成的伤害不超过10000。

输出描述

输出仅包含一个整数，即最少需要的HP数。

输入样例

5 2

7 3 2 6 4

输出样例

5

-------------------------------------

小团的机器人

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

小团拥有了一个能在魔法地图上行走的机器人。魔法地图是一个n行m列的网格图，并且每个格子都是白色的或黑色的。当机器人站在网格图上的某一个格子时，它只能走到相邻的颜色与当前格子不同的格子上。当机器人站在第x行第y列的格子时（记作(x,y)），与该格子相邻的格子有：

l 左边的格子(x, y-1)

l 右边的格子(x, y+1)

l 上方的格子(x-1, y)

l 下方的格子(x+1, y)

机器人会进行自动寻路，具体地：如果机器人站在 (x, y)上，那么它会按照下、右、左、上的顺序搜索可走的格子，按这四个方向中第一个可走的方向行走。当机器人走向下一个格子时，上一个格子的颜色将立即发生变化。例如：若当前站在(x, y)，格子颜色为黑色，走向了颜色为白色的(x, y+1)，那么当机器人走到(x, y+1)时，(x, y)的颜色将立即变为白色。当四个方向都无法行走时，机器人将停下来。注意，机器人只会在地图内部行走，不会走到地图外。

小团想知道，如果机器人从某一个位置(x, y)开始自动寻路，行走k步以后，它所在的位置是哪里？如果机器人还未走到k步就停下来了，那么输出停下来时所在的位置即可。

输入描述

第一行是两个正整数n、m，分别表示魔法地图有n行m列。

接下来n行，每行一个长度为m的字符串，字符串只包含字符’0’和’1’。第i行第j个位置为’0’表示魔法地图的第i行第j列的格子为白色，为’1’则表示为黑色。

接下来一行一个正整数T，表示小团会问T个问题。

接下来T行，每行三个正整数x, y, k，表示小团询问机器人从第x行第y列开始行走k步后的位置。保证1<=x<=n且1<=y<=m。

*注意询问之间相互独立，之前的询问对后续的询问不造成影响。**换句话说你需要在行走之后恢复魔法地图原本的格子状态。***

输出描述

T行，每行两个空格隔开的正整数a b，表示对应输入中的每个问题的答案。

输入样例**1**

3 3

010

110

100

2

1 1 2

3 1 4

输出样例**1**

2 1

2 3

样例**解释1**

从(1, 1)出发，只能向下走一步到(2, 1)，然后停止。注意，虽然向下和向右都是不同颜色，但按照下、右、左、上的顺序搜寻，首先会搜寻到向下的格子并走过去。

从(3, 1)出发，走4步的路径为(3, 1)->(3, 2)->(2, 2)->(2, 3)

数据范围和说明

30%的数据保证：1<=n,m<=20, T=1, 1<=k<=100

80%的数据保证：1<=n,m<=100, 1<=T<=10, 1<=k<=100

100%的数据保证 ：1<=n,m<=400, 1<=T<=10, 1<=k<=100

---------------

小美的实验结果

时间限制: 2000/1000 MS (Java/Others)

内存限制: 524288/524288 K (Java/Others)

问题描述

小美在做一个实验，这个实验会在纸带上打印出若干个数字，已知该实验所呈现出的正确结果应该是存在某一个分割处k，在k之前打印出的数字都是小于0的，而在k之后的数字应该都是大于0的，那么在k之前如果某一个数据大于等于0，那么我们认为这个数据是异常的，同理，在k之后如果某一个数据小于等于0，那么我们也认为这个数据是异常的。

现在给出小美打印的纸带，且k是未知的，那么请问在最乐观的情况下至少有多少个实验数据是异常的。(显然如果出现0，无论k为哪个时刻，这个0数据都是异常的)

输入描述

输入第一行包含一个正整数n，表示小美在纸带上打印的数字数量。(1<=n<=100000)

输入第二行包含n个整数 ，即小美在纸带上打印的数字，中间用空格隔开。数字仅会为

-1，0，1中的一个。

输出描述

输出仅包含一个整数，表示至少有多少个实验数据是异常的。

输入样例

5

0 -1 1 1 -1

输出样例

2

样例解释

在最乐观的情况下，k应该在第二个和第三个数字之间，此时第一个和最后一个数据是异常的。

---------------------------

字母树

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

给定一棵有n个节点的树，节点用1,2, …, n编号。1号节点为树的根节点，每个节点上有一个用大写字母表示的标记。求每个节点的子树中出现的字母标记种类数。

注：子树的定义：设T是有根树，a是T中的一个顶点，由a以及a的所有后裔（后代）导出的子图称为有根树T的子树。

输入描述

第一行输入一个正整数n, 表示树的节点数量。

第二行输入n - 1个正整数，第i个整数表示第i+1号节点的父亲节点。

第三行输入长度为n的由大写字母组成的字符串s1s2…sn，第i个字符si表示第i号节点的标记。

输出描述

输出n个整数，相邻两个数之间用空格隔开，第i个整数表示第i号节点的子树中出现不同的字母种类数。

输入样例1

6

1 2 2 1 4

ABCCAD

输出样例1

4 3 1 2 1 1

数据范围和说明

对于80%的数据，3 ≤ n ≤ 100

对于100%的数据，3 ≤ n ≤ 50000。

数据保证形成一棵合法的树，字符串由大写字母组成。

样例说明

1号节点的子树有节点{1,2,3,4,5,6}，出现了A, B, C, D四种字母。

2号节点的子树有节点{2,3,4,6}，出现了B, C, D三种字母。

3号节点的子树有节点{3}，出现了C一种字母。

4号节点的子树有节点{4, 6}， 出现了C，D两种字母。

5号节点的子树有节点{5}，出现了A一种字母。

6号节点的子树有节点{6}，出现了D一种字母。

---------------------------