题面描述

输入一串方波信号，求取最长的完全连续交替方波信号，并将其输出。如果有相同长度的交替方波信号，输出任一即可。

思路

用一个栈存字符,如果当前字符是$0$,栈顶是$0$那么可能是一个新的交替字符,取出来验证即可。如果当前字符是$0$，栈顶是$1$，直接入栈,如果当前字符是$1$，直接入栈。

代码分析

1. 输入部分：

   • 使用 cin >> s; 从标准输入读取一个字符串，代表方波信号。这个字符串由字符 0 和 1 组成。

2. 正则表达式定义：

   • 定义了一个正则表达式 regex pattern("^(01)+0$");，用于匹配符合特定模式的字符串。该模式要求字符串必须以一个或多个 01 交替组合开始，并且以 0 结尾。

3. 初始化变量：

   • ans 被初始化为 -1，用于存储找到的最长符合条件的方波信号。若未找到符合条件的信号，最终将输出 -1。
   • currentSignal 用于动态存储当前正在检查的信号。
   • maxLen 初始化为 0，用于记录找到的符合条件的信号的最大长度。

4. 遍历字符串：

   • 使用 for 循环遍历输入字符串中的每个字符，将当前字符添加到 currentSignal 中，形成一个可能的信号。

5. 条件检查：

   • 当遇到字符 0 时，代码检查 currentSignal 的长度。若长度大于 1 且倒数第二个字符也是 0，则表明一个信号的结束。
   • 进一步使用 regex_search(currentSignal, pattern) 来检查 currentSignal 是否符合正则表达式定义的完全交替方波信号的模式，并且检查当前信号的长度是否大于 maxLen。如果都符合条件，则更新 maxLen 和 ans。

6. 信号重置：

   • 在每次找到结束信号后，重置 currentSignal 为一个空字符串，以准备下一段可能的信号。

7. 最后检查：

   • 在遍历结束后，代码还会检查 currentSignal 是否满足条件。这是因为最后一个信号可能没有在循环中被处理（例如，字符串以 0 结束的情况）。如果符合条件且长度大于 maxLen，则更新答案。

8. 输出结果：

   • 最后，程序将输出找到的符合条件的最长信号，如果没有找到符合条件的信号，则输出 -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标识，如图：

说明：

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

输入描述

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

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

输出描述

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

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

样例1

输入

00101010101100001010010

输出

01010

说明

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

0 010101010110(第一个信号段)00

01010(第二个信号段)

010(第三个信号段)

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

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