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

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

第一题

题目：最大总和

给定一个包含正整数的数组 nums 和一个正整数k，你需要从数组中选择k个数，使得这k个数的总和最大。

输入描述

数组nums，长度n，1≤n≤100，数组中的元素都是正整数。整数k，1≤k≤n。

输出描述

一个整数，表示选出的k个数的最大总和。

样例输入

[4,3,2,7,9],3

样例输出

20

参考题解

小顶堆。

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int getMaxSum(const vector<int>& nums, int k) {
    // 使用优先队列（最小堆）来维护k个最大元素
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 遍历数组元素
    for (int num : nums) {
        // 如果堆还没有满，直接添加
        if (minHeap.size() < k) {
            minHeap.push(num);
        } else if (num > minHeap.top()) {
            // 如果堆已满且当前元素大于堆顶元素，替换堆顶元素
            minHeap.pop();
            minHeap.push(num);
        }
    }

    // 计算k个最大元素的总和
    int maxSum = 0;
    while (!minHeap.empty()) {
        maxSum += minHeap.top();
        minHeap.pop();
    }

    return maxSum;
}

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

public static int getMaxSum(int[] nums, int k) {
        // 使用优先队列来维护k个最大元素
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 遍历数组元素
        for (int num : nums) {
            // 如果堆还没有满，直接添加
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                // 如果堆已满且当前元素大于堆顶元素，替换堆顶元素
                minHeap.poll();
                minHeap.offer(num);
            }
        }

        // 计算k个最大元素的总和
        int maxSum = 0;
        while (!minHeap.isEmpty()) {
            maxSum += minHeap.poll();
        }

        return maxSum;
}

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

import heapq

def get_max_sum(nums, k):
    # 使用最小堆来维护k个最大元素
    min_heap = []

    # 遍历数组元素
    for num in nums:
        # 如果堆还没有满，直接添加
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        elif num > min_heap[0]:
            # 如果堆已满且当前元素大于堆顶元素，替换堆顶元素
            heapq.heappop(min_heap)
            heapq.heappush(min_heap, num)

    # 计算k个最大元素的总和
    max_sum = sum(min_heap)

    return max_sum

第二题

题目：最频子串

给定一个字符串s和一个整数k，你需要找出字符串s中所有长度为k的子串中出现频率最多的子串。如果有多个子串出现频率相同，则返回字典序最小的那个子串。

输入描述

字符串s，长度n，1≤n≤100。

整数k，0≤k≤n。

输出描述

出现频率最高的子串。

样例输入

"mississippi",2

样例输出

“is”

说明

说明：is和si出现的频率一样，但是is在字典次序更小，所以输出is

参考题解

使用 HashMap 来存储每个长度为 k 的子串及其出现频率。2、遍历字符串 s，对于每个长度为 k 的子串，更新其在 HashMap 中的频率计数。3、找出最频子串：遍历 HashMap，找出出现频率最高的子串。如果存在多个子串出现频率相同，则选择字典序最小的子串。

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

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

using namespace std;

string findMostFrequentSubstring(const string& s, int k) {
    if (k == 0 || s.length() < k) {
        return "";
    }

    // 存储子串的频率
    unordered_map<string, int> frequencyMap;

    // 遍历所有长度为k的子串并计算频率
    for (int i = 0; i <= s.length() - k; i++) {
        string substring = s.substr(i, k);
        frequencyMap[substring]++;
    }

    // 找出频率最高的子串，并处理字典序
    int maxFrequency = 0;
    string mostFrequentSubstring = "";
    for (const auto& entry : frequencyMap) {
        const string& substring = entry.first;