笔试时间：2024年03月12日

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

第一题

题目：偏爱的字符

小李天生偏爱一些字符，对于一个字符串，他总是想把字符串中的字符变成他偏爱的那些字符。如果字符串中某个字符不是他所偏爱的字符，称为非偏爱字符，那么他会将该非偏爱字符替换为字符串中距离该字符最近的一个偏爱的字符。这里的距离定义即为字符在字符串中的对应下标之差的绝对值。如果有不止一个偏爱的字符距离非偏爱字符最近，那么小李会选择最左边的那个偏爱字符来替换该非偏爱字符，这样就保证了替换后的字符串是唯一的。小李的所有替换操作是同时进行的。假定小李有m个偏爱的字符，依次为c1,c2...cm，当小李看到一个长度为n的字符串s时，请你输出小李在进行全部替换操作后形成的字符串。

输入描述

第一行输入两个正整数n，m。

接下来一行输入m个字符c1,c2...cm，每两个字符之间用空格隔开，表示小李偏爱的字符。

接下来一行输入一个字符串s。

1≤n≤100000，1≤m≤26，保证题目中所有的字符均为大写字符，小李偏爱的字符互不相同，且偏爱字符至少出现一次。

输出描述

输出一行字符串，表示小李将给定的字符串s替换后形成的字符串。

样例输入

12 4

Z G B A

ZQWEGRTBYAAI

样例输出

ZZZGGGBBBAAA

说明：字符Q为非偏爱字符，且偏爱字符Z距离它最近，所以替换成Z；同理E距离G最近，替换成G；对于字符W，偏爱字符Z和G与其距离相同，所以替换为左边的Z；.......对于字符 I ，右边没有偏爱字符，左边第一个偏爱字符是A，所以替换成字符A。同一个偏爱字符可能会在字符串中出现多次。

参考题解

将偏爱字符的下表存储在数组中，对需要转化的字符，二分搜索最近的即可。

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

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<char> favorite_chars(m);
    for (int i = 0; i < m; ++i) {
        cin >> favorite_chars[i];
    }
    
    set<char> favorites_set(favorite_chars.begin(), favorite_chars.end());
    
    string text;
    cin >> text;
    
    vector<int> favorite_indexes;
    for (int i = 0; i < text.size(); ++i) {
        if (favorites_set.find(text[i]) != favorites_set.end()) {
            favorite_indexes.push_back(i);
        }
    }
    
    for (int i = 0; i < text.size(); ++i) {
        if (favorites_set.find(text[i]) == favorites_set.end()) {
            int left_idx = distance(favorite_indexes.begin(), lower_bound(favorite_indexes.begin(), favorite_indexes.end(), i)) - 1;
            int right_idx = distance(favorite_indexes.begin(), upper_bound(favorite_indexes.begin(), favorite_indexes.end(), i));
            
            int left_distance = (left_idx >= 0) ? i - favorite_indexes[left_idx] : INT_MAX;
            int right_distance = (right_idx < favorite_indexes.size()) ? favorite_indexes[right_idx] - i : INT_MAX;
            
            int closer_index = (left_distance <= right_distance) ? favorite_indexes[left_idx] : favorite_indexes[right_idx];
            text[i] = text[closer_index];
        }
    }
    
    cout << text << endl;
    
    return 0;
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        List<Character> favoriteChars = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            favoriteChars.add(scanner.next().charAt(0));
        }

        Set<Character> favoritesSet = new HashSet<>(favoriteChars);

        String text = scanner.next();

        List<Integer> favoriteIndexes = new ArrayList<>();
        for (int i = 0; i < text.length(); i++) {
            if (favoritesSet.contains(text.charAt(i))) {
                favoriteIndexes.add(i);
            }
        }

        char[] textArray = text.toCharArray();
        for (int i = 0; i < textArray.length; i++) {
            if (!favoritesSet.contains(textArray[i])) {
                int leftIdx = Collections.binarySearch(favoriteIndexes, i);
                leftIdx = (leftIdx >= 0) ? leftIdx - 1 : -leftIdx - 2;
                int rightIdx = Collections.binarySearch(favoriteIndexes, i);
                rightIdx = (rightIdx >= 0) ? rightIdx + 1 : -rightIdx - 1;