360 2020-03-24 笔试第1题
大致思路就是：
一个线性扫描，
记录 s1. s2不等的字符数量的同时，记录s1在这个不等时候，为A，T的数量，
然后返回 min(A1DiffCnt, T1DiffCnt) + diffCnt - min(A1DiffCnt, T1DiffCnt)*2 即可
min(A1DiffCnt, T1DiffCnt)相当于是2个字符交换的次数。
diffCnt - min(A1DiffCnt, T1DiffCnt)*2相当于是字符替换的次数。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int f(string& s1, string& s2)
{
int A1DiffCnt = 0, T1DiffCnt = 0;
int diffCnt = 0;
for (int i = 0; i < s1.size(); ++i)
{
if (s1[i] != s2[i])
{
++diffCnt;
if (s1[i] == 'A') ++A1DiffCnt;
if (s1[i] == 'T') ++T1DiffCnt;
}
}
return min(A1DiffCnt, T1DiffCnt) + diffCnt - min(A1DiffCnt, T1DiffCnt)*2;
}
int main()
{
// 这里可以改成自己输入测一下把，应该没问题；
string s1("ATTT");
string s2("TTAA");
cout << f(s1, s2) << endl;
return 0;
} 不过我实际写得时候一上来就想套成牛客上面那个源字符串通过 增/删/替换 变成目标字符串的 dp题了emmm所以就xjb a了45%。
后面下来发现就根本不是dp，一个线性扫描就行了emmm。
按难度来说应该算是easy题把，可惜笔试时候没a出来。
分享一下给各位牛油，顺便为自己祈福！！！
投递中国科学技术大学等公司10个岗位