洛谷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*"

输出:

2

解释:

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

---

示例 2

输入:

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

输出:

0

解释:

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

---

思路分析

问题核心

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

思路拆解

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

---

代码段

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);}
}

---

代码逐行讲解

1. 输入处理：

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

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

2. 初始化变量：

   int ans = 0;
   char[] A = a.toCharArray();
   char[] B = b.toCharArray();
   

   • 初始化操作计数器 ans，并将字符串转换为字符数组 A 和 B。

3. 遍历字符串：

   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] 不同，则进行操作，并翻转下一个字符。

4. 输出结果：

   System.out.println(ans);
   

   • 输出操作次数。

---

复杂度分析

时间复杂度

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

空间复杂度

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

---

总结的知识点

1. 字符串处理：

   • 使用 toCharArray 将字符串转换为字符数组。

2. 遍历与操作：

   • 通过遍历字符串逐个字符进行比较和操作。

3. 条件判断：

   • 根据条件判断是否进行操作。

---

整合

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);}
}

---

总结

通过遍历和操作，能够高效地将字符串 a 转换为字符串 b，并计算所需的最少操作次数。