每日算法练习Day03
题目来源
U535982 C-小梦的AB交换 - 洛谷
题目描述
小梦有一个长度为 2∗n 的 AB 串 s，即 s 中只包含 "A" 和 "B" 两种字符，且其中恰好有 n 个 "A" 和 n 个 "B"。
他可以对 s 执行以下操作：
∙ 选择 i,j (1≤i,j≤2⋅n,i=j)，并交换 si 和 sj。
他想知道，需要至少多少次操作，才能使得 s 满足相邻的字符不相同，请你帮他算一算吧。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 T，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行一个正整数 n，表示 s 长度的一半。
第二行一个长度为 2∗n 的字符串 s，保证只由 "A", "B" 两种字符构成。
输出格式
对于每组测试数据：
在单独的一行输出一个整数，表示最少进行的操作次数。
输入输出样例
输入 #1复制
2 3 AAABBB 3 ABAABB
输出 #1复制
1 1
说明/提示
【样例 1 解释】
交换 s2=A 和 s5=B，得到 s= "ABABAB"，满足题意，一次交换即可。
【数据范围】
令 N 表示 T 组数据中 n 的总和。
对于 50% 的数据有：T=1,1≤N≤3。
对于所有的测试数据有： 1≤T≤100,1≤N≤106。
题解
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); // 读取测试数据组数 while (T-- > 0) { int n = sc.nextInt(); // 每组数据的n String s = sc.next(); // 每组数据的字符串s // 构建两种合法的交替字符串： // 形式1：B开头，交替排列（B A B A...） StringBuilder pattern1 = new StringBuilder(); // 形式2：A开头，交替排列（A B A B...） StringBuilder pattern2 = new StringBuilder(); for (int i = 0; i < 2 * n; i++) { if (i % 2 == 0) { // 偶数位（从0开始） pattern1.append('B'); pattern2.append('A'); } else { // 奇数位 pattern1.append('A'); pattern2.append('B'); } } // 计算原字符串与两种形式的差异数，交换次数=差异数/2 int cost1 = calcDiff(s, pattern1.toString()); int cost2 = calcDiff(s, pattern2.toString()); // 输出最小交换次数 System.out.println(Math.min(cost1, cost2)); } sc.close(); } // 计算原字符串与目标模式的差异数，返回交换次数（差异数/2） private static int calcDiff(String s, String pattern) { int diff = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != pattern.charAt(i)) { diff++; } } return diff / 2; }1. 先获取数据组数
2.然后我们可以用循环来获取数据
3.建立两种模式来实现这个字母不同的结果，最后再比较这个操作过后的字符串和原来的字符串的区别即可
注释：
s.charAt(i)是获取数组中对应的字母