笔试时间：2024年03月13日

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

第一题

题目：计算出非回文字符串长度

回文字符串是一种特殊格式的字符串，如果一个字符串满足不区分大小写，且保留数字和字母，去掉其余的符号之后，短语正着读和反着读都一样，则可以认为该短语是一个回文串。假定给出一个字符串A，其子串是A删除一个或连续多个字符后的新字符串B，比如字符串"i" "iq" "qoonex" "nex" "iex"等都是字符串"IQOONEX"的子串，但是"iqon" "oo" "iqnx" "iqq" "ooo" "nn" "iqee"等就不是"IQOONEX"的子串。请计算出非回文字符串长度。

输入描述

待测试的字符串s(1≤|s长度|≤50)。

输出描述

不是回文字符串的非空子序列长度数组(按照由大到小排序)，如果某一长度不存在，则输出-1。

特殊说明：以字符串“@!#abAA@”，总长度为8 为例

1 字符串移除非字母和数字字符，返回的一维数组中，其中8 7 6 5长度的非回文字符串不存在（特殊字符串去掉后不存在这些长度的字符串），输出-1，长度为4的非回文字符串abAA，输出4，往下类推3 、2、1长度的字符串。

2 字符检查不区分大小写，比如上面abAA中，aA和AA正反读是一样的，是回文字符串

样例输入一

[I,Q,O,O,O,O,Q,I]

样例输出一

[-1,7,6,5,4,3,2,-1]

说明：

字符串长度为8,

长度为8的子串不存在不是回文的排序，长度为-1

长度为7的子串存在不是回文的排序，长度为7

长度为6的子串存在不是回文的排序，长度为6

依次往下类推...

样例输入二

[V,I,V,O]

样例输出二

[4,3,2,-1]

说明：

字符串长度为4

长度为4的子串存在不是回文的排序，长度为4

长度为3的子串存在不是回文的排序，长度为3

依次往下类推...

参考题解

首先去除特殊符号以及数字并将全部转化为小写，接下来套用回文字符串判断。对于每一个可能的长度（从字符串的总长度开始递减到1），检查是否存在至少一个子序列不是回文。如果一个特定长度的所有可能子序列都是回文，那么这个长度的输出应该是-1。如果存在至少一个非回文子序列，我们记录这个长度。

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

class Solution {
public:
    vector<int> find_length_of_non_palindromic_substring(vector<string>& input_str) {
        auto is_palindrome = [](const string& s) {
            return s == string(s.rbegin(), s.rend());
        };

        string s = accumulate(input_str.begin(), input_str.end(), string(""));
        string clean_s;
        transform(s.begin(), s.end(), back_inserter(clean_s), [](char c) { return isalnum(c) ? tolower(c) : ' '; });
        int n = clean_s.size();
        vector<int> result(n, -1);

        for (int length = n; length > 0; --length) {
            bool found_non_palindromic = false;
            for (int start = 0; start <= n - length; ++start) {
                string subseq = clean_s.substr(start, length);
                if (!is_palindrome(subseq)) {
                    found_non_palindromic = true;
                    result[length - 1] = length;
                    break;
                }
            }
            if (!found_non_palindromic) {
                result[length - 1] = -1;
            }
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

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

class Solution:
    def find_length_of__non_palindromic_substring(self, input_str: List[str]) -> List[int]:
        def is_palindrome(s):
            return s == s[::-1]
        s = ''.join(input_str)
        clean_s = ''.join(filter(str.isalnum, s)).lower()
        n = len(clean_s)
        result = [-1] * n

        for length in range(n, 0, -1):
            found_non_palindromic = False
            for start in range(0, n - length + 1):
                subseq = clean_s[start:start + length]
                if not is_palindrome(subseq):
                    found_non_palindromic = True
                    result[length - 1] = length
                    break
            if not found_non_palindromic:
                result[length - 1] = -1
        result.reverse()
        return result

第二题

题目：排列字串搜索

给定一个文本字符数组 text[n] 和模板字符数组 pat[m]，请写一个函数 search(pat[], text[])，该函数打印所有的 pat 数组元素排列在 text 数组中出现的次数。假设：n>0;m>0

样例输入一

"abcd","bacdgabcda"

样例输出一

3

说明：pat[] = “abcd” 的排列 → "bacd"，位于 text[] 的位置为 0；pat[] 的排列 → "abcd"，位于 text[] 的位置为 5；pat[] 的排列 → "bcda"，位于 text[] 的位置为 6。

样例输入二

"aaba","aaababaa"

样例输出二

3

样例输入三

"cde","aaababaa"

样例输出三

0

参考题解

滑动窗口。

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

class Solution {
public:
    int search(const string& pat, const string& text) {
        unordered_map<char, int> cnt;
        for (char c : pat) {
            cnt[c]++;
        }