笔试时间：2024年09月25日 秋招

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

第一题

题目

给出一个整数数组，元素大小范围区间都在[-10,10]之间。可以有三次机会将数组中的一个数替换成任意数，请算出可能的最长相等子段数列的长度。

输入描述

输入一行元素，用空格分割

元素大小范围区间都在[-10，10]之间。

输出描述

输出一个整数x,表示可能的最长相等子段数列的长度。

补充说明：

时间复杂度O(n)

空间复杂度O(1)

数组的长度为1<= n <= 10^5

第一个示例中，可以将数组变成[0,0,0,0,0,3]或者[0,3,3,3,3,3]，结果都是5

样例输入一

0 3 1 0 6 3

样例输出一

5

样例输入二

1 2

样例输出二

2

参考题解

计数频率：统计每个数字出现的次数。计算最长相等子段：使用滑动窗口，通过频率数组找出最多能形成的相等子段长度。替换：使用当前数字的频率和当前窗口大小来决定是否能通过替换达到更长的相等子段。

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

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

using namespace std;

int maxEqualSegmentLength(const vector<int>& nums) {
    int max_count = 0;
    int left = 0;
    int right = 0;
    int replace_count = 3;
    unordered_map<int, int> count_map;

    while (right < nums.size()) {
        count_map[nums[right]]++;
        max_count = max(max_count, count_map[nums[right]]);

        while ((right - left + 1) - max_count > replace_count) {
            count_map[nums[left]]--;
            if (count_map[nums[left]] == 0) {
                count_map.erase(nums[left]);
            }
            left++;
        }

        right++;
    }

    return right - left;
}

int main() {
    string input_line;
    getline(cin, input_line);

    if (input_line.empty()) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> nums;
    istringstream iss(input_line);
    int num;
    while (iss >> num) {
        nums.push_back(num);
    }

    cout << maxEqualSegmentLength(nums) << endl;

    return 0;
}

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

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

public class MaxEqualSegmentLength {

    public static int maxEqualSegmentLength(int[] nums) {
        int maxCount = 0;
        int left = 0;
        int right = 0;
        int replaceCount = 3;
        Map<Integer, Integer> countMap = new HashMap<>();

        while (right < nums.length) {
            countMap.put(nums[right], countMap.getOrDefault(nums[right], 0) + 1);
            maxCount = Math.max(maxCount, countMap.get(nums[right]));

            while ((right - left + 1) - maxCount > replaceCount) {
                countMap.put(nums[left], countMap.get(nums[left]) - 1);
                if (countMap.get(nums[left]) == 0) {
                    countMap.remove(nums[left]);
                }
                left++;
            }

            right++;
        }

        return right - left;
    }

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

        if (inputLine.isEmpty()) {
            System.out.println(0);
            return;
        }

        String[] inputArray = inputLine.split(" ");
        int[] nums = new int[inputArray.length];
        for (int i = 0; i < inputArray.length; i++) {
            nums[i] = Integer.parseInt(inputArray[i]);
        }

        System.out.println(maxEqualSegmentLength(nums));
    }
}

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

def max_equal_segment_length(nums):
    max_count = 0
    left = 0
    right = 0
    replace_count = 3 
    count_map = {}

    while right < len(nums):
        count_map[nums[right]] = count_map.get(nums[right], 0) + 1
        max_count = max(max_count, count_map[nums[right]])

        while (right - left + 1) - max_count > replace_count:
            count_map[nums[left]] -= 1
            if count_map[nums[left]] == 0:
                del count_map[nums[left]]
            left += 1

        right += 1

    return right - left


def main():
    input_line = input().strip()

    if not input_line:
        print(0)
        return

        nums = list(map(int, input_line.split()))

    print(max_equal_segment_length(nums))


if __name__ == "__main__":
    main()

第二题

题目

在文本处理系统中，我们经常需要对文本进行一系列的转换操作。现在，系统接收到了两个字符串 str1 和 str2，它们代表了转换前后的文本状态。系统的任务是验证是否可以通过一系列特定的字符映射操作，将 str1转换成 str2。每一次映射操作，系统可以将 st1中出现的所有相同字母替换成其他任何小写英文字母。系统需要确保这种转换是可能的，并且在满足时间复杂度和空间复杂度的要求下完成验证。

输入描述

输入一行两个字符串str1,str2，用空格分割，表示需要被转换的字符串和转换的目标字符串。

输出描述

输出一个字符串表示转化结果，true 表示能够转化，fasle表示不能转化。

补充说明：

时间复杂度:O(n)，其中n是字符串 str1 或 str2 的长度

空间复杂度:O(k)，其中k是 str1 和 str2 中最大不同字符的数遢

字符串长度:1<=str1.length == str2.length <= 10^4

字符范围:str1 和 str2 中都只会出现小写英文字母

样例输入一

aabcc ccdee

样例输出一

true

说明：

1.系统可以通过以下映射操作将 str1 转换为 str2:

。将'a'映射为’c’

。将'b'映射为’d’

。将'c'映射为‘e‘

样例输入二

aabcc ccdda

样例输出二

false

说明：

系统无法通过映射操作将 str1 转换为 str2，因为 str1 中的"CC"无法转换成str2 中的“da”。

参考题解

映射数组：定义一个大小为 26 的整型数组 c，用来存储字符的映射关系。数组的每个元素初始化为 -1，表示尚未映射任何字符。遍历：通过循环遍历字符串的每个字符：检查当前字符 a[i] 是否已经有对应的映射。如果没有（c[ai] == -1），则将其映射到字符 b[i]。如果已经有映射，检查该映射是否一致。如果不一致，输出 false 并结束程序。

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

#include <iostream>
#include <vector>
#include <string>

int main() {
    std::string a, b;
    std::ci