洛谷P8597

洛谷 P8597

题目描述

给定两个字符串 a 和 b，其中 a 表示初始状态，b 表示目标状态。字符串由字符 '*' 和 'o' 组成。每次操作可以选择一个位置 i，将 a[i] 修改为 b[i]，同时翻转 a[i+1]（即 '*' 变为 'o'，'o' 变为 '*'）。请你计算将 a 转换为 b 所需的最少操作次数。

示例

示例 1

输入:

a = "*o**o*"
b = "*oo*o*"

输出:

解释:

第一次操作：选择位置 1，将 a[1] 修改为 b[1]，同时翻转 a[2]。
第二次操作：选择位置 3，将 a[3] 修改为 b[3]，同时翻转 a[4]。

示例 2

输入:

a = "*o*o*"
b = "*o*o*"

输出:

解释:

初始状态和目标状态相同，无需操作。

思路分析

问题核心

我们需要通过最少的操作将字符串 a 转换为字符串 b，每次操作会影响当前字符和下一个字符。

思路拆解

遍历字符串：
- 从左到右遍历字符串 a，逐个字符与 b 进行比较。
操作计数：
- 如果当前字符 a[i] 与 b[i] 不同，则进行操作，并翻转下一个字符。
输出结果：
- 输出操作次数。

代码段

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String a = sc.next();String b = sc.next();int ans = 0;char[] A = a.toCharArray();char[] B = b.toCharArray();for (int i = 0; i < A.length - 1; i++) {if (A[i] == B[i])continue;A[i] = B[i];if (A[i + 1] == '*')A[i + 1] = 'o';elseA[i + 1] = '*';ans++;}System.out.println(ans);}
}

在这里插入图片描述

代码逐行讲解

输入处理：

Scanner sc = new Scanner(System.in);
String a = sc.next();
String b = sc.next();

使用 Scanner 读取输入字符串 a 和 b。

初始化变量：
```
int ans = 0;
char[] A = a.toCharArray();
char[] B = b.toCharArray();
```
- 初始化操作计数器 ans，并将字符串转换为字符数组 A 和 B。

遍历字符串：

for (int i = 0; i < A.length - 1; i++) {if (A[i] == B[i])continue;A[i] = B[i];if (A[i + 1] == '*')A[i + 1] = 'o';elseA[i + 1] = '*';ans++;
}

遍历字符数组 A，逐个字符与 B 进行比较。
如果当前字符 A[i] 与 B[i] 不同，则进行操作，并翻转下一个字符。

输出结果：
```
System.out.println(ans);
```
- 输出操作次数。

复杂度分析

时间复杂度

遍历字符串的时间复杂度为 O(n)，其中 n 是字符串的长度。

空间复杂度

使用了字符数组存储字符串，空间复杂度为 O(n)。

总结的知识点

字符串处理：
- 使用 toCharArray 将字符串转换为字符数组。
遍历与操作：
- 通过遍历字符串逐个字符进行比较和操作。
条件判断：
- 根据条件判断是否进行操作。

整合

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String a = sc.next();String b = sc.next();int ans = 0;char[] A = a.toCharArray();char[] B = b.toCharArray();for (int i = 0; i < A.length - 1; i++) {if (A[i] == B[i])continue;A[i] = B[i];if (A[i + 1] == '*')A[i + 1] = 'o';elseA[i + 1] = '*';ans++;}System.out.println(ans);}
}