笔试时间：2024年07月13日 提前批

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

第一题

题目：找01

牛牛拥有一个长度为 n 的01 串，现在他想知道，对于每个字符，在它前面的最近的不同字符的下标是多少？

输入描述

本题为多组测试数据。

第一行输入一个正整数 T(1<=t<=100)，代表测试数据组数。

对于每组测试数据，第一行输入一个正整数 n(1<=n<=1000)，代表初始 01串的长度。

第二行输入一个长度为 n的01串，代表初始字符串。

输出描述

对于每组测试数据，一行输出 n 个整数 a1,a2,...,an，其中 ai 代表初始字符串中第 i 个位置的字符前面，最近的不同字符的下标是 ai，特殊的，如果前面不存在不同字符，则输出 -1 表示不存在。

样例输入

1

4

1101

样例输出

-1 -1 2 3

参考题解

遍历字符串，不断记录0和1的下标，对于0就取上一次1的下标，并且更新0的下标；对于1则取上一次0的下标，更新1的下标。

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

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int p0 = -1, p1 = -1;
        vector<int> res(n, -1);
        
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c == '0') {
                res[i] = p1;
                p0 = i + 1;
            } else {
                res[i] = p0;
                p1 = i + 1;
            }
        }
        
        for (int i = 0; i < n; ++i) {
            if (i > 0) cout << " ";
            cout << res[i];
        }
        cout << endl;
    }
    return 0;
}

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

import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            String s = sc.next();
            int p0 = -1, p1 = -1;
            Vector<Integer> res = new Vector<>(n);

            for (int i = 0; i < n; ++i) {
                res.add(-1);
            }

            for (int i = 0; i < n; ++i) {
                char c = s.charAt(i);
                if (c == '0') {
                    res.set(i, p1);
                    p0 = i + 1;
                } else {
                    res.set(i, p0);
                    p1 = i + 1;
                }
            }

            for (int i = 0; i < n; ++i) {
                if (i > 0) System.out.print(" ");
                System.out.print(res.get(i));
            }
            System.out.println();
        }
        sc.close();
    }
}

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

def main():
    T = int(input())
    for _ in range(T):
        n = int(input())
        s = input()
        p0 = -1
        p1 = -1
        res = [-1] * n

        for i in range(n):
            c = s[i]
            if c == '0':
                res[i] = p1
                p0 = i + 1
            else:
                res[i] = p0
                p1 = i + 1

        print(" ".join(map(str, res)))

if __name__ == "__main__":
    main()

第二题

题目：不能出现太多

给定n个数字A1,A2,..An，请求出这些数字中出现次数小于等于k的最小的数。

输入描述

第一行正整数n,k

接下来一行n个正整数，第i个表示Ai 1<=k<=n<=10^5,1<=Ai<=10^9

输出描述

一行一个整数，表示答案。

如果不存在出现次数少于等于k次的数字，输出-1

样例输入一

5 2

1 1 1 2 3

样例输出一

2

说明

1出现了三次，不合法；2,3均只出现了一次，其中2最小

样例输入二

8 2

1 1 4 5 7 1 3 3

样例输出二

3

参考题解

利用哈希表模拟。

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

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

int solve(int n, int k, const vector<int>& nums) {
    unordered_map<int, int> counter;
    for (int num : nums) {
        counter[num]++;
    }

    vector<int> sorted_keys;
    for (const auto& pair : counter) {
        sorted_keys.push_back(pair.first);
    }
    sort(sorted_keys.begin(), sorted_keys.end());

    for (int key : sorted_keys) {
        if (counter[key] <= k) {
            return key;
        }
    }
    return -1;
}

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

    cout << solve(n, k, nums) << endl;
    return 0;
}

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

import java.util.*;

public class Main {
    public static int solve(int n, int k, List<Integer> nums) {
        Map<Integer, Integer> counter = new HashMap<>();
        for (int num : nums) {
            counter.put(num, counter.getOrDefault(num, 0) + 1);
        }

        List<Integer> sortedKeys = new ArrayList<>(counter.keySet());
        Collections.sort(sortedKeys);

        for (int key : sortedKeys) {
            if (counter.get(key) <= k) {
                return key;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        List<Integer> nums = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) {
            nums.add(sc.nextInt());
        }

        System.out.println(solve(n, k, nums));
        sc.close();
    }
}

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

def solve(n, k, nums):
    from collections impor