题目描述
翻硬币(详细代码注解)
话不多说 上代码
C++ 代码
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
char replace(char s){
return s == '*' ? 'o' : '*';
}
int main(){
string s1, s2; // s1为初始状态, s2为目标状态
cin >> s1 >> s2;
int count = 0; // 记录硬币翻转次数
for (int i = 0; i < s1.length() - 1; i++) { // 从前往后遍历s1即可
if (s1[i] == s2[i]) //与s2比较 如相等则跳过 (这个判断其实可以不要 直接else}
continue;
else
{
//s1[i] = replace(s1[i]);
// 看了别人的评论 s1[i] 是不需要改动的 只需要改动s1[i+1]即可 因为是从前往后遍历的 s1[i]已经经过了就不会经过第二次
s1[i+1] = replace(s1[i+1]);
count++;
}
}
cout << count << endl;
return 0;
}
答主想到直接从前往后遍历 是因为题目算法标签为 递推
算法思路以及为什么这样做是最少次数的问题 可以参考下面这个题解链接 https://www.acwing.com/solution/content/6674/
新手上路 有错误或别的方法希望各位大佬踩一踩hhhhh