阿里云春招实习笔试题解(0421)

type

status

date

slug

summary

📝 主旨内容

满足权值串的最小长度(双指针)

小红定义一个字符串权值为:相邻字母相等的对儿数。例如，aaabbc 的权值是3。现在小红拿到了一个字符串，她想取一个连续子串满足权值恰好等于k。小红希望你帮她求出子串长度的最小值。你能帮帮她吗?

输入描述

第一行输入两个正整数nk，代表小红拿到的字符串长度、取的连续子串的权值。

第二行输入一个长度为n的、仅由小写字母组成的字符串1≤k<n≤300000)

输出描述

如果不存在一个合法的子串满足条件，请输出-1，否则输出一个正整数，代表连续了串的最小长度。

示例：

输入：

输出：

💡

双指针模板题，需要注意权值要恰好为k

构造两个排列(思维)

小红拿到了一个长度为n的数组a，她希望你构造两个长度为n的排列p和q，满足以下条件:

你能帮帮她吗?

所谓排列，指一个长度为n的数组，其中1到n每个元素恰好出现1次。

输入描述

第一行输入一个正整数n，代表小红拿到的数组大小。第二行输入n个整数，代表小红拿到的数组。1≤n≤10^5,0≤ai≤n-1

输出描述

如果无解，请输出-1。否则第一行输出n个正整数，第二行输出n个正整数，代表小红构造的两个排列。有多解时输出任意即可。

示例：

输入：

输出：

💡

对于,这样的和是确定的，所以可以提前把的值处理出来，保存到b数组中，如果输入的a数组和b数组排序后不相同，则无解。可以用map存储每个对应的和。

联通块大小相同的最少操作次数(并查集,数学)

小红拿到了一个森林(即若干棵树组成的无向图)。她可以进行若干次以下操作:

新增一个节点，连接在任意节点上。

选择一个叶子，删除对应的节点和边。

小红希望最终森林的每个连通块的大小都相同，请你帮小红求出最少的操作次数。

输入描述

第一行输入两个正整数n，m，代表森林的点数和边数。接下来的m行，每行输入两个正整数uv，代表u号节点和u号节点有一条边连接。

1≤m<n≤10^5, 1≤u,v≤n

保证给定的无向图是一个森林。

输出描述

一个整数，代表小红最小的操作次数。

示例：

输入：

输出：

说明：操作2次，分别将一个节点连接在4号上面，这样两个连通块的大小均为3。

💡

通过并查集求解联通块问题并计数，问题就变成了：给定一个数组，可以对数组内的数加一或减一，使得数组每个数都相等的最小操作次数

💡

首先对数组排序，不难证明最后的数一定出现在原数组，枚举数组中的每个数，通过前缀和计算出全部数字变成当前数的代价，取最小值

🤗 总结归纳

第一道模板题，第二题需要仔细分析，第三题是两个问题的组合

📝 主旨内容

满足权值串的最小长度(双指针)

输入描述

输出描述

示例：

构造两个排列(思维)

输入描述

输出描述

示例：

联通块大小相同的最少操作次数(并查集,数学)

输入描述

输出描述

示例：

🤗 总结归纳

📎 参考文章