首页 > 试题广场 >

偏爱的字符

[编程题]偏爱的字符

热度指数：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

梦见你是幸运

不难注意到，当一个字符串出现偏爱字符时，总是左边的先选择，所有当从左到右遍历字符串的时候，如果匹配到了偏爱字符则对该字符到上一个偏爱字符中间进行赋值即可，总时间复杂度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

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)

KotRin

创建left、right数组，数组内部类型为pair<int,int>类型，左边代表的距离，右边代表的是距离哪个偏爱字符，最后遍历s 比较s中字符距离左边偏爱字符和右边偏爱字符，取小的，记得对头尾进行特判

C++代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define str string
#define rep(i,l,r) for(int i = l;i <= r;i++)
typedef pair<int,char> PII;
const int N = 100010;
char ch[26];
signed main() {
    int n,m; cin >> n >> m;
    while(m--) {char c; cin >> c; ch[c - 'A'] = 1;}
        
    str s; cin >> s;
    PII left[N],right[N];
    
    for(int i = 0,l = -1;i < s.size();i++) {
        if(ch[s[i] - 'A']) l = i;

        if(l == -1) {
            left[i].first = 0;
        }else {
            left[i].first = i - l;
            left[i].second = s[l];
        }
    }


    for(int i = s.size() - 1,r = -1;i >= 0;i--) {
        if(ch[s[i] - 'A']) r = i;

        if(r == -1) {
            right[i].first = 0;
        }else {
            right[i].first = r - i;
            right[i].second = s[r];
        }
    }

    for(int i = 0;i < s.size();i++) {
        if(left[i].first > right[i].first) {
            if(!right[i].first) s[i] = left[i].second;
            else s[i] = right[i].second;
        }
        else {
            if(!left[i].first) s[i] = right[i].second;
            else s[i] = left[i].second;
        }
    }

    cout << s << endl;
    

    return 0;
}

发表于 2025-08-21 17:54:40 回复(0)

说又不是不能用的斑马很讲义气

其实就是类似接雨水问题，核心算法就是双指针

import sys
n,m=map(int,input().split())
c=list(map(str,input().split()))
s=list(input())

def transform(n,m,c,s):
    if m==1:    #只有一个偏好字符时，直接输出（缩短时间）
        return(c[0]*n)
    left_idx=-1
    right_idx=-1
    for l in range(n):
        if s[l] in c:    #遍历字符，有偏好字符时更新记录左边偏好字符下标
            left_idx=l
        else:
            if right_idx<l: #右边没有偏好字符，就先寻找右边的偏好字符
                r=l
                while r>right_idx and r<n:
                    if s[r] in c:
                        right_idx=r
                        break    #这里没有break也会跳出循环，加break因为不自信= =
                    else:
                        r+=1
            if left_idx<0:  #左边没有偏好字符，直接替换为右边的偏好字符
                s[l]=s[right_idx]
            elif r==n:  #右边没有找到偏好字符，直接替换为左边的偏好字符
                s[l]=s[left_idx]
            else:   #左右都有偏好字符，计算两边距离再替换
                left_diff=abs(left_idx-l)
                right_diff=abs(right_idx-l)
                if left_diff<=right_diff:
                    s[l]=s[left_idx]
                else:
                    s[l]=s[right_idx]
    return ''.join(char for char in s)
print(transform(n,m,c,s))

编辑于 2025-08-18 10:43:31 回复(0)

精致的熊熊在努力存钱

n,m = map(int,input().split())

li = list(input().split())

s = input()

result = {}

re = []

for i in range(len(s)):

if s[i] in li:

result[i] = s[i]

result_items = list(result.items())

# 处理左端

left_key,left_value = result_items[0]

if left_key > 0:

for i in range(left_key):

re.append(left_value)

# 处理中间部分

for i in range(len(result_items)-1):

current_item = result_items[i] # (key, value)

next_item = result_items[i + 1] # (key, value)

current_key, current_value = current_item

next_key, next_value = next_item

for j in range(current_key,next_key):

d = next_key - current_key - 1

if d % 2 == 0:

zj = current_key + int(d/2)

else:

zj = current_key + 1 + int(d//2)

if j <= zj:

re.append(current_value)

else:

re.append(next_value)

# 处理最右端

right_key,right_value = result_items[-1]

if right_key < n-1:

for i in range(right_key,n):

re.append(right_value)

elif right_key == n-1:

re.append(right_value)

print(''.join(re))

发表于 2025-10-09 16:42:49 回复(0)

求offer卷轴一张

贪心+动态规划

遍历两次，从左到右存储左边最近的偏爱字母下标，从右到左存储右边最近的偏爱字母下标，每次存储判断是否为偏爱字母，不是存储左右边，是存储自己下标，然后按照最优结果去更新字符串。

 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; public class Main { public static void main(String[] args) throws IOException { //12 4  //Z G B A  //ZQWEGRTBYAAI  //输出例子：  //ZZZGGGBBBAAA  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" "); int n = Integer.parseInt(str[0]); int m = Integer.parseInt(str[1]);
        String[] pianai = br.readLine().split(" ");
        Set<String> pianaiSet = new HashSet<String>(); for (int i = 0; i < m; i++) {
            pianaiSet.add(pianai[i]);
        } char[] line= br.readLine().toCharArray(); int[] leftres=new int[n]; int[] rightres=new int[n];
        leftres[0]=-1; if(pianaiSet.contains(Character.toString(line[0]))){
            leftres[0]=0;
        } for(int i=1;i<n;i++){ if(pianaiSet.contains(Character.toString(line[i]))){
                leftres[i]=i;
            }else {
                leftres[i]=leftres[i-1];
            }
        }
        rightres[n-1]=-1; if(pianaiSet.contains(Character.toString(line[n-1]))){
            rightres[n-1]=n-1;
        } for(int i=n-2;i>=0;i--){ if(pianaiSet.contains(Character.toString(line[i]))){
                rightres[i]=i;
            }else {
                rightres[i]=rightres[i+1];
            }
        } int[] res=new int[n]; for(int i=0;i<n;i++){ if (leftres[i]==-1 && rightres[i]!=-1){
                res[i]=rightres[i];
            } else if(rightres[i]==-1 && leftres[i]!=-1){
                res[i]=leftres[i];
            }else { if (i-leftres[i]>rightres[i]-i){
                    res[i]=rightres[i];
                }else {
                    res[i]=leftres[i];
                }
            }
        } for(int i=0;i<n;i++){
            line[i]=line[res[i]];
        }
        String ans=new String(line);
        System.out.println(ans);
    }
}

发表于 2025-09-17 17:17:57 回复(0)

C/C++

就等着被替代把

语言：C++

小白思路分享：利用两个下标存储左右最接近的喜爱字符；因为会优先取左边的，因此向右遍历的时候只用搜索到下标距离比左边小的位置，可以去除大量无效操作

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

int judge_love_char(char c, vector<char> love_char) {
    int res = 0;
    for (auto& lc : love_char) {
        if (c == lc) {
            res = 1;
            break;
        }
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<char> love_char;
    // vector<char> input_char;
    string input_string;
    love_char.resize(m);

    for (int i = 0; i < m; i++) {
        cin >> love_char[i];
    }
    cin >> input_string;

    vector<char> input_char(input_string.begin(), input_string.end());
    vector<char> output_char = input_char;

    int left_love_num = n-1;
    int right_love_num = n - 1;
    for (int i = 0; i < n; i++) {
        if (judge_love_char(input_char[i], love_char)) {
            left_love_num = i;
        } 
        else {
            // if(!judge_love_char(input_char[left_love_num], love_char)){
            //     left_love_num
            // }
            for (int j = i + 1; j <= i+1+left_love_num; j++) {
                if (judge_love_char(input_char[j], love_char)) {
                    right_love_num = j;
                    // cout << right_love_num << " " << input_char[right_love_num] << endl;
                    break;
                }
            }
            if (judge_love_char(input_char[left_love_num], love_char) &&
                judge_love_char(input_char[right_love_num], love_char)) {
                int delta_left = abs(i - left_love_num);
                int delta_right = abs(i - right_love_num);
                if (delta_left <= delta_right && left_love_num >= 0) {
                    output_char[i] = input_char[left_love_num];
                } else {
                    output_char[i] = input_char[right_love_num];
                }
            }
            else if(judge_love_char(input_char[left_love_num], love_char)){
                output_char[i] = input_char[left_love_num];
            }
            else if(judge_love_char(input_char[right_love_num], love_char)){
                output_char[i] = input_char[right_love_num];
            }

        }
    }
    for (auto& lo : output_char)
        cout << lo;
}

编辑于 2025-09-01 11:10:26 回复(0)

勤奋努力的海螺上岸了

滑动窗口：left：左偏爱字符，right：右偏爱字符，mid：遍历字符

1. mid == 偏爱字符（mid == right）

1.1 左缩进，left = mid

1.2 右扩展，找到下一个偏爱字符，超出范围，则剩余非偏爱字符均为left

2. 判断最近偏爱字符

发表于 2025-08-23 14:58:37 回复(0)

牛客723899313号

给一个C++的

#include <iostream>

#include <unordered_map>

#include <vector>

using namespace std;

int main() {

// int a, b;

// while (cin >> a >> b) { // 注意 while 处理多个 case

// cout << a + b << endl;

// }

int m,n;cin>>m>>n;

std::unordered_map<char, int> mp;

for(int i = 0;i<n;i++)

{

char s;

cin>>s;

mp[s] = 1;

}

string data;cin>>data;

vector<int> id;

for(int i = 0;i<data.size();i++)

{

auto it = mp.find(data[i]);

if(it!=mp.end()) id.push_back(i);

}

if(id.size() == 1)

{

for(int i = 0;i<data.size();i++) data[i] = data[id[0]];

cout<<data;

}

else

{

int left = id[0],right = id[1],id_temp = 1;

for(int i = 0;i<data.size();i++)

{

if(i<=left) data[i] = data[left];

else if(i>left&&i<=right)

{

if(i - left<=right - i) data[i] = data[left];

else

{

left = right;data[i] = data[left];

if(id_temp+1<id.size())

{

id_temp++;right = id[id_temp];

}

else {

left = id[id.size()-1];

right = left;

}

};

}

else if(i>=left)

{

data[i] = data[id[id.size()-1]];

}

cout<<data;

}

// 64 位输出请用 printf("%lld")

发表于 2025-08-20 20:36:25 回复(0)

迟缓的少年又熬夜了

思路很简单，数据量也不大。获得所有偏好字符串的下标信息，按照规则进行分配即可。

规则是：按照距离和右边优先进行分配

import java.util.HashMap;

import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
HashSet<character> ls = new HashSet<>();
for (int i = 0; i < m; i++) {
ls.add(in.next().charAt(0));
}
in.nextLine();
String str = in.nextLine();
Map<integer,character> f = new LinkedHashMap<>();
for (int i = 0; i < n; i++) {
Character c = str.charAt(i);
if (ls.contains(c)) {
f.put(i,c);
}
}
int pre = -1;
Character prec = null;
StringBuilder ans = new StringBuilder();
for (Map.Entry<integer,character> entry : f.entrySet()) {
int cur = entry.getKey();
Character curc = entry.getValue();

if (pre == -1) {

// 首个

for (int i = 0; i <= cur; i++) {
ans.append(curc);
}
} else {
int mid = (pre + cur) / 2;
for (int i = pre + 1; i <= mid; i++) {
ans.append(prec);
}
for (int i = mid + 1; i <= cur; i++) {
ans.append(curc);
}
}
pre = cur;
prec = curc;
}

int res = n - ans.length();

// 末尾处理

for (int i = 0; i < res; i++) {
ans.append(prec);
}
System.out.println(ans.toString());
}
}</integer,character></integer,character></character>

发表于 2025-08-20 00:32:43 回复(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)

提交观点

问题信息

字符串小米集团双指针

难度：

11条回答 45收藏 916浏览

偏爱的字符

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题