动易 手机网站,wordpress怎么在底部调用友情链接,百度seo搜搜,微信小程序注册代码题目
有一个长度为 N 的字符串 S#xff0c;其中的每个字符要么是 B#xff0c;要么是 E。
我们规定 S 的价值等于其中包含的子串 BB 以及子串 EE 的数量之和。
例如#xff0c;BBBEEE 中包含 22 个 BB 以及 22 个 EE#xff0c;所以 BBBEEE 的价值等于 44。
我们想要计…题目
有一个长度为 N 的字符串 S其中的每个字符要么是 B要么是 E。
我们规定 S 的价值等于其中包含的子串 BB 以及子串 EE 的数量之和。
例如BBBEEE 中包含 22 个 BB 以及 22 个 EE所以 BBBEEE 的价值等于 44。
我们想要计算 S 的价值不幸的是在我们得到 S 之前约翰将其中的一些字符改为了 F。
目前我们只能看到改动后的字符串 S对于其中的每个 F我们并不清楚它之前是 B 还是 E。
请你计算改动前的 S 有多少种可能的价值并将所有可能价值全部输出。
输入格式
第一行包含一个整数 N
第二行包含改动后的字符串 S
输出格式
第一行输出一个整数 K表示改动前的 S 的可能价值的数量。
接下来 K 行按照升序顺序每行输出一个可能价值。
数据范围
1≤N≤2×10^5
输入样例1
4
BEEF输出样例1
2
1
2输入样例2
9
FEBFEBFEB输出样例2
2
2
3输入样例3
10
BFFFFFEBFE输出样例3
3
2
4
6思路与代码
这道题没有模板可以套所以我们要分类讨论。如果全部都是F的话证明价值从0-n都可以。如果不是就更具体讨论了。具体讨论如下这里的low地点和high高点分别是最小价值和最高价值 寻找第一个和最后一个非F字符的位置 使用两个指针 l 和 r分别初始化为字符串的开头和结尾。while 循环找到第一个非 ‘F’ 的字符的位置分别赋给 lr 计算低点 创建一个 StringBuilder 对象 str将其初始化为输入字符串 s。从 l 到 r 的范围内遍历字符串。如果当前字符是 ‘F’则将其修改为 ‘B’ 或 ‘E’使得相邻字符不相同。如果当前字符与前一个字符相同即 str.charAt(i) str.charAt(i - 1)则增加 low 计数。 计算高点 从 l 到 r 的范围内遍历字符串。如果当前字符是 ‘F’则将其修改为与前一个字符相同。如果当前字符与前一个字符相同即 str.charAt(i) str.charAt(i - 1)则增加 high 计数。 计算结束的范围和步长 计算从 l 到 r 之间的字符个数即 ends l n - 1 - r。如果 ends 大于 0说明字符串在两端有一些 ‘F’需要计入 high 中此时将 high 增加 ends并将步长 d 设置为 1。 输出结果 计算 high - low 的结果除以步长 d并加上 1得到最终输出的范围。从 low 到 high 按照步长 d 遍历输出结果
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 读取输入int n scanner.nextInt();String s scanner.next();if (s.equals(new String(new char[n]).replace(\0, F))) {// 如果全是F输出整个范围System.out.println(n);for (int i 0; i n; i) {System.out.println(i);}} else {// 寻找第一个和最后一个非F字符的位置int l 0, r n - 1;while (s.charAt(l) F) l;while (s.charAt(r) F) r--;int low 0, high 0;StringBuilder str new StringBuilder(s);// 计算低点for (int i l; i r; i) {if (str.charAt(i) F) {if (str.charAt(i - 1) B) str.setCharAt(i, E);else str.setCharAt(i, B);}if (i l str.charAt(i) str.charAt(i - 1)) low;}// 重置字符串str new StringBuilder(s);// 计算高点for (int i l; i r; i) {if (str.charAt(i) F) str.setCharAt(i, str.charAt(i - 1));if (i l str.charAt(i) str.charAt(i - 1)) high;}// 计算结束的范围和步长int ends l n - 1 - r, d 2;if (ends 0) {high ends;d 1;}// 输出结果System.out.println((high - low) / d 1);for (int i low; i high; i d)System.out.println(i);}}
}
接着我们结合第一个测试用例来理解这个代码
输入样例1
4
BEEF输出样例1
2
1
2结合用例理解
执行到这串代码的时候
while (s.charAt(l) F) { l;
}
while (s.charAt(r) F) { r--;
}l还是0r变为2
计算低点 执行到计算低点的代码时候当i2时进来low所以low1 然后执行到i3时因为已经把F替换为跟前面一个字符不同的字符所以进不到low的判断
计算高点
当i2时进入到了high判断里high了high1
计算ends
主要是为了计算左右两端的F个数因为左右两端有多少个 ‘F’ 的原因是我们希望每个 ‘F’ 都能够独立地成为一个分组。在计算高点 high 时我们希望每个 ‘F’ 能够单独计数因此需要考虑两端的 ‘F’ 个数所以在这里计算出ends1然后d就被设置为1步长为1高点就再加上1
输出
(high - low) / d 1 的计算是为了确定最终输出的分组数量步长 d 表示每次增加的索引步长保证了每个 ‘F’ 只能被计数一次
