翻硬币
问题描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。
比如,可能情形是:**oo***oooo
如果同时翻转左边的两个硬币,则变为:oooo***oooo
现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两
个硬币,那么对特定的局面,最少要翻动多少次呢?
我们约定:把翻动相邻的两个硬币叫做一步操作,那么要求:
输入格式
两行等长的字符串,分别表示初始状态和要达到的目标状态。每行的长度<1000
输出格式
一个整数,表示最小操作步数。
样例输入 1
**********
o****o****
样例输出 1
5
样例输入 2
*o**o***o***
*o***o**o***
样例输出 2
1
理解与思路
我一看这一题下意识就是用数组去存数据,然后在挨个比较,但是操作起来可能会有那么一点点难和复杂
然后我又想能不能有一个方法是操作起来不难的而且复杂程度不高的?就去百度了,果然有一种方法
这位博主的思路就是用另外一个数组去存数据,但存的数据不是用符号来的,是用数字的
然后这个思路也非常有意思,它不是两两交换吗?然后博主就用另一个数组存 1 和 - 1,如果数据不一样的就改变符号
再循环遍历,最后得出的结果数据肯定是一样的,而且这也是最快、最简洁的一种方法
我写的代码如下
c++
#include <iostream>
#include <string>
using namespace std;
void main(){
string s1;
string s2;
int p1[1000];
int p2[1000];
int sum = 0;
cin>>s1;
cin>>s2;
int i = 0;
//把输入的数据转换成数字来计算
for(i;i<s1.length();i++){
if(s1[i]==‘*‘){
p1[i]=1;
}else if(s1[i]==‘o‘){
p1[i]=-1;
}
if(s2[i]==‘*‘){
p2[i]=1;
}else if(s2[i]=‘o‘){
p2[i]=-1;
}
}
//计算比较输入的数据
for(i = 0;i<s1.length()-1;i++){
if(p1[i] != p2[i]){
sum++;
p1[i]= - p1[i];
p1[i+1] = - p1[i+1];
}
}
cout<<sum;
return ;
}
JAVA
import java.util.Scanner;
public class coin {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s1 = in.nextLine();
String s2 = in.nextLine();
int[] p1 = new int[1000];
int[] p2 = new int[1000];
int sum = 0;
//把输入的数据转换成数字来计算
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i)== ‘*‘) {
p1[i] = 1;
} else if (s1.charAt(i) == ‘o‘) {
p1[i] = -1;
}
if (s2.charAt(i) == ‘*‘) {
p2[i] = 1;
} else if (s2.charAt(i) == ‘o‘) {
p2[i] = -1;
}
}
//计算比较输入的数据
for (int i = 0; i < s1.length() - 1; i++) {
if (p1[i] != p2[i]) {
sum++;
p1[i] = -p1[i];
p1[i + 1] = -p1[i + 1];
}
}
System.out.print(sum);
}
}