笔试时间：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 Counterstring = input()cnt = min(string.count('y'), string.count('o'), string.count('u'))dic = Counter(string)dic['y'] -= cntdic['o'] -= cntdic['u'] -= cntres = ["you"]*cntfor k,v in dic.items():    if v > 0: res += [k]*vprint(''.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 bisectn = 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;