笔试时间：2024年03月13日

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

第一题

题目：游游的you子串

游游拿到了一个字符串，她想重排这个字符串后，使得该字符串包含尽可能多的"you"连续子串。你能帮帮她吗？

输入描述

一个仅包含小写字母的字符串，长度不超过10^5。

输出描述

重排后的字符串。有多解时输出任意即可。

样例输入

yyoouuuu

样例输出

uyouyouu

参考题解

统计you中最小字符串的个数x，res = x * you + 剩下的。

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

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

int main() {
    std::string input;
    std::cin >> input;

    int cnt = std::min({std::count(input.begin(), input.end(), 'y'),
                        std::count(input.begin(), input.end(), 'o'),
                        std::count(input.begin(), input.end(), 'u')});

    std::unordered_map<char, int> freq;
    for (char ch : input) {
        freq[ch]++;
    }

    freq['y'] -= cnt;
    freq['o'] -= cnt;
    freq['u'] -= cnt;

    std::string result(cnt, 'y');
    for (auto& kv : freq) {
        if (kv.second > 0) {
            result += std::string(kv.second, kv.first);
        }
    }

    std::cout << result << std::endl;

    return 0;
}

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

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();

        int cnt = Math.min(Math.min(countChar(input, 'y'), countChar(input, 'o')), countChar(input, 'u'));

        Map<Character, Integer> charCount = new HashMap<>();
        for (char c : input.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        charCount.put('y', charCount.get('y') - cnt);
        charCount.put('o', charCount.get('o') - cnt);
        charCount.put('u', charCount.get('u') - cnt);

        StringBuilder res = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : charCount.entrySet()) {
            char c = entry.getKey();
            int count = entry.getValue();
            if (count > 0) {
                res.append(String.valueOf(c).repeat(count));
            }
        }

        System.out.println("you".repeat(cnt) + res.toString());
    }

    private static int countChar(String str, char c) {
        int count = 0;
        for (char ch : str.toCharArray()) {
            if (ch == c) {
                count++;
            }
        }
        return count;
    }
}

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

from collections import Counter
string = input()
cnt = min(string.count('y'), string.count('o'), string.count('u'))
dic = Counter(string)

dic['y'] -= cnt
dic['o'] -= cnt
dic['u'] -= cnt
res = ["you"]*cnt
for k,v in dic.items():
    if v > 0: res += [k]*v
print(''.join(res))

第二题

题目：游游的数组推平

游游拿到了一个数组，她每次操作可以任选一个元素加 1 或者减 1。游游想知道，将所有元素都变成和ai相等需要操作最少多少次？你需要回答i∈[1,n]的结果。

输入描述

第一行输入一个正整数n，代表数组的大小。第二行输入n个正整数ai，代表数组的元素。

1<=n<=10^5

1<=ai<=10^9

输出描述

输出n行，分别代表i∈[1,n]的结果。

样例输入

3

2 1 4

样例输出

3

4

5

说明：数组变成[2,2,2]需要操作 3 次，变成[1,1,1]需要操作 4 次，变成[4,4,4]需要操作 5 次。

参考题解

前缀和。

假设数组排序后为a0 a1 a2 a3 .... ai ... an-1，假设变换成ai，那么应该是：(a[i]-a[i-1] + a[i]-a[i-2] + ... a[i]-a[0]) + (a[i+1]-a[i] + a[i+2]-a[i] + ... a[n-1]-a[i]) = (i*a[i] - (a[0] + ... a[i-1])) + (a[i+1]+....a[n-1] - (n-i-1)*a[i])。可以用前缀和来快速计算。

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    vector<int> sorted_arr = arr;
    sort(sorted_arr.begin(), sorted_arr.end());

    vector<int> pres(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        pres[i] = pres[i - 1] + sorted_arr[i - 1];
    }

    for (int a : arr) {
        auto index = lower_bound(sorted_arr.begin(), sorted_arr.end(), a) - sorted_arr.begin();
        cout << (index) * a - pres[index] + pres[n] - pres[index + 1] - (n - index - 1) * a << endl;
    }

    return 0;
}

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

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = scanner.nextInt();
        }

        int[] sortedArr = Arrays.copyOf(arr, n);
        Arrays.sort(sortedArr);

        int[] pres = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            pres[i] = pres[i - 1] + sortedArr[i - 1];
        }

        for (int a : arr) {
            int index = Arrays.binarySearch(sortedArr, a);
            index = index < 0 ? -index - 1 : index;
            System.out.println((index) * a - pres[index] + pres[n] - pres[index + 1] - (n - index - 1) * a);
        }
    }
}

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

import bisect

n = int(input())
arr = [int(c) for c in input().split()]

sorted_arr = sorted(arr)
pres = [0]*(n+1)
for i in range(1,n+1):pres[i] = pres[i-1] + sorted_arr[i-1]
for a in arr:
    index = bisect.bisect_left(sorted_arr, a)
    print((index)*a - pres[index] + pres[-1]-pres[index+1]-(n-index-1)*a)

第三题

题目：游游的数组压缩

游游拿到了一个数组，她希望你将数组相同的相邻元素压缩在一起。你能帮帮她吗？给定的数组是已经被压缩了一部分的形式，请你继续将其压缩到不能再压缩为止。举个例子，数组[2,3,5,5,5,3]会被压缩成[2(1),3(1),5(3),3(1)]。

输入描述

一个字符串，代表待压缩的数组。字符串长度不超过10^5，且括号内的一定是不超过10^9的正整数。

数组中每个元素的值域范围是[-10^9,10^9]

输出描述

一个字符串，表示压缩后的数组。

样例输入一

[1(2),1(1),-1(3)]

样例输出一

[1(3),-1(3)]

说明：该字符串表示的数组是[1,1,1,-1,-1,-1]

样例输入二

[1(1),2(2),3(31),3(42),2(12)]

样例输出二

[1(1),2(2),3(73),2(12)]

参考题解

将输入的字符串使用正则表达式进行解析，解析成每个字符串和对应出现次数的元组形式。每个元组包含两个元素：值和该值的出现次数。接下来，遍历这个列表。对于每个元素，检查它是否与前一个元素的值相同。如果是，我将这两个元素的出现次数相加，以此来“压缩”数组。

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

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <regex>

using namespace std;

string compressArray(string s) {
    // 解析字符串为数组和次数的列表
    regex pattern("\\[(.*?)\\]");
    smatch match;