【华为OD-E卷 - 最长方连续方波信号 100分（python、java、c++、js、c）】
【华为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
输出：
01010
说明 输入信号串中有三个信号：
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 # 当前交替波长度为 1
else:
state = 0 # 继续等待 '0'
current_len = 0 # 重置当前波长
elif state == 1: # 状态 1，等待遇到 '1'
if char == "1":
state = 2 # 转移到状态 2（遇到 '1'）
current_len += 1 # 当前交替波长度加 1
else:
state = 1 # 如果遇到 '0'，重新开始交替波
start = i # 更新起始位置
current_len = 1 # 当前波长重置为 1
elif 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，则返回 -1
if 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;
}
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏