C++代码 –> 考察点 递归
#include<iostream>
#include<string>
using namespace std;
string s1,s2; // s1 为初始状态, s2为目标状态
void turn(int i) //翻转函数,将s1 的 第 i - 1 个字符翻转
{
if(s1[i] == 'o') s1[i] = '*';
else s1[i] = 'o';
}
int main()
{
cin >> s1 >> s2;
int cnt = 0;
for(int i = 0; i < s1.size(); ++i)
if(s1[i] != s2[i]) ++cnt, turn(i), turn(i+1);
cout << cnt << endl;
return 0;
}
题目思路
题目属于经典的开关题目,第一眼让人想到bfs,但实际并不需要,请看下面细说
这道题有两个隐藏信息:
(1) 操作的顺序并不影响结果 –> 不影响最少的操作次数,即从左往右检测不同操作和从右往左检测不同最终结果相同。
(2) 对于每个硬币的翻转操作只有0 / 1 , 因为如果是2次那就是原地踏步,且这样就不满足最少的操作次数。 而且题目的输入一定保证有解的情况下,故达成目标状态每个硬币的翻转操作一定保证只有一次。
故从左边往右边看起
对于最左边的第一个硬币 是否被翻转只与其与目标是否相关,因为对于左边第一个只有一种操作可以影响它。对于第二个硬币,不管第一个硬币有没有翻转,此时遍历到第二个硬币肯定已经保证了第一个硬币与目标状态是相同的,故翻转两个硬币的操作肯定此时不会翻转当前硬币和前一个硬币,故能改变第二个硬币状态的操作都只有一种。依次类推,由于从左到右遍历,对于每一个硬币都不能再次改变其前一个的状态,故改变当前硬币状态的操作只剩下一种,若相同,则继续遍历下一个硬币状态,若不同想要与目标相同肯定只能翻转当前硬币和其下一个硬币
因为这里存入的是string ,这里写成 i和i均可,因为都是循环结束之后进行的进行递增操作,表示字符向右遍历,这里的话是只是个人代码风格的问题,但是 i和 i在某些情况下却有不一样的结果,故有时要分清情况,但这里二者效果一样
请问 为什么 是 ++i