E卷-最长连续方波信号(100分)
最长连续方波信号
问题描述
输入一串方波信号，求取最长的完全连续交替方波信号，并将其输出。如果有相同长度的交替方波信号，输出任一即可。方波信号高位用 1 标识，低位用 0 标识。
说明：
- 一个完整的信号一定以 0 开始然后以 0 结尾，即 010 是一个完整信号，但 101，1010，0101 不是。
- 输入的一串方波信号是由一个或多个完整信号组成。
- 两个相邻信号之间可能有 0 个或多个低位，如 0110010，011000010。
- 同一个信号中可以有连续的高位，如 01110101011110001010，前 14 位是一个具有连续高位的信号。
- 完全连续交替方波是指 10 交替，如 01010 是完全连续交替方波，0110 不是。
示意图：
连续方波信号： 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0
|___|¯¯¯¯¯¯¯|___|¯|___|¯|___|_______|¯|___|¯|___|_______|
二进制表示： 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0
输入格式
输入一行，为信号字符串（长度 且
）。
注：输入总是合法的，不用考虑异常情况。
输出格式
输出一行，为最长的完全连续交替方波信号串。 若不存在完全连续交替方波信号串，输出 -1。
样例输入
00101010101100001010010
样例输出
01010
样例解释
输入信号串中有三个信号：
- 0 010101010110（第一个信号段）
- 00 01010（第二个信号段）
- 010（第三个信号段）
第一个信号虽然有交替的方波信号段，但出现了 11 部分的连续高位，不算完全连续交替方波。在剩下的连续方波信号串中，01010 最长。
数据范围
- 输入字符串长度：
题解
这道题的核心在于识别和提取完全连续交替的方波信号。解题思路如下：
- 遍历输入字符串，将其分割成多个以 0 开始和结束的信号段。
- 对每个信号段，检查是否为完全连续交替的方波信号。
- 记录并更新最长的完全连续交替方波信号。
关键点在于理解什么是有效的信号段和完全连续交替的方波：
- 有效信号段：以 0 开始，以 0 结束。
- 完全连续交替方波：形如 (01)+ 0 的模式。
使用正则表达式 ^(01)+0$ 可以很方便地匹配完全连续交替的方波信号。时间复杂度为 O(n)，其中 n 是输入字符串的长度。考虑到输入长度最大为 1024，这个解法的效率是可以接受的。
参考代码
- Python
import re
def find_longest_alternating_wave(signal):
# 正则表达式模式，匹配完全连续交替的方波信号
pattern = re.compile(r'^(01)+0$')
max_length = 0
longest_wave = '-1'
current_wave = ''
for char in signal:
if char == '0':
if current_wave and current_wave[-1] == '0':
# 检查当前波形是否是完全连续交替的，并更新最长波形
if pattern.match(current_wave) and len(current_wave) > max_length:
max_length = len(current_wave)
longest_wave = current_wave
current_wave = ''
current_wave += char
# 检查最后一个波形
if pattern.match(current_wave) and len(current_wave) > max_length:
longest_wave = current_wave
return longest_wave
# 读取输入
signal = input().strip()
# 查找最长的完全连续交替方波信号并输出
print(find_longest_alternating_wave(signal))
- C
// 部分通过，后续会完善
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_LENGTH 2025 // 最大输入长度 + 1 (用于存储字符串结束符)
// 检查是否为完全连续交替的方波信号
int is_alternating_wave(const char* wave) {
int len = strlen(wave);
if (wave[0] != '0' || wave[len-1] != '0') return 0;
for (int i = 1; i < len - 1; i++) {
if (wave[i] == wave[i-1]) return 0;
}
return 1;
}
// 查找最长的完全连续交替方波信号
void find_longest_alternating_wave(const char* signal, char* result) {
int max_length = 0;
char current_wave[MAX_LENGTH] = {0};
int current_index = 0;
for (int i = 0; signal[i]; i++) {
if (signal[i] == '0' && current_index > 0 && current_wave[current_index-1] == '0') {
if (is_alternating_wave(current_wave) && current_index > max_length) {
max_length = current_index;
strcpy(result, current_wave);
}
current_index = 0;
}
current_wave[current_index++] = signal[i];
current_wave[current_index] = '\0';
}
// 检查最后一个波形
if (is_alternating_wave(current_wave) && current_index > max_length) {
strcpy(result, current_wave);
}
if (max_length == 0) {
strcpy(result, "-1");
}
}
int main() {
char signal[MAX_LENGTH];
char result[MAX_LENGTH];
// 读取输入
fgets(signal, sizeof(signal), stdin);
signal[strcspn(signal, "\n")] = 0; // 移除换行符
// 查找最长的完全连续交替方波信号
find_longest_alternating_wave(signal, result);
// 输出结果
printf("%s\n", result);
return 0;
}
- Javascript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
function findLongestAlternatingWave(signal) {
// 正则表达式模式，匹配完全连续交替的方波信号
const pattern = /^(01)+0$/;
let maxLength = 0;
let longestWave = '-1';
let currentWave = '';
for (let char of signal) {
if (char === '0') {
if (currentWave && currentWave[currentWave.length - 1] === '0') {
// 检查当前波形是否是完全连续交替的，并更新最长波形
if (pattern.test(currentWave) && currentWave.length > maxLength) {
maxLength = currentWave.length;
longestWave = currentWave;
}
currentWave = '';
}
}
currentWave += char;
}
// 检查最后一个波形
if (pattern.test(currentWave) && currentWave.length > maxLength) {
longestWave = currentWave;
}
return longestWave;
}
rl.question('', (signal) => {
// 查找最长的完全连续交替方波信号并输出
console.log(findLongestAlternatingWave(signal));
rl.close();
});
- Java
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String signal = scanner.nextLine();
System.out.println(findLongestAlternatingWave(signal));
scanner.close();
}
public static String findLongestAlternatingWave(String signal) {
// 正则表达式模式，匹配完全连续交替的方波信号
Pattern pattern = Pattern.compile("^(01)+0$");
int maxLength = 0;
String longestWave = "-1";
StringBuilder currentWave = new StringBuilder();
for (char c : signal.toCharArray()) {
if (c == '0') {
if (currentWave.length() > 0 && currentWave.charAt(currentWave.length() - 1) == '0') {
// 检查当前波形是否是完全连续交替的，并更新最长波形
if (pattern.matcher(currentWave).matches() && currentWave.length() > maxLength) {
maxLength = currentWave.length();
longestWave = currentWave.toString();
}
currentWave = new StringBuilder();
}
}
currentWave.append(c);
}
// 检查最后一个波形
if (pattern.matcher(currentWave).matches() && currentWave.length() > maxLength) {
longestWave = currentWave.toString();
}
return longestWave;
}
}
- Cpp
#include <iostream>
#include <string>
#include <regex>
std::string findLongestAlternatingWave(const std::string& signal) {
// 正则表达式模式，匹配完全连续交替的方波信号
std::regex pattern("^(01)+0$");
int maxLength = 0;
std::string longestWave = "-1";
std::string currentWave;
for (char c : signal) {
if (c == '0') {
if (!currentWave.empty() && currentWave.back() == '0') {
// 检查当前波形是否是完全连续交替的，并更新最长波形
if (std::regex_match(currentWave, pattern) && currentWave.length() > maxLength) {
maxLength = currentWave.length();
longestWave = currentWave;
}
currentWave.clear();
}
}
currentWave += c;
}
// 检查最后一个波形
if (std::regex_match(currentWave, pattern) && currentWave.length() > maxLength) {
longestWave = currentWave;
}
return longestWave;
}
int main() {
std::string signal;
std::getline(std::cin, signal);
// 查找最长的完全连续交替方波信号并输出
std::cout << findLongestAlternatingWave(signal) << std::endl;
return 0;
}
OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记
投递LINE等公司10个岗位 >