题型及时间

90分钟

单选10 + 算法3

单选包括Java基础八股文、设计模式、计算机网络、sql语句

算法

1

题目描述

小美准备登录美团，需要输入密码，小美忘记了密码,只记得密码可能是n 个字符串中的一个。小美会按照密码的长度从小到大依次尝试每个字符串，对于相同长度的字符串，小美随机尝试，并且相同的密码只会尝试一次。小美想知道，她最少需要尝试多少次才能登录成功，最多需要尝试多少次才能登录成功。小美不会重新尝试已经尝试过的字符串。成功登录后会立即停止尝试。

输入描述

第一行输入一个整数 n(1< n < 1000)代表密码字符串的个数。

第二行输入一个只由小写字母组成的字符串s(1 <|s| <1000)代表正确的密码。

接下来 n行，每行输入一个长度不超过 1000.的字符串,代表小美记得的密码。

输出描述

在一行上输出两个整数，表示最少和最多尝试次数。

输入示例

4

ab

abc

ab

ac

ac

输出示例

1 2

说明

小美可能按照[“ab”“ac”"abc” 的顺序尝试，第一次尝试成功，也可能按照[“ac”,“ab”,“abc] 的顺序尝试，第二次尝试成功。小美在尝试"ac"发现不正确后不会继续尝试"ac”。

参考答案

<code>n = int(input())

s = input()

mem =[]

a，b=0，0

for _ in range(n):

ts = input()

if ts in mem:

continue

mem.append(ts)

if len(ts) < len(s) or ts == s:

a += 1

elif len(ts) == len(s):

b += 1

print(a, a+b)

2

题目描述

小美有一个长度为九 的数组 ai,a2,…,an，他可以对数组进行如下操作:

删除第一个元素 a1，同时数组的长度减一，花费为 x。

删除整个数组，花费为k x MEX(a) (其中MEX(a)表示a 中未出现过的最小非负整数。

例如[0,1,2,4]的MEX为3)。

小美想知道将a 数组全部清空的最小代价是多少，请你帮帮他吧。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T(1< T < 1000)代表数据组数，每组测试数据描述如下:

第一行输入三个正整数n,k,x (1 <n <2 x 10^5, 1< k,x < 10 ^9)代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。第二行输入n 个整数 a1,a2,…,an (0 < ai ≤ n)，表示数组元素。

除此之外，保证所有的n 之和不超过 2 x 10^5。

输出描述

对于每一组测试数据，在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。

输入示例

1

6 3 3

4 5 2 3 1 0

输出示例

15

说明

若不执行操作一就全部删除，

MEX{4,5,2,3,1,0}=6，花费 18;

若执行-次操作一后全部删除，

MEX{5,2,3,1,0}=4，花费3+12;

若执行两次操作一后全部删除，MEX{2,3,1,0]=4,花费6+12;

若执行三次操作一后全部删除，MEX{3,1,0}= 2,花费9+6;

若执行四次操作一后全部删除，MEX{1,0}= 2，花费 12+6;

若执行五次操作一后全部删除，MEX{0}= 1，花费15+3;

若执行六次操作一，MEX= 0，花费18;

参考答案

def min_cost_to_clear(n, k, x, arr):

dp = [0] * (n + 1)

dp[n] = x * n

mex = 0

res = float('inf')

p = 0

record = { }

for i in range(n - 1, -1, -1):

p += 1

while arr[i] == mex or mex in record:

mex += 1

record[arr[i]] = 1

dp[i] = x * (n - p) + mex * k

if dp[i] < res:

res = dp[i]

return res

T = int(input())

results = []

for _ in range(T):

n, k, x = map(int, input().split())

arr = list(map(int, input().split()))

result = min_cost_to_clear(n, k, x, arr)

results.append(result)

for res in results:

print(res)

3

题目描述

小美的彩带是由一条长度为 九 的彩带一直无限循环得到的,彩带的每一个位置都有一个颜色，用ai表示。因此当i>n时,ai=ai-n。小美每次会从左往后或从右往左剪一段长度为 2 的彩带，她想知道她每次剪下来的彩带有多少种颜色。

输入描述

第一行输入两个整数n,q(1 ≤n,q<2x 105)代表彩带长度、剪彩带次数。

第二行输入n 个整数al,a2,…,an (1 ≤ ai ≤ 10°)代表彩带每一个位置的颜色。

此后 q 行，每行输入一个字符 c和一个整数x(1 <x < 10°;c E’L’,"R)代表裁剪方向和裁剪长度,其中工"说明从左往右剪，"R 说明从右往左剪。

输出描述

对于每一次裁剪彩带，在一行上输出一个整数代表颜色数量。

输入示例

6 3

1 1 4 5 1 4

L 2

L 3

R 12

输出示例

1

3

3

说明

第一次剪彩带，剪下来的是[1,1]，有《1]这1种颜色，

第二次剪彩带，剪下来的是 [4,5,1]，有

{1,4,5}这3种颜色;第三次剪彩带，剪下来的是[1,1,4,5,1,4,1,1,4,5,1,4，有{1,4,5}这3种颜色。

参考答案

n, q = map(int, input().split())

arr = list(map(int, input().split()))

l, r = 0, len(arr) - 1

for _ in range(q):

c, x = tuple(input().split())

x = int(x)

if c == 'L':

tl, tr = l, l + x - 1

l = l + x

else:

tl, tr = l - x + 1, r

r = l - x

tset = set()

for idx in range(tl, tr + 1):

tset.add(arr[idx])

print(len(tset))