笔试时间：2024年08月31日 秋招

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

第一题

题目

小明获得了一项任务，任务是一个谜题，谜题的答案是一个长度为N的字母串。小明试图寻找答案，整理出所有的字符串。为了不重复，他萌生了按字典序浏览单词的想法。但是小明已经厌倦了手动计算每个字符串的下一个字符串，所以他想让你帮助他编写一个程序自动化实现这个过程。编写一个程序，根据输入的字母串，按字典序输出下一个单词(长度相同)。

输入描述

输入的第一行给出一个字符串S;

1 ≤ S < 10^3，字母串仅包含小写字母。

输出描述

根据输入的字母串，按字典序输出与给出字母串长度相同的下一个字母串。若没有这样的字母串，输出-1。

样例输入一

zz

样例输出一

-1

样例输入二

aa

样例输出二

ab

参考题解

判断是否全是z，全是z输出-1，找到第一个不是z的然后当面字母加1，后面的的全变成a。

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

#include <iostream>
#include <string>
using namespace std;

string solve(string s) {
    int n = s.length();
    int i = n - 1;

    while (i >= 0 && s[i] == 'z') {
        i--;
    }

    if (i == -1) {
        return "-1";
    }

    s[i] = s[i] + 1;
    for (int j = i + 1; j < n; j++) {
        s[j] = 'a';
    }

    return s;
}

int main() {
    string s;
    getline(cin, s);
    s.erase(0, s.find_first_not_of(" \t\n\r")); // Equivalent to strip() in Java
    s.erase(s.find_last_not_of(" \t\n\r") + 1);

    cout << solve(s) << endl;
    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine().strip();
        System.out.println(solve(s));
        scanner.close();
    }

    public static String solve(String s) {
        char[] sArray = s.toCharArray();
        int n = sArray.length;

        int i = n - 1;
        while (i >= 0 && sArray[i] == 'z') {
            i--;
        }

        if (i == -1) {
            return "-1";
        }

        sArray[i] = (char) (sArray[i] + 1);
        for (int j = i + 1; j < n; j++) {
            sArray[j] = 'a';
        }
        return new String(sArray);
    }
}

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

def solve(s):
    s_array = list(s)
    n = len(s_array)

    i = n - 1
    while i >= 0 and s_array[i] == 'z':
        i -= 1

    if i == -1:
        return "-1"

    s_array[i] = chr(ord(s_array[i]) + 1)
    for j in range(i + 1, n):
        s_array[j] = 'a'

    return ''.join(s_array)

if __name__ == "__main__":
    s = input().strip()
    print(solve(s))

第二题

题目

给出一个几个互不相同的非负整数，最初是无序的，现在有两种操作:选择两个连续的数字，然后反转他们的位置，比如「1,2会变成2，1选择三个连续的数字，然后反转他们的位置，比如「1,2,3会变成3,2,1可以证明，在有限次以上两种操作下，一定可以将数列变为有序。但是如果一直进行第一种操作，那不就变成冒泡排序了吗，所以你要最小化第一种操作的次数。现在问在要把所有数字变成升序的前提下，最少要进行多少次第一种操作？

输入描述

第一行输入一个正整数n，代表数字的个数

接下来n行，每行一个整数ai,保证这些数字互不相同

l ≤ n ≤ 10^5

0 ≤ ai < 10^9

输出描述

输出一个整数，代表最少进行的操作1的次数。

样例输入

4

2

4

3

1

样例输出

1

说明

先对最后三个数字进行一次操作2，然后再对前两个数字进行一次操作1

说明

输入给定的间隔为50，如果以元素1为起点，则可以消除1,51,101这些元素，因此，我们可以消除给定数组中的1这个元素，同理，如果以2为起点，则可以消除2,52,102这些元素，因此，我们可以消除给定数组中的2这个元素，以此类推，无论以哪个元素作为起点，都只能消除1个元素，因此返回最小的起点元素1。

参考题解

统计每个数与最终位置的距离为奇数之和，一个是原始数组一个是最终排序后的数组，如果同一个数在两个数组中的距离为偶数那么一定可以通过第二种方式置换得到，然后距离差为奇数的数字个数一定是偶数，最后除以2就是最终答案。

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

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    cin.ignore(); // 忽略换行符

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    vector<int> nums2 = nums; // 克隆数组
    sort(nums2.begin(), nums2.end());

    map<int, int> dic;