[编程题]小红的字符串修改
- 热度指数：8493 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行输入一个长度不超过
，且仅由小写字母构成的字符串
代表小红手中待替换的串。
代表目标串。
输出描述:
示例1
输入
abc abbc
输出
1
说明
需要进行一次替换，将 '
' 替换成 '
' ，此时得到 "
" ，是 "
" 的子串，因为本质上是由 "
示例2
输入
zzzzzz xyzabc
输出
9
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
String t = scanner.nextLine();
scanner.close();
int sLen = s.length();
int tLen = t.length();
// 因为t的长度不小于s，所以至少有一个可能的子串
int minOperations = Integer.MAX_VALUE;
// 遍历t中所有与s长度相同的子串
for (int i = 0; i <= tLen - sLen; i++) {
int operations = 0;
// 计算将s转换为当前子串所需的操作次数
for (int j = 0; j < sLen; j++) {
char sChar = s.charAt(j);
char tChar = t.charAt(i + j);
// 计算两个字符之间的最小替换次数
operations += minSteps(sChar, tChar);
}
// 更新最小操作次数
if (operations < minOperations) {
minOperations = operations;
}
}
System.out.println(minOperations);
}
// 计算两个字符之间的最小替换次数
private static int minSteps(char a, char b) {
int diff = Math.abs(a - b);
// 替换可以向前或向后，取较小值
return Math.min(diff, 26 - diff);
}
}
发表于 2025-08-27 11:18:31
回复(0)
def replace_num(s1, s2): #入参 一样长度
cont = 0
for j in range(len(s1)):
cont += min(abs(ord(s2[j])-ord(s1[j])),26-abs(ord(s2[j])-ord(s1[j]))) #ord()字母转ascii
return cont
def main():
s1 = input().strip()
s2 = input().strip()
min_cont = float('inf') #定义无穷大的数保证记录第一次的值
if len(s2)>len(s1):
for i in range(len(s2)-len(s1)+1): #子串的可能个数 s1=abc s2=abcd 子串：abc bcd
replc_cont = replace_num(s1,s2[i:i+len(s1)])
if replc_cont < min_cont:
min_cont = replc_cont #更新最小次数
else: #两字符串相等的情况
replc_cont = replace_num(s1,s2)
if replc_cont < min_cont:
min_cont = replc_cont #更新最小次数
print(min_cont)
if __name__ == "__main__":
main()
发表于 2025-09-23 17:37:38
回复(0)
def times(s1,s2):
#在这里输入确保s1和s2长度相同
count = 0
for i in range(len(s1)):
count += min(abs(ord(s1[i])-ord(s2[i])),26-abs(ord(s1[i])-ord(s2[i])))
return count
s = input()
t = input()
len_s = len(s)
len_t = len(t)
min_times = 1e5
for start in range(len_t):
if (start+len_s)<=len_t:
tmp_times = times(s,t[start:start+len_s])
if tmp_times<min_times:
min_times = tmp_times
else:
break
print(min_times)
发表于 2025-08-24 15:56:23
回复(0)
#include <cstdlib>
#include <iostream>
using namespace std;
// uhyxfldiji
// bbgkrifblcaegilmoyxo
int main() {
string s,t;
cin>>s>>t;
int sn=s.size();
int tn=t.size();
int c=0,min=0,ans=0;
for(int i=0;i<tn-sn+1;i++){
c=0;
for(int j=0;j<sn;j++){
ans=abs(s[j]-t[i+j]);
if(ans>13){
ans=26-ans;
}
c+=ans;
}
if( min==0 || c<min){
min=c;
}
}
cout<<min;
}
发表于 2025-08-03 16:21:58
回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
//计算将子串t的[start, start+len-1]范围内的字符变成s所需的最少替换次数
int calculateMinReplacement(char *s,char *t, int start, int len){
int replacement = 0;
for(int i = 0; i < len; i++){
int diff = abs(s[i] -t[start +i]);
//替换次数为两者之间的最小距离
replacement +=(diff <=13)?diff:26-diff;
}
return replacement;
}
int main(){
char s[10001], t[10001];
scanf("%s",s);
scanf("%s",t);
int s_len = strlen(s);
int t_len = strlen(t);
// 初始化最小替换次数为最大整数
int min_replacement = INT_MAX;
//遍历t中每一个可能的其实位置，计算相应的替换次数
for(int i = 0; i <= t_len - s_len; i++){
int replament = calculateMinReplacement(s, t, i, s_len);
if(replament < min_replacement){
min_replacement = replament;
}
}
printf("%d\n",min_replacement);
return 0;
}
发表于 2025-07-09 13:45:20
回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char str1[1000], str2[1000];
int n;
scanf("%s", str1);
scanf("%s", str2);
int len1 = strlen(str1);
int len2 = strlen(str2);
int min = 1e9;
for(int j=0; j<len2-len1+1; j++){
int x = 0;
for(int i=0; i<len1; i++){
int a = str1[i] - 95;
int b = str2[i+j] - 95;
if(a != b){
int d = abs(a-b);
n = d < 26 - d ? d : 26-d;
x += n;
}
}
if(min>x){
min = x;
}
}
printf("%d", min);
return 0;
}
发表于 2026-01-22 21:16:53
回复(0)
//注意s的索引是 i - left ，而不是i，不然会越界
#include <climits>
#include <iostream>
#include<algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s,t;cin>>s>>t;
int slen = s.size();
int left = 0,right = slen - 1;
int res = INT_MAX;
while(right <= t.size() - 1){
int tmpres = 0;
for(int i = left; i <= right; i++){
int tmp = max(s[i - left]- t[i],t[i] - s[i - left]);
int curres = min(tmp,26 - tmp);
tmpres += curres;
}
res = min(res,tmpres);
left++;
right++;
}
cout<<res<<'\n';
}
// 64 位输出请用 printf("%lld")
发表于 2026-01-18 11:24:10
回复(0)
#include <iostream>
using namespace std;
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
int main() {
string s,t;
cin>>s>>t;
int window_len=s.size();
int minstep=999999;
for(int i=0;i<t.size()-(window_len-1);i++){
int window_step=0;
for(int j=0;j<window_len;j++){//滑动窗口滑动t串 统计每一次s串变成窗口内的串的步骤
char charbegin=s[j];
char chartarget=t[i+j];
// cout<<charbegin<<"->"<<chartarget<<' ';
// cout<<"abs:"<<j<<"::"<<min(abs(charbegin-chartarget),26-abs(charbegin-chartarget))<<endl; test
window_step+=min(abs(charbegin-chartarget),26-abs(charbegin-chartarget));
}
minstep=min(minstep,window_step);
}
cout<<minstep;
}
发表于 2026-01-13 17:40:54
回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int readline(char**);//利用内存分配读入任意长度字符串
int min_distance(char, char);//计算两个字母转换的最小次数
int search_min(char*, char*);//使用双循环嵌套求出所有可能的次数
int initial_capacity = 10;//定义字符串最初长度
int main() {
char* s = calloc(initial_capacity + 1, sizeof(char));//初始内存分配
if (s == NULL)
exit(EXIT_FAILURE);
char* t = calloc(initial_capacity + 1, sizeof(char));
if (t == NULL) {
free(s);
exit(EXIT_FAILURE);
}//全部分配成功
readline(&s);
readline(&t);//储存输入
printf("%d\n", search_min(s, t));
free(t);
free(s);//释放内存
return 0;
}
int readline(char** str) {
int cur_cap = initial_capacity;
int i = 0, ch;
while ((ch = getchar()) != '\n' && ch != EOF) {
if (i > cur_cap) {
cur_cap += 5;
*str = realloc(*str, (cur_cap + 1) * sizeof(char));
if (*str == NULL)
exit(EXIT_FAILURE);
}
(*str)[i++] = ch;
}
(*str)[i] = '\0';
*str = realloc(*str, (strlen(*str) + 1) * sizeof(char));
return strlen(*str);
}
int min_distance(char a, char b) {
if (a > b)
return (a - b) > (26 - a + b) ? 26 - a + b : a - b;//返回可能次数中的最小值（下同）
else
return (b - a) > (26 - b + a) ? 26 - b + a : b - a;
}
int search_min(char* s, char* t) {
int slen = strlen(s);
int tlen = strlen(t);
int min = 0;
for (int i = 0; i < slen; i++)
min += min_distance(s[i], t[i]);//确定第一组可能，方便与其他情况比较
int current_min;
for (int i = 1; i <= tlen - slen; i++) {//在上次循环基础上遍历字符串t，注意最后的元素的位置
current_min = 0;
for (int j = 0; j < slen; j++)//遍历字符串s
current_min += min_distance(t[i + j], s[j]);
if (current_min < min)
min = current_min;//储存现在最小的情况
}
return min;
}
发表于 2026-01-07 16:05:09
回复(0)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int min(char a,char b)
{
int dir= abs(a-b);
return dir < 26-dir ? dir : 26-dir;
}
int main() {
char s[1001];
char t[1001];
scanf("%s",&s);
scanf("%s",&t);
int len_s=strlen(s);
int len_t=strlen(t);
int num=10000;
for(int i=0;i<len_t-len_s;i++)
{
int sum=0;
for(int j=0;j<len_s;j++)
{
sum += min(s[j], t[i+j]);
}
if(sum<num)
{
num=sum;
}
}
printf("%d",num);
return 0;
}
#include <string.h>
#include <stdlib.h>
int min(char a,char b)
{
int dir= abs(a-b);
return dir < 26-dir ? dir : 26-dir;
}
int main() {
char s[1001];
char t[1001];
scanf("%s",&s);
scanf("%s",&t);
int len_s=strlen(s);
int len_t=strlen(t);
int num=10000;
for(int i=0;i<len_t-len_s;i++)
{
int sum=0;
for(int j=0;j<len_s;j++)
{
sum += min(s[j], t[i+j]);
}
if(sum<num)
{
num=sum;
}
}
printf("%d",num);
return 0;
}
发表于 2025-11-17 19:44:55
回复(0)
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let s = '', t = '', sLen = 0, tLen = 0;
const chartCode = "a".charCodeAt(0);
rl.on('line', function (line) {
const tokens = line.split(' ');
if(s === ''){
s = tokens[0];
sLen = s.length;
return
}
t = tokens[0];
tLen = t.length;
const sCharCodeList = s.split('').map(val=> {return val.charCodeAt(0) - chartCode})
const tCharCodeList = t.split('').map(val=> {return val.charCodeAt(0) - chartCode})
let result = null;
for(let i = 0; i < tLen - sLen; i++){
let count = 0;
for(let n = 0; n < sCharCodeList.length; n++){
const diff = Math.abs(sCharCodeList[n] - tCharCodeList[n + i])
count += Math.min(diff, 26 - diff)
}
if(result === null){
result = count
}
if(count < result){
result = count
}
}
console.log(result)
});
发表于 2025-10-17 10:30:08
回复(0)
s = input()
t = input()
min_number = len(s)*26
for i in range(len(t)-len(s)+1):
number = 0
for j in range(i,i+len(s)):
ord_t = ord(t[j])-ord("a")
ord_s = ord(s[j-i])-ord("a")
if ord_t == ord_s:
continue
else:
number += min(abs(ord_s-ord_t),26-abs(ord_s-ord_t))
min_number = min(min_number,number)
print(min_number)
发表于 2025-09-29 21:06:08
回复(0)
import sys
a = input()
b = input()
res = []
left, right = 0, len(a)
while left <= len(b) - len(a):
length = 0
for i in range(left, right):
diff = abs(ord(b[i]) - ord(a[i-left]))
length += min(diff, 26 - diff)
res.append(length)
left += 1
right += 1
print(min(res))
发表于 2025-09-18 16:38:22
回复(0)
#include <iostream>
#include<string>
#include<climits>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
int op = INT_MAX;
int len = s.size();
int n = t.size() - len;
for (int i = 0; i < n; i++) {
int p = 0;
for (int j = 0; j < len; j++) {
char ch_min=min(t[i+j],s[j]);
char ch_max=max(t[i+j],s[j]);
p +=min(ch_max-ch_min+0,ch_min+26-ch_max);
}
op=min(p,op);
}
cout<<op;
}
发表于 2025-09-13 17:02:45
回复(0)
#include <iostream>
#include <string>
#include <climits>
using namespace std;
int main() {
string a, b;
cin >> a >> b;
int min = INT_MAX;
int sum = 0;
for(int i=0; i<=b.size()-a.size(); i++) {
sum = 0;
for(int j=0; j<a.size(); j++) {
int diff = (a[j] - b[i+j] + 26 ) % 26;
sum += diff <= 13 ? diff : 26-diff;
}
if(sum < min) {
min = sum;
}
}
cout << min << endl;
}
发表于 2025-08-09 14:43:11
回复(0)
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
string s1, s2;
cin >> s1 >> s2;
size_t pos = s2.find(s1);
if (pos != string::npos) {
cout << "0" << endl;
}
else {
if (s1.length() == s2.length()) {
int sum = 0;
for (int x = 0; x < s1.length(); x++) {
if (abs(s1[x] - s2[x] > 13)) {
sum += 26 - abs(s1[x] - s2[x] >= 13);
}
else {
sum += abs(s1[x] - s2[x]);
}
}
cout << sum << endl;
}
else {
int min = 13001;
for (int x = 0; x < s2.length() - s1.length() + 1; x++) {
int value = 0;
for (int y = 0; y < s1.length(); y++) {
if (abs(s2[x + y] - s1[y]) >= 13) {
value += 26 - abs(s2[x + y] - s1[y]);
}
else {
value += abs(s2[x + y] - s1[y]);
}
}
if (min > value) {
min = value;
}
}
cout << min << endl;
}
}
return 0;
}
#include <string>
#include <cmath>
using namespace std;
int main() {
string s1, s2;
cin >> s1 >> s2;
size_t pos = s2.find(s1);
if (pos != string::npos) {
cout << "0" << endl;
}
else {
if (s1.length() == s2.length()) {
int sum = 0;
for (int x = 0; x < s1.length(); x++) {
if (abs(s1[x] - s2[x] > 13)) {
sum += 26 - abs(s1[x] - s2[x] >= 13);
}
else {
sum += abs(s1[x] - s2[x]);
}
}
cout << sum << endl;
}
else {
int min = 13001;
for (int x = 0; x < s2.length() - s1.length() + 1; x++) {
int value = 0;
for (int y = 0; y < s1.length(); y++) {
if (abs(s2[x + y] - s1[y]) >= 13) {
value += 26 - abs(s2[x + y] - s1[y]);
}
else {
value += abs(s2[x + y] - s1[y]);
}
}
if (min > value) {
min = value;
}
}
cout << min << endl;
}
}
return 0;
}
发表于 2025-08-03 19:00:46
回复(0)
问题信息
难度：
18条回答
100收藏
1610浏览
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
