首页 > 试题广场 >

偏爱的字符

[编程题]偏爱的字符

热度指数：1305 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

第一行输入两个正整数n，m。
接下来一行输入m个字符，每两个字符之间用空格隔开，表示小李偏爱的字符。
接下来一行输入一个字符串s。

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

输出描述:

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

示例1

输入

12 4
Z G B A
ZQWEGRTBYAAI

输出

ZZZGGGBBBAAA

说明

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

算法知识视频讲解

查看答案及解析

Java

Dosure33

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String mn = in.nextLine();
        String cc = in.nextLine();
        String s = in.nextLine();
        String[] mnArr = mn.split(" ");
        int n = Integer.parseInt(mnArr[0]);
        List<String> cList = Arrays.asList(cc.split(" "));
        char[] sArr = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i >= j && cList.contains("" + sArr[i - j])) {
                    sb.append(sArr[i - j]);
                    break;
                }
                if (i + j < n && cList.contains("" + sArr[i + j])) {
                    sb.append(sArr[i + j]);
                    break;
                }
            }
        }
        System.out.println(sb.toString());
    }
}

发表于 2025-10-13 17:39:57 回复(0)

Java

梦见你是幸运

不难注意到，当一个字符串出现偏爱字符时，总是左边的先选择，所有当从左到右遍历字符串的时候，如果匹配到了偏爱字符则对该字符到上一个偏爱字符中间进行赋值即可，总时间复杂度O(a + b)。

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            Set<character> p = new HashSet<>();
            for (int i = 0; i < b; i++) {
                p.add(in.next().charAt(0));
            }
            in.nextLine();
            String s = in.nextLine();
 
            int pre = -1;
            char[] res = new char[s.length()];
            for (int i = 0; i < a; i++) {
                if (p.contains(s.charAt(i))) {
                    if (pre < 0) {
                        for (int j = 0; j < i; j++) {
                            res[j] = s.charAt(i);
                        }
                    } else {
                        for (int j = pre; j < (i - pre) / 2 + pre + 1; j++) {
                            res[j] = s.charAt(pre);
                        }
                        for (int j = (i - pre) / 2 + pre + 1; j < i; j++) {
                            res[j] = s.charAt(i);
                        }
                    }
                    res[i] = s.charAt(i);
                    pre = i;
                }
            }
            if (pre > -1 && pre != a - 1) {
                for (int j = pre; j < a; j++) {
                    res[j] = s.charAt(pre);
                }
            }
            System.out.println(res);
        }
    }
}

编辑于 2025-08-19 14:26:24 回复(0)

Java

大佬求代

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt(),m = in.nextInt();
        String s ="";
        for(int i=0;i<m;i++){
            s+=in.next();
        }
        StringBuilder ss = new StringBuilder(in.next());
        //记录所有偏爱下标:
        List<Integer> list = new ArrayList<>();
        for(int i =0;i<n;i++){
            if(s.contains(ss.charAt(i)+"")){
                list.add(i);
            }
        }
        //遍历所有的偏爱下标,取两个下标的中点,修改,最后一个特殊:
        for(int i =1;i<list.size();i++){
            int l = list.get(i-1),r = list.get(i);
            int mid = l+(r-l)/2;
            for(int j = l+1;j<=mid;j++)ss.setCharAt(j,ss.charAt(l));
            for(int j = mid+1;j<r;j++)ss.setCharAt(j,ss.charAt(r));
        }
        //处理第一个偏爱下标:
        int index = list.get(0);
        for(int i = 0;i<index;i++)ss.setCharAt(i,ss.charAt(index));
        //处理最后一个偏爱下标:
        index = list.get(list.size()-1);
        for(int i = index+1;i<n;i++)ss.setCharAt(i,ss.charAt(index));
        System.out.println(ss.toString());
    }
}

发表于 2025-08-12 08:45:55 回复(0)

提交观点

问题信息

字符串小米集团双指针

难度：

3条回答 45收藏 921浏览

偏爱的字符

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题