笔试时间：2024年04月21日

历史笔试传送门：2023秋招笔试合集

第一题

题目

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

输入描述

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

第二行输入一个长度为n的、仅由小写字母组成的字符串。

输出描述

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

样例输入

6 2

aaabbc

样例输出

3

参考题解

双指针。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


int main()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int res = 0, ans = n + 1;
    for(int i = 0, j = i + 1; i < n; i ++)
    {
        if(i && s[i] == s[i - 1]) res --;
        while(j < n && res < k)
        {
            if(s[j] == s[j - 1]) res ++;
            j ++;
        }
        if(res == k)
        {
            ans = min(ans, j - i);
        }
    }
    if(ans == n + 1) ans = -1;
    cout << ans;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        String s = scanner.next();
        int res = 0, ans = n + 1;
        for (int i = 0, j = i + 1; i < n; i++) {
            if (i > 0 && s.charAt(i) == s.charAt(i - 1)) res--;
            while (j < n && res < k) {
                if (s.charAt(j) == s.charAt(j - 1)) res++;
                j++;
            }
            if (res == k) {
                ans = Math.min(ans, j - i);
            }
        }
        if (ans == n + 1) ans = -1;
        System.out.println(ans);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n, k = map(int, input().split())
s = input()
res = 0
ans = n + 1
for i in range(n):
    j = i + 1
    if i > 0 and s[i] == s[i - 1]:
        res -= 1
    while j < n and res < k:
        if s[j] == s[j - 1]:
            res += 1
        j += 1
    if res == k:
        ans = min(ans, j - i)
if ans == n + 1:
    ans = -1
print(ans)

第二题

题目

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

1、pi + qi = n + 1

2、|pi - qi| = ai

你能帮帮她吗?

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

输入描述

第一行输入一个正整数n，代表小红拿到的数组大小。

第二行输入n个整数，代表小红拿到的数组。

输出描述

如果无解，请输出-1。 否则第一行输出n个正整数pi。

第二行输出n个正整数，代表小红构造的两个排列。有多解时输出任意即可。

样例输入

3

2 2 0

样例输出

1 3 2

3 1 2

参考题解

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

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int N = 1e5 +7;
int a[N], b[N], c[N];
map<int, vector<pair<int, int>>> mp;
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
        b[i] = a[i];
    }