游戏网站外链建设,2020广东黄页,企业系统包括哪些系统,wordpress 4.9 中文版问题描述
在生物学中#xff0c;DNA 序列的相似性常被用来研究物种间的亲缘关系。现在我们有两条 DNA 序列#xff0c;每条序列由 A、C、G、T 四种字符组成#xff0c;长度相同。但是现在我们记录的 DNA 序列存在错误#xff0c;为了严格满足 DNA 序列的碱基互补配对即 A …问题描述
在生物学中DNA 序列的相似性常被用来研究物种间的亲缘关系。现在我们有两条 DNA 序列每条序列由 A、C、G、T 四种字符组成长度相同。但是现在我们记录的 DNA 序列存在错误为了严格满足 DNA 序列的碱基互补配对即 A - T 和 C - G我们需要依据第一条 DNA 序列对第二条 DNA 序列进行以下操作 选择第二条 DNA 序列的任意两个位置交换他们的字符。 选择第二条 DNA 序列任意一个位置将其字符替换为 A、C、G、T 中的任何一个。
需要注意的是每个位置上的碱基只能被操作一次
你的任务是通过最小的操作次数使第二条 DNA 序列和第一条 DNA 序列互补。并且已知初始两条 DNA 序列长度均为 N。
输入格式
第一行包含一个整数 N0N≤1000)表示 DNA 序列的长度。
接下来的两行每行包含一个长度为 N 的字符串表示两条 DNA 序列。
输出格式
输出一个整数表示让第二条 DNA 序列和第一条 DNA 序列互补所需的最小操作次数。
#include iostream
#include vector
#include stringusing namespace std;
const int N 1e3 10;
string str1, str2;bool isMatch(char ch1, char ch2) {return (ch1 A ch2 T) || (ch1 C ch2 G) ||(ch1 T ch2 A) || (ch1 G ch2 C);
}int findMinSwap() {vectorint unMatch;int ans 0;// 记录未匹配的位置for (int i 0; i str1.length(); i) {if (!isMatch(str1[i], str2[i]))unMatch.push_back(i);}/** 字符串1的i位置与字符串2的j位置匹配* 字符串1的j位置与字符串2的j位置匹配* 进行交换* */for (int i 0; i unMatch.size(); i) {for (int j i 1; j unMatch.size(); j) {if (isMatch(str1[unMatch[i]], str2[unMatch[j]]) isMatch(str1[unMatch[j]], str2[unMatch[i]])) {swap(str2[unMatch[i]], str2[unMatch[j]]);ans;unMatch.erase(unMatch.begin() j); // 注意这里一定要先释放j位置 如果先释放i位置 那么j位置会向前移动一个位置 导致错误unMatch.erase(unMatch.begin() i);if(i)i--;break;}}}// ans 加上没有交换的位置只能改变碱基ans unMatch.size();return ans;
}int main() {int n;cin n;cin str1 str2;cout findMinSwap() endl;
}
