【华为OD-E卷 - 最长方连续方波信号 100分（python、java、c++、js、c）】

题目

输入一串方波信号，求取最长的完全连续交替方波信号，并将其输出，如果有相同长度的交替方波信号，输出任一即可，方波信号高位用1标识，低位用0标识，如图：
在这里插入图片描述
说明：

一个完整的信号一定以0开始然后以0结尾，即010是一个完整信号，但101，1010，0101不是输入的一串方波信号是由一个或多个完整信号组成两个相邻信号之间可能有0个或多个低位，如0110010，011000010 同一个信号中可以有连续的高位，如01110101011110001010，前14位是一个具有连续高位的信号完全连续交替方波是指10交替，如01010是完全连续交替方波，0110不是

输入描述

输入信号字符串（长度 >= 3 且 <= 1024）

注：输入总是合法的，不用考虑异常情况

输出描述

输出最长的完全连续交替方波信号串

若不存在完全连续交替方波信号串，输出 -1

备注

用例

用例一：

输入：

00101010101100001010010

输出：

说明输入信号串中有三个信号：

0 010101010110(第一个信号段)

00 01010(第二个信号段)

010(第三个信号段)

第一个信号虽然有交替的方波信号段，但出现了11部分的连续高位，不算完全连续交替方波，

在剩下的连续方波信号串中01010最长

python解法

解题思路：
问题描述：

输入一个由字符 ‘0’ 和 ‘1’ 组成的字符串。
查找最长的 “交替波” 子串，该子串必须满足以下条件：
至少包含 3 个字符。
‘0’ 和 ‘1’ 必须交替出现（例如，01010 是合法的交替波，而 0110 不是）。
如果没有满足条件的子串，输出 “-1”。
实现步骤：

使用状态机来检测字符串中的交替波子串。
定义 3 个状态：
state = 0：初始状态，等待遇到 ‘0’ 开始波形。
state = 1：遇到 ‘0’，等待遇到 ‘1’ 形成波形。
state = 2：遇到 ‘1’，等待遇到 ‘0’ 扩展波形。
遍历字符串，更新状态并记录波形的起始位置和长度。
如果当前子串比之前找到的最长子串更长，则更新结果。
遍历结束后，返回最长的交替波子串。
输入输出：

输入：一个只包含 ‘0’ 和 ‘1’ 的字符串。
输出：
如果存在符合条件的交替波子串，返回其内容。
否则，返回 “-1”

# 读取输入字符串
s = input()def longestAlternatingWave(s):max_len = 0  # 记录最长交替波的长度result = "-1"  # 存储最终结果（默认为 -1，表示不存在交替波）current_len = 0  # 当前交替波的长度start = 0  # 当前交替波的起始位置state = 0  # 状态机的初始状态：0 表示等待遇到 '0'# 遍历字符串中的每个字符for i, char in enumerate(s):if state == 0:  # 初始状态，等待遇到 '0'if char == "0":state = 1  # 转移到状态 1（遇到 '0'）start = i  # 记录交替波的起始位置current_len = 1  # 当前交替波长度为 1else:state = 0  # 继续等待 '0'current_len = 0  # 重置当前波长elif state == 1:  # 状态 1，等待遇到 '1'if char == "1":state = 2  # 转移到状态 2（遇到 '1'）current_len += 1  # 当前交替波长度加 1else:state = 1  # 如果遇到 '0'，重新开始交替波start = i  # 更新起始位置current_len = 1  # 当前波长重置为 1elif state == 2:  # 状态 2，等待遇到 '0'if char == "0":state = 1  # 转移回状态 1（遇到 '0'）current_len += 1  # 当前交替波长度加 1# 如果当前波长大于记录的最大波长，更新结果if current_len > max_len:max_len = current_len  # 更新最大波长result = s[start:i+1]  # 更新结果为当前交替波子串else:state = 0  # 如果遇到 '1'，重新开始波形current_len = 0  # 重置波长# 如果找到的最长交替波长度小于 3，则返回 -1if max_len < 3:return "-1"return result  # 返回最长交替波子串# 调用函数并输出结果
print(longestAlternatingWave(s))

java解法

解题思路
问题描述：

输入一个仅包含 ‘0’ 和 ‘1’ 的字符串。
查找其中最长的 “交替波” 子串。
“交替波” 的定义是以 01 模式交替出现的字符串，且以 0 结尾，例如：01010、010。
如果没有找到符合条件的子串，输出 -1。
解法设计：

使用类 WaveProcessor 封装处理逻辑。
遍历输入字符串，构造当前的波形子串，检测是否符合波形规则并更新最长波形。
波形规则通过正则表达式匹配，确保子串是有效波形。
关键方法设计：

getLongestWave：
遍历输入字符串构造波形。
每次遇到 ‘0’ 时，检测当前波形是否已完成。
如果当前波形有效且比最长波形更长，则更新最长波形。
isWaveTerminated：
检查波形是否以 ‘0’ 结尾，表示波形可能完成。
isValidWave：
使用正则表达式 ^(01)+0$ 检查波形是否为有效的交替波。
输入输出：

输入：
一个字符串，仅包含 ‘0’ 和 ‘1’。
输出：
最长的交替波子串；如果没有找到，输出 -1

import java.util.Scanner;
import java.util.regex.Pattern;public class Main {public static void main(String[] args) {// 创建 Scanner 对象用于读取输入Scanner sc = new Scanner(System.in);// 读取用户输入的信号字符串String input = sc.nextLine();// 创建 WaveProcessor 对象处理输入信号WaveProcessor processor = new WaveProcessor(input);// 获取最长的交替波子串String result = processor.getLongestWave();// 输出结果System.out.println(result);}
}// 波形处理类，封装交替波查找的逻辑
class WaveProcessor {private final String signal; // 输入的信号字符串// 定义一个正则表达式，用于匹配有效的交替波private static final Pattern VALID_WAVE = Pattern.compile("^(01)+0$");// 构造方法，初始化信号字符串public WaveProcessor(String signal) {this.signal = signal;}/*** 查找最长的交替波子串* @return 最长的交替波子串，如果不存在返回 "-1"*/public String getLongestWave() {StringBuilder currentWave = new StringBuilder(); // 当前正在构造的波形String longestWave = "-1"; // 用于存储最长波形，默认值为 "-1"int maxLength = 0; // 记录最长波形的长度// 遍历输入信号字符串的每个字符for (int i = 0; i < signal.length(); i++) {char currentChar = signal.charAt(i); // 当前字符if (currentChar == '0') { // 每当遇到 '0'// 检查当前波形是否以 '0' 终止if (isWaveTerminated(currentWave)) {// 如果波形有效且长度大于已记录的最长波形if (isValidWave(currentWave) && currentWave.length() > maxLength) {longestWave = currentWave.toString(); // 更新最长波形maxLength = currentWave.length(); // 更新最长波形的长度}// 当前波形无效或已完成，重置构造波形currentWave.setLength(0);}}// 将当前字符追加到波形中currentWave.append(currentChar);}// 检查遍历结束后，最后一个波形是否为最长波形if (isValidWave(currentWave) && currentWave.length() > maxLength) {longestWave = currentWave.toString(); // 更新最长波形}// 返回最长波形，如果没有找到，返回默认值 "-1"return longestWave;}/*** 检查当前波形是否以 '0' 终止* @param wave 当前构造的波形* @return 如果以 '0' 终止，返回 true，否则返回 false*/private boolean isWaveTerminated(StringBuilder wave) {return wave.length() > 0 && wave.charAt(wave.length() - 1) == '0';}/*** 检查波形是否符合交替波的规则* @param wave 当前构造的波形* @return 如果波形符合规则，返回 true，否则返回 false*/private boolean isValidWave(StringBuilder wave) {return VALID_WAVE.matcher(wave).find();}
}

C++解法

解题思路

更新中

C解法

解题思路

更新中

JS解法

解题思路
问题描述：

输入是一个仅包含 ‘0’ 和 ‘1’ 的字符串，称为信号。
查找字符串中最长的 “交替波” 子串。
交替波的定义：
必须以 ‘01’ 交替出现。
必须以 ‘0’ 结尾，例如：01010。
如果找不到满足条件的交替波，返回 “-1”。
实现逻辑：

遍历字符串，查找符合交替波条件的子串。
当遇到字符 ‘0’ 时，检查从该字符开始的可能交替波。
用一个指针 j 扫描每对 ‘01’，直到交替波终止（即下一个字符不是 ‘1’ 或子串结束）。
如果当前交替波以 ‘0’ 结尾且长度大于已记录的最大长度，更新结果。
重复此过程直到遍历完整个字符串。
输入输出：

输入：
一行字符串，仅包含字符 ‘0’ 和 ‘1’。
输出：
最长的交替波子串；如果没有找到符合条件的交替波，输出 “-1”。
时间复杂度：

O(n)：字符串只需要遍历一次（使用双指针）。
空间复杂度：O(1)，只使用常量额外空间。

// 引入 Node.js 的 readline 模块用于处理输入输出
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});// 读取输入行并调用核心函数
rl.on("line", (line) => {console.log(findLongestWave(line)); // 调用函数并输出结果
});/*** 查找最长的交替波子串* @param {string} signal 输入信号字符串* @returns {string} 最长的交替波子串，如果不存在返回 "-1"*/
function findLongestWave(signal) {let maxLength = 0; // 记录最长交替波的长度let result = "-1"; // 存储最终结果，默认为 "-1"let i = 0; // 指针 i，用于遍历字符串while (i < signal.length) {// 检查是否从当前字符开始形成交替波if (signal[i] === '0') {let j = i; // 指针 j，用于检测交替波的结束// 检查每对 '01' 是否符合交替波规则while (j + 1 < signal.length && signal[j] === '0' && signal[j + 1] === '1') {j += 2; // 每次跳过 '01' 两个字符}// 如果交替波以 '0' 结束，则形成一个有效波if (j < signal.length && signal[j] === '0') {// 提取当前交替波子串let currentWave = signal.slice(i, j + 1);// 如果当前波的长度超过已记录的最大长度，更新结果if (currentWave.length > maxLength) {maxLength = currentWave.length; // 更新最大长度result = currentWave; // 更新最长波子串}}// 移动 i 到交替波结束的下一个位置i = j + 1;} else {// 如果当前字符不是 '0'，直接跳到下一个字符i++;}}// 返回最长的交替波子串，如果不存在，返回默认值 "-1"return result;
}