如果通过每次翻转两枚相邻硬币,能从状态一变为状态二,则两个状态之间必定有偶数个不同状态的硬币。
模拟法:
- 从最左侧开始遍历,如果该位置硬币状态与目标不同,就翻动该位置和该位置后面的两枚硬币。
因为题目说了有解,所以遍历到倒数第二枚的时候,所有硬币状态就与目标相同了。
这个方法也有点贪心的思路,每次追求当前位置状态与目标状态一致。我还是喜欢称它为模拟法。
//cpp
#include <iostream>
#include <string>
using namespace std;
const int N = 110;//用不到,看范围就直接写了
int main()
{
string s1, s2;//s1:初始状态,s2:目标状态
int cnt = 0;//记录翻转次数
cin >> s1 >> s2;
for (int i = 0; i < s1.size() - 1; i++)
{
if (s1[i] != s2[i])//第 i 个位置上状态不同,就翻转该位置和后一个位置硬币
{
cnt++;//翻转一次硬币
if (s1[i] == '*') s1[i] = 'o';//翻转 i 位置上的硬币
else s1[i] = '*';
if (s1[i+1] == 'o') s1[i+1] = '*';//翻转 i + 1 位置上的硬币
else s1[i+1] = 'o';
}
}
cout << cnt;//输出翻转次数
}
时间复杂度:遍历了一边输出,时间复杂度是 O(n)。
该思路时间复杂度已是最优,要使起始状态变为目标状态,至少遍历一边来进行判断,时间复杂度最少是 O(n)。
空间复杂度:没有开辟与输入输出有关的空间,空间复杂度是O(1)。
有问题可以直接评论,
觉得不错可以点个赞,点个关注~
其实第i个硬币不需要翻转的,翻转第i+1个硬币就可以了
不是每次都必须翻转两枚硬币么?
是必须翻转两枚,但是不用在代码里面实现,不需要后续遍历,所以感觉就如果遇到不同的了翻转后一枚硬币就可以了
这个思路可以的
有道理
嗯嗯感觉受到了启发
确实
确实不会再影响了。
你说的有道理
家人们,谁懂啊?咱就是说为啥第i个位置不同,反转第i+1个,不用反转第i个啊啊?
不是应该反转第i个,不反转第i+1个么?啊啊啊啊啊QAQ
666
别光扣6啊,告诉我为啥啊QAQ,一整个大无语
因为是从前往后考虑,第i个位置不同时,实际上是需要翻转i和i+1,但第i个位置上的硬币之后不会再考虑了,是否将其翻转不会影响结果,所以在代码里不用实现
哈哈哈,味太浓了
呜呜快一年前的梗了都QAQ
哈哈现在懂了吗,没懂我教你
###这个只要考虑下一个硬币就可以了,不需要考虑上一个硬币,因为你的结果的翻找的次数
简洁
简洁
一条语句造不成多大影响
想不通为啥这样的反转次数最少。。。。/捂脸
这样写可以看作不断将问题缩小,而且对必要反转棋子只操作一次,换言之就是,保证这个棋子被反转过去,不会又被反转回来,这样就一定是最小的
### 牛逼
为什么for (int i = 0; i < s1.size() - 1; i++)这里用sizeof不可以?求大佬解惑
我是派大星,我觉得不错
海绵牛逼
我有一种证明的思路,那就是先比对字符串标记需要修改的位置,翻把所有偶数个连续的反转(到这一步肯定最佳),剩下全都是单独存在互不相邻的待反转点,对于这些不相邻之间的点最快反转个数是x+1(x是中间隔着多少个点),但是有个问题是前面偶数个相邻的反转(比如连续5个反转4个)顺序不同结果也不同,这种之间顺着比对反转似乎就是以让单独存在的点靠的尽可能近的方式来降低翻转次数。
我猜出来是这样反转最小,但是不知道怎么证明,也想不出来其他的反转方式-v-
有证明吗
没太懂为啥
玩AC SABER还没来得及写这题就输了(离谱
这种是比较暴力的解法,一个一个来比对,如果不一样则翻面。
dalao,空间复杂度应该是O(n)吧,开辟了两个长度为n的string
两个字符串是输入,不计入算法空间。
如果写成函数,把输入当做参数传入,函数的空间复杂度是常数级。
懂了,算法空间是O(1),程序空间是O(n),谢谢大佬