最长连续方波信号

题目描述

输入一串方波信号, 求取最长的完全连续交替方波信号, 并将其输出, 如果有相同长度的交替方波信号, 输出任一即可. 方波信号高位用1标识, 低位用0标识.

说明:

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

输入

输入信号字符串, 长度 >= 3 且 <= 1024:

例如: 0010101010110000101000010

注: 输入总是合法的, 不用考虑异常情况.

输出

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

例如: 01010

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

示例1

输入:

00101010101100001010010

输出:

01010

题解

Python

def main():
    # 读取输入
    # 然后使用双指针法遍历所有的输入信号
    # 方波条件:
    # 1. 以0开头, 以0结尾
    # 2. 0和1交替出现

    ZERO = "0"
    ONE = "1"

    signals = input()
    assert 3 <= len(signals) <= 1024
    assert signals[0] == ZERO and signals[-1] == ZERO

    last_continous_signal = "-1"

    stack = []
    # 遍历输入信号
    for char in signals:
        # 如果栈为空
        if len(stack) == 0:
            # 那第一个信号需要是 "0"
            # 如果不是"0", 就什么都不做
            if char == ZERO:
                print("stack bottom:", char)
                stack.append(char)
            continue

        # 如果栈顶的信号与当前信号相同, 则说明出现了冲突
        if stack[-1] == char:
            # 检查当前栈中是不是有效的连续交替信号
            # 如果是, 就把它更新到结果中
            if stack[-1] == ZERO:
                # 至少是 "010"
                if len(stack) >= 3 and len(stack) > len(last_continous_signal):
                    last_continous_signal = "".join(stack)
            elif len(stack) >= 4:
                # 至少是 "0101"
                stack.pop()
                assert stack[-1] == ZERO
                if len(stack) > len(last_continous_signal):
                    last_continous_signal = "".join(stack)

            # 最后将栈顶清空, 如果当前元素是 "0", 就把它入栈; 否则什么也不做
            stack.clear()
            if char == ZERO:
                stack.append(char)
            continue
        else:
            # 没有出现相同信号, 将新的信号入栈即可
            stack.append(char)
    
    # 输出结果
    print(last_continous_signal)

if __name__ == "__main__":
    main()