字节2021春招客户端开发笔试

A

题意：输入一个数组，输出一个相同长度的数组，每个相同位置的元素对应了输入数组的后一个比自己大的元素与当前位置的间隔，若没有比自己大的数，输出-1 Input：

5  [3, 1, 2, 4, 5]

Output：

[3, 1, 1, 1, -1]

解题结果：AC，leetcode基本原题

https://leetcode-cn.com/problems/next-greater-element-ii/

B

题意：输入n个人的身高，这n个人围着站成一圈，输出在它所有可能的排序中，最大身高差的最小值

Input：

4 100 150 200 250

Output：

100

Hint：

最后的可能排序为100 150 250 200

解题结果：AC

原理：与当前元素最近的元素的距离是最小的，与当前元素次近的元素的距离是永远可以被满足的，所以我们取整个数组的所有元素与其次近的元素的距离（有两个，前后次近距离中取小）的最大值

排序后，记录整个数组中当前元素与前第二个元素和后第二个元素的差的最小值的最大值。

特例：n==3时直接输出最大值而不取最小值

C

题意：输入M条指令，指令形式为"op x y"，

• 当op == 1，说明我们希望将号码为x和号码为y的书放在同一个书架上

• 当op == 2，说明我们不希望将号码为x和号码为y的书放在同一个书架上

求在所有op==1的指令满足之后，op==2的指令有多少个不能被满足？

Input：

4 1 1 2 2 1 3 1 2 3 2 1 4

Output：

1

解题结果：AC

经典并查集，但是题目规定书号码x, y <= 1e9，所以不能直接建数组，而是使用哈希表

D

题意：输入少于24000个长度小于16的字符串，我们定义两个字符串s1和s2是相似的，如果它满足：

• s2字符串可以由s1字符串增加、删除、更改一个字符得到

求满足相似的字符串的最长子序列的长度

Input：

cat  dig dog fig fin fine  fog wine

Output：

5

解题结果：约等于15%，不记得了

不会，直接遍历了一遍，求子串（子串和子序列不一样）的最长长度，可能是用dp，没想到状态转移方程

直接print 1能得到30%

欢迎大神指导