笔试时间：2025年8月27日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

定义函数 countUniqueChars(s)，用于统计字符串 s 中的唯一字符（即出现次数恰好为1的字符）个数。例如：s = "AMAP"，唯一字符为 'M' 和 'P'（各出现一次），因此 countUniqueChars(s) = 2。给定字符串 s（长度满足 1 <= s.length <= 10^5，且只包含大写英文字母），计算所有子字符串 t（包括重复出现的子串）的 countUniqueChars(t) 的总和。

输入描述

输入给定一个字符串，长度 <= 10^5，只包含大写字符；

输出描述

在代码补全中返回对应答案。

样例输入

"ABC"

样例输出

10

所有子串："A", "B", "C", "AB", "BC", "ABC"。- 每个子串均由唯一字符组成（无重复字符），因此总和为 1+1+1+2+2+3=10。

参考题解

预处理每个字符出现的位置（记录下标）。对于每个字符 c 的每个出现位置 i，找出前一个相同字符的位置 left（若无则为-1）和后一个相同字符的位置 right（若无则为n）。则字符 c 在位置 i 对总和的贡献为：以 i 为中心扩展，使得 c 唯一的子串数量 = (i - left) * (right - i)。遍历所有字符和所有出现位置，累加贡献即可。

C++：

#include <bits/stdc++.h>
using namespace std;

int uniqueLetterString(const string& s) {
    int n = (int)s.size();
    unordered_map<char, vector<int>> pos;
    pos.reserve(256);

    for (int i = 0; i < n; ++i) {
        pos[s[i]].push_back(i);
    }

    long long res = 0;
    for (auto& kv : pos) {
        const vector<int>& idx = kv.second;
        int m = (int)idx.size();
        for (int i = 0; i < m; ++i) {
            int left  = (i > 0)     ? idx[i - 1] : -1;
            int right = (i < m - 1) ? idx[i + 1] : n;
            res += 1LL * (idx[i] - left) * (right - idx[i]);
        }
    }
    return (int)res;
}

Java：

import java.util.*;

class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        Map<Character, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            map.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
        }

        long res = 0;
        for (List<Integer> idx : map.values()) {
            int m = idx.size();
            for (int i = 0; i < m; ++i) {
                int left  = (i > 0)     ? idx.get(i - 1) : -1;
                int right = (i < m - 1) ? idx.get(i + 1) : n;
                res += (long)(idx.get(i) - left) * (right - idx.get(i));
            }
        }
        return (int)res;
    }
}

Python：

def uniqueLetterString(s: str) -> int:
    n = len(s)
    index_map = {}
    for i, char in enumerate(s):
        if char not in index_map:
            index_map[char] = []
        index_map[char].append(i)

    res = 0
    for indices in index_map.values():
        m = len(indices)
        for i in range(m):
            left = indices[i-1] if i > 0 else -1
            right = indices[i+1] if i < m-1 else n
            res += (indices[i] - left) * (right - indices[i])
    return res

第二题

题目：有一个大小为m x n的矩阵网格mat，小红按照以下对角线遍历的顺序去捡糖果，在经过的网格路线上，每隔一个网格会有一个糖果(第一个网格一定有糖果)，请按遍历顺序输出小红捡到糖果的网格序号。输出要求：用数组返回捡到糖果的网格序号。

输入描述

第一行为测试数据中mat的大小m和n，以空格间隔；随之是m行，每行长度为n的数据，以空格分割。

输出描述

一行空格分割的序号。补充说明提示：2<= m <= 202 <= n <= 20

样例输入

2 3  

1 2 3  

4 5 6

样例输出

1 4 3

参考题解

根据题目要求，我们需要按照对角线遍历顺序收集矩阵中的值，然后每隔一个网格取一个值（第一个网格一定有糖果）。对角线遍历的规则是：对于每条对角线索引k（从0到m+n-2），如果k是偶数，则从高行索引向低行索引遍历；如果k是奇数，则从低行索引向高行索引遍历。

C++：

#include <bits/stdc++.h>
using namespace std;

int mai