#P3249. 最长方连续方波信号(200分)
-
1000ms
Tried: 89
Accepted: 24
Difficulty: 7
所属公司 :
华为od
最长方连续方波信号(200分)
题面描述
输入一串方波信号,求取最长的完全连续交替方波信号,并将其输出。如果有相同长度的交替方波信号,输出任一即可。
思路
用一个栈存字符,如果当前字符是0,栈顶是0那么可能是一个新的交替字符,取出来验证即可。如果当前字符是0,栈顶是1,直接入栈,如果当前字符是1,直接入栈。
代码分析
-
输入部分:
- 使用
cin >> s;从标准输入读取一个字符串,代表方波信号。这个字符串由字符0和1组成。
- 使用
-
正则表达式定义:
- 定义了一个正则表达式
regex pattern("^(01)+0$");,用于匹配符合特定模式的字符串。该模式要求字符串必须以一个或多个01交替组合开始,并且以0结尾。
- 定义了一个正则表达式
-
初始化变量:
ans被初始化为-1,用于存储找到的最长符合条件的方波信号。若未找到符合条件的信号,最终将输出-1。currentSignal用于动态存储当前正在检查的信号。maxLen初始化为0,用于记录找到的符合条件的信号的最大长度。
-
遍历字符串:
- 使用
for循环遍历输入字符串中的每个字符,将当前字符添加到currentSignal中,形成一个可能的信号。
- 使用
-
条件检查:
- 当遇到字符
0时,代码检查currentSignal的长度。若长度大于1且倒数第二个字符也是0,则表明一个信号的结束。 - 进一步使用
regex_search(currentSignal, pattern)来检查currentSignal是否符合正则表达式定义的完全交替方波信号的模式,并且检查当前信号的长度是否大于maxLen。如果都符合条件,则更新maxLen和ans。
- 当遇到字符
-
信号重置:
- 在每次找到结束信号后,重置
currentSignal为一个空字符串,以准备下一段可能的信号。
- 在每次找到结束信号后,重置
-
最后检查:
- 在遍历结束后,代码还会检查
currentSignal是否满足条件。这是因为最后一个信号可能没有在循环中被处理(例如,字符串以0结束的情况)。如果符合条件且长度大于maxLen,则更新答案。
- 在遍历结束后,代码还会检查
-
输出结果:
- 最后,程序将输出找到的符合条件的最长信号,如果没有找到符合条件的信号,则输出
-1。
- 最后,程序将输出找到的符合条件的最长信号,如果没有找到符合条件的信号,则输出
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
string s; // 声明一个字符串变量 s,用于存储输入的方波信号
cin >> s; // 从标准输入读取方波信号字符串
// 定义正则表达式,匹配以多个“01”交替并以“0”结尾的字符串
regex pattern("^(01)+0$");
string ans = "-1"; // 用于存储结果的变量,初始为“-1”,表示未找到符合条件的信号
string stack; // 用于存储当前正在检查的信号
int maxLen = 0; // 记录找到的最长符合条件的信号的长度
// 遍历输入字符串的每一个字符
for (const auto &c : s) {
// 如果当前字符是 '0'
if (c == '0') {
int len = stack.length(); // 获取当前信号的长度
// 检查当前信号是否满足结束条件
if (len > 0 && stack[len - 1] == '0') {
// 如果当前信号的长度大于 maxLen,并且符合正则表达式的匹配
if (len > maxLen && regex_search(stack, pattern)) {
maxLen = len; // 更新最长信号长度
ans = stack; // 更新结果
}
stack = ""; // 清空 stack,为下一个信号做准备
}
}
// 将当前字符添加到 stack 中
stack += c;
}
// 在循环结束后,检查最后一个信号段(如果没有以 '0' 结束)
if (stack.length() > maxLen && regex_search(stack, pattern)) {
ans = stack; // 如果最后信号符合条件,更新结果
}
cout << ans << endl; // 输出结果
return 0; // 返回0表示程序正常结束
}
python
import re
# 输入获取
s = input() # 从标准输入读取一个字符串,代表方波信号
# 算法入口
def getResult():
# 编译正则表达式,匹配以多个“01”交替并以“0”结尾的字符串
reg = re.compile(r"^(01)+0$")
maxLen = 0 # 记录找到的最长符合条件的信号的长度
ans = "-1" # 用于存储结果的变量,初始为“-1”,表示未找到符合条件的信号
stack = [] # 用于构建当前正在检查的信号
# 遍历输入字符串的每一个字符
for c in s:
# 如果当前字符是 '0'
if c == "0":
# 检查 stack 是否非空且最后一个字符也是 '0'
if len(stack) > 0 and stack[-1] == "0":
sub = "".join(stack) # 将 stack 中的字符连接成一个字符串
# 检查当前字符串的长度是否大于 maxLen,并且符合正则表达式的匹配
if len(sub) > maxLen and reg.match(sub):
maxLen = len(sub) # 更新最长信号长度
ans = sub # 更新结果
stack.clear() # 清空 stack,为下一个信号做准备
# 将当前字符添加到 stack 中
stack.append(c)
# 检查最后一个信号段(如果没有以 '0' 结束)
sub = "".join(stack) # 将最后的 stack 连接成字符串
if len(sub) > maxLen and reg.match(sub):
ans = sub # 如果最后信号符合条件,更新结果
return ans # 返回结果
# 输出打印
print(getResult()) # 调用函数并打印结果
java
import java.util.Scanner; // 导入 Scanner 类用于读取输入
import java.util.regex.Pattern; // 导入 Pattern 类用于正则表达式匹配
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); // 创建 Scanner 对象
System.out.println(getResult(sc.nextLine())); // 读取输入并调用 getResult 方法,输出结果
sc.close(); // 关闭 Scanner
}
// 算法入口
public static String getResult(String s) {
// 编译正则表达式,匹配以多个“01”交替并以“0”结尾的字符串
Pattern reg = Pattern.compile("^(01)+0$");
String ans = "-1"; // 用于存储结果的变量,初始为“-1”,表示未找到符合条件的信号
int maxLen = 0; // 记录找到的最长符合条件的信号的长度
StringBuilder sb = new StringBuilder(); // 用于构建当前正在检查的信号
// 遍历输入字符串的每一个字符
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i); // 获取当前字符
// 如果当前字符是 '0'
if (c == '0') {
// 检查 sb 是否非空且最后一个字符也是 '0'
if (sb.length() > 0 && sb.charAt(sb.length() - 1) == '0') {
// 如果当前信号的长度大于 maxLen,并且符合正则表达式的匹配
if (sb.length() > maxLen && reg.matcher(sb.toString()).find()) {
maxLen = sb.length(); // 更新最长信号长度
ans = sb.toString(); // 更新结果
}
sb = new StringBuilder(); // 清空 sb,为下一个信号做准备
}
}
// 将当前字符添加到 sb 中
sb.append(c);
}
// 在循环结束后,检查最后一个信号段(如果没有以 '0' 结束)
if (sb.length() > maxLen && reg.matcher(sb.toString()).find()) {
ans = sb.toString(); // 如果最后信号符合条件,更新结果
}
return ans; // 返回结果
}
}
题目内容
输入一串方波信号,求取最长的完全连续交替方波信号,并将其输出,如果有相同长度的交替方波信号,输出任一即可,方波信号高位用1标识,低位用0标识,如图:

说明:
- 一个完整的信号一定以0开始然后以0结尾,即010是一个完整信号,但101,1010,0101不是
- 输入的一串方波信号是由一个或多个完整信号组成
- 两个相邻信号之间可能有0个或多个低位,如0110010,011000010
- 同一个信号中可以有连续的高位,如01110101011110001010,前14位是一个具有连续高位的信号
- 完全连续交替方波是指10交替,如01010是完全连续交替方波,0110不是
输入描述
输入信号字符串(长度 >= 3 且 <= 1024)
注:输入总是合法的,不用考虑异常情况
输出描述
输出最长的完全连续交替方波信号串
若不存在完全连续交替方波信号串,输出 -1。
样例1
输入
00101010101100001010010
输出
01010
说明
输入信号串中有三个信号:
0 010101010110(第一个信号段)00
01010(第二个信号段)
010(第三个信号段)
第一个信号虽然有交替的方波信号段,但出现了11部分的连续高位,不算完全连续交替方波,
在剩下的连续方波信号串中01010最长