| 等 级 | |
| 排 名 | 3660 |
| 经 验 | 1796 |
| 参赛次数 | 3 |
| 文章发表 | 1 |
| 年 龄 | 19 |
| 在职情况 | 学生 |
| 学 校 | 大连交通大学 |
| 专 业 | 机械工程+软件工程 |
自我简介：
TA的其他文章
| 字符串的修改 （C++代码） 浏览：2873 |
你可能喜欢
【排队买票】 （C语言代码）浏览：1438 |
C二级辅导-阶乘数列 （C语言代码）浏览：269 |
C语言程序设计教程（第三版）课后习题11.1 （C语言代码）浏览：585 |
C语言程序设计教程（第三版）课后习题9.6 （C语言代码）浏览：586 |
C语言程序设计教程（第三版）课后习题6.7 （C语言代码）浏览：780 |
解体思路：
贪心
对字符串 A 的增删改都会导致操作次数 + 1，所以只需找出字符串 B 中能够对应到字符串 A 中的字符数目（即不需改动的字符），用 A.Length() - count 即可求得。
注意事项:
注意到有可能字符串 B 的第一个字符对应到字符串 A 偏后的字符，所以需要循环 B.Length() 次，忽略掉字符串 B 中的各个字符，依次求解，取最小值。
参考代码:
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 200 + 5;
int main(){
string a, b;
cin >> a >> b;
int ans = maxn;
for(int i = 0; i < b.length(); i ++){
int count = 0;
int posa, posb, pos = 0;
for(posb = i; posb < b.length(); posb ++){
for(posa = pos; posa < a.length(); posa ++){
if(a[posa] == b[posb]){
pos = posa + 1;
count ++;
}
}
}
ans = ans > (a.length() - count) ? (a.length() - count):ans;
}
cout << ans << endl;
return 0;
}0.0分
22 人评分
评论区
代码答案是错的，比如1234和4321输入理论输出为4，你的输出为3
星空 2020-03-17 19:54:03 |
但是用楼主的代码通过了，，这样的变换有没有可能是3呢？（感觉代码逻辑也没毛病）
出家人 2020-07-21 09:53:06 |
题目是有问题的，如果逻辑严密，这道题正确做法会非常麻烦
xiaoyang 2020-10-15 20:08:18 |
@636861284 这题目的做法，感觉确实非常麻烦
虹山上峰 2022-04-02 16:15:34 |
是非常麻烦，写了半天感觉没问题了，妈的，通过不了，21和12很明显需要两次……楼主答案是1却通过了，证明蓝桥杯真不怎样
命运之光 2022-12-30 23:26:10 |
@hongshanshangfe 蓝桥杯测试样例多，这只说明C语言网后台的测试样例不够全面，蓝桥杯比赛时测试样例多，比这个正式太多了
命运之光 2022-12-30 23:26:42 |
#include <bits/stdc++.h> using namespace std; int main(){ string str1,str2; cin>>str1>>str2; int len1=str1.size(),len2=str2.size(); vector<vector<int> > dp(len1+1,vector<int>(len2+1,0)); for(int i=0;i<=len1;i++)dp[i][0]=i; for(int i=0;i<=len2;i++)dp[0][i]=i; for (int i=1;i<=len1;i++) { for (int j=1;j<=len2;j++) { dp[i][j]=min(min(dp[i][j-1]+1, dp[i-1][j]+1),dp[i-1][j-1]+(str1[i-1]==str2[j-1]?0:1)); } } cout<<dp[len1][len2]<<endl; return 0; }
命运之光 2022-12-30 23:29:17 |
网上有正确代码，考虑的比较全面
- «
- 1
- »