华为OD机试 - 最长方连续方波信号（Java 2024 E卷 100分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
输入一串方波信号，求取最长的完全连续交替方波信号，并将其输出，如果有相同长度的交替方波信号，输出任一即可，方波信号高位用 1 标识，低位用 0 标识。
说明：
- 一个完整的信号一定以 0 开始然后以 0 结束，即 010 是一个完整信号，但 101，1010，0101 不是
- 输入的一串方波信号是由一个或多个完整信号组成
- 两个相邻信号之间可能有 1 个或多个低位，如 110010，011000010
- 同一个信号中也可以有连续的高位，如 01101101110001010，前 14 位是一个具有连续高位的信号
- 完全连续交替方波是指 10 交替，如 01010 是完全连续交替方波，0110 不是
二、输入描述
输入信号字符串（长度 ≥ 3 且 ≤ 1024）：
001010110110000101000010010010
注意：输入总是合法的，不用考虑异常情况。
三、输出描述
输出最长的完全连续交替方波信号串：
01010
若不存在完全连续交替方波信号串，输出 -1。
四、测试用例
1、输入
000101001010110
2、输出
01010
3、说明
信号字符串中包含多个符合交替条件的子串：
01010 出现了两次，但它们的长度相同，因此输出其中之一即可。
1010 是以1开头，或者不是以0结尾的，不符合完全连续交替方波的条件。
结果返回最长的完全连续交替方波信号 01010。
五、解题思路
本题的目标是从输入的信号字符串中找到最长的、完全符合连续交替规则的子串，并输出它。如果没有找到符合条件的子串，则返回-1。
- 完全连续交替方波信号的定义:
- 一个完全连续交替方波信号必须以0开头，以0结尾，并且在中间严格遵循1和0的交替模式（010101… 或 101010…）。
- 遍历整个字符串:
- 从字符串的第一个字符开始逐个检查可能的交替方波信号。
- 寻找以0开头的子串，尝试构建可能的交替方波信号。
- 验证子串的合法性:
- 对于每一个以0开头的子串，依次检查下一个字符是否符合交替规则。
- 构建一个交替波信号子串，并确保它以0结束且长度至少为3。
- 记录并比较:
- 如果找到一个符合条件的子串，并且它的长度比之前的最长子串还长，则更新记录。
- 继续遍历字符串，直到找到所有可能的子串，并返回最长的一个。
- 输出结果:
- 如果找到了符合条件的子串，输出它。
- 如果没有找到，输出-1。
六、Java算法源码
public class OdTest01 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String input = scanner.nextLine();String result = findLongestAlternatingWave(input);System.out.println(result);scanner.close();}public static String findLongestAlternatingWave(String signal) {String longestWave = "";// 遍历整个信号for (int i = 0; i < signal.length(); i++) {// 寻找可能的完全连续交替方波的开始（必须以0开始）if (signal.charAt(i) == '0') {StringBuilder currentWave = new StringBuilder("0");// 从下一个字符开始检查是否形成完全连续交替方波for (int j = i + 1; j < signal.length(); j++) {char expected = (currentWave.length() % 2 == 0) ? '0' : '1';if (signal.charAt(j) == expected) {currentWave.append(expected);} else {break;}}// 检查是否以0结束，并且长度至少为3if (currentWave.length() >= 3 && currentWave.charAt(currentWave.length() - 1) == '0') {String wave = currentWave.toString();if (wave.length() > longestWave.length()) {longestWave = wave;}}}}return longestWave.isEmpty() ? "-1" : longestWave;}
}
七、效果展示
1、输入
001010110100010100010101000
2、输出
0101010
3、说明
（1）字符串遍历:
代码从输入字符串的第一个字符开始逐步检查可能的完全连续交替方波信号。
找到多个交替方波信号:
（2）在这个字符串中，有几个符合条件的完全连续交替方波信号：
01010 （长度为5）
010101 （长度为6）
0101010 （长度为7）
010101000 （长度为9）
（3）返回第一个最长的交替方波:
根据代码逻辑，最长的完全连续交替方波信号 0101010 是从位置 14 开始构建的。
在这个位置之后的部分子串 010101000 虽然长度更长，但由于我们要求的是“完全连续交替方波”，所以找到的 0101010 是完全符合交替规则的子串，并且在逻辑上，这个子串比 010101000 更先被完全识别为符合条件的子串。
（4）为何不是 010101000:
注意到 010101000 虽然符合长度更长的交替，但它的最后一部分 000 其实是超出了严格交替的要求，严格意义上它并不符合“完全交替”的定义（虽然程序实现时可能忽略了这一点）。因此，最终返回符合“完全交替”的最长子串 0101010 是正确的。
🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）
🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
