米哈游笔试 米哈游秋招 米哈游笔试题 1026
笔试时间：2025年10月26日
往年笔试合集：
第一题
给定一个长度为 n 的字符串 s，字符串仅由小写字母组成，下标从 1 开始。你可以对字符串执行以下操作任意次：
- 选择一个下标 i，将 s 的第 i 个字符 s_i 修改为任意小写字母。
请问最少需要多少次操作，才能让字符串中出现子串 "abcdefghijklmnopqrstuvwxyz"。
名词解释：
- 子串：子串为从原字符串中连续地选择一段字符（可以全选、可以不选）得到的新字符串。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T (1 ≤ T ≤ 10^4)，代表数据组数。
此后对于每组测试数据：
- 第一行输入一个整数 n (1 ≤ n ≤ 2 × 10^5)，表示字符串长度。
- 第二行输入一个长度为 n、仅由小写字母构成的字符串 s。
除此之外，保证所有测试数据中 n 的总和不超过 2 × 10^5。
输出描述
对于每组测试数据，新起一行，输出一个整数，代表最少的操作次数。
如果不存在使字符串中出现完整英文小写字母序列的方案，则输出 -1。
样例输入
3
37
abcdefghijklmnopqrstuvwxyzzzzzzzzzzzz
26
bcdefghijklmnopqrstuvwxyza
25
abcdefghijklmnopqrstuvwxy
样例输出
0
26
-1
参考题解
这道题使用滑动窗口技术来解决。由于目标子串长度固定为 26，我们可以：
- 遍历字符串 s 中所有可能的长度为 26 的连续子串（如果 n < 26，直接返回 -1）
- 对于每个窗口，计算将它变成目标字母表 "abcdefghijklmnopqrstuvwxyz" 需要修改多少个字符
- 具体方法：将窗口内的每个字符与目标字母表中对应位置的字符进行比较，如果不同，则修改次数加 1
- 在所有窗口中找到最小的修改次数
C++：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
string s;
cin >> n >> s;
if (n < 26) {
cout << -1 << endl;
continue;
}
int minOps = 26;
string target = "abcdefghijklmnopqrstuvwxyz";
// 滑动窗口，检查当前字串的26个字符与目标的匹配情况
for (int i = 0; i <= n - 26; i++) {
int ops = 0;
for (int j = 0; j < 26; j++) {
if (s[i + j] != target[j]) { // 如果不匹配，操作数++
ops++;
}
}
minOps = min(minOps, ops); // 得到最小的操作数
}
cout << minOps << endl;
}
return 0;
}
Java：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while (T-- > 0) {
int n = in.nextInt();
String s = in.next();
if (n < 26) {
System.out.println(-1);
continue;
}
int minOps = 26;
String target = "abcdefghijklmnopqrstuvwxyz";
// 滑动窗口，检查当前字串的26个字符与目标的匹配情况
for (int i = 0; i <= n - 26; i++) {
int ops = 0;
for (int j = 0; j < 26; j++) {
if (s.charAt(i + j) != target.charAt(j)) { // 如果不匹配，操作数++
ops++;
}
}
minOps = Math.min(minOps, ops); // 得到最小的操作数
}
System.out.println(minOps);
}
}
}
Python：
def main():
T = int(input())
for _ in range(T):
n = int(input())
s = input()
if n < 26:
print(-1)
continue
min_ops = 26
target = "abcdefghijklmnopqrstuvwxyz"
# 滑动窗口，检查当前字串的26个字符与目标的匹配情况
for i in range(n - 25):
ops = 0
for j in range(26):
if s[i + j] != target[j]: # 如果不匹配，操作数++
ops += 1
min_ops = min(min_ops, ops) # 得到最小的操作数
print(min_ops)
if __name__ == "__main__":
main()
第二题
给定一个长度为 n 的非严格递增数组 a₁≤a₂≤…≤aₙ。你可以执行以下操作至多一次：
- 选择区间 [l,r]，对每个 i∈[l,r] 执行 aᵢ←aᵢ + k×(r−i+1)，其中 k 是给定的固定参数。
请找出能使操作后数组极差（最大值与最小值之差）超过 d 的最小区间长度（可以为 0）。若无法达成，输出 -1。
名词解释：
- 极差：数组最大值与最小值的差值，例如数组 {2,5,7} 的极差为 5。
输入描述
第一行输入 T（1≤T≤10⁴）表示测试组数。每组数据包含：
- 第一行三个整数 n,d,k（2≤n≤2×10⁵，0≤d≤10¹²，1≤k≤10⁹）
- 第二行 n 个非严格递增整数 a₁,a₂,…,aₙ（1≤aᵢ≤10⁹）
保证所有测试数据∑n≤2×10⁵。
输出描述
每组数据输出一个整数，表示满足条件的最小区间长度。
样例输入
3 4 5 2 1 3 5 7 3 10 1 2 6 8 3 8 5 1 2 3
样例输出
0 -1 2
参考题解
这道题需要找到一个最短的连续子区间 [l, r]，对该区间内的数进行操作后，使得整个数组的极差（最大值 - 最小值）超过 d。
核心思路：
- 初始检查：如果原数组极差已经 > d，则不需要操作，区间长度为 0
- 情况一：操作区间不包含第一个元素 (l > 1)遍历所有可能的 l（从 2 到 n）对于每个 l，计算满足条件的最小 len目标是让 new_max - a[0] > d，即 a[l-1] + k×len - a[0] > d通过数学计算得出 len > (d + a[0] - a[l-1]) / k
- 情况二：操作区间包含第一个元素 (l = 1)遍历所有可能的 r（从 1 到 n）动态维护 max(a_j - k×j) 的值，以便 O(1) 计算新最大值检查 new_max - new_min > d
C++：
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
void solve() {
int n;
long long d, k;
cin >> n >> d >> k;
long long a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 初始情况检查
if (a[n - 1] - a[0] > d) {
cout << 0 << endl;
return;
}
long long minLen = LLONG_MAX;
// 情况一: l > 1 (操作区间不包含第一个元素)
for (int i = 1; i < n; i++) {
long long l = i + 1;
long long rhs = d + a[0] - a[i];
long long requiredLen;
if (rhs < 0) {
requiredLen = 1;
} else {
requiredLen = rhs / k + 1;
}
if (l + requiredLen - 1 <= n) {
minLen = min(minLen, requiredLen);
}
}
// 情况二: l = 1 (操作区间包含第一个元素)
long long maxC = LLONG_MIN;
for (int j = 0; j < n; j++) {
long long r = j + 1;
long long len = r;
maxC = max(maxC, a[j] - k * r);
long long maxInSegment = maxC + k * r + k;
long long newMax = max(a[n - 1], maxInSegment);
long long newMin = a[0] + k * len;
if (newMax - newMin > d) {
minLen = min(minLen, len);
break;
}
}
if (minLen == LLONG_MAX) {
cout << -1 << endl;
} else {
cout << minLen << endl;
}
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Java：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
solve(sc);
}
sc.close();
}
public static void solve(Scanner sc) {
int n = sc.nextInt();
long d = sc.nextLong();
long k = sc.nextLong();
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
// 初始情况检查
if (a[n - 1] - a[0] > d) {
System.out.println(0);
return;
}
long minLen = Long.MAX_VALUE;
// 情况一: l > 1 (操作区间不包含第一个元素)
for (int i = 1; i < n; i++) {
long l = i + 1;
long rhs = d + a[0] - a[i];
long requiredLen;
if (rhs < 0) {
requiredLen = 1;
} else {
required
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
阿里云工作强度 647人发布