【算法题】最长方连续方波信号

共计 2846 个字符，预计需要花费 8 分钟才能阅读完成。

2022年6月9日23点39分 更新

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 标题：最长方连续方波信号 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
 * 输入一串方波信号，求取最长的完全连续交替方波信号，并将其输出，如果有相同长度的交替方波信号，输出任一即可，方波信号高位用1标识，低位用0标识，如图：
 * 说明：
 * 1） 一个完整的信号一定以0开始然后以0结尾，即010是一个完整信号，但101，1010，0101不是
 * 2）输入的一串方波信号是由一个或多个完整信号组成
 * 3） 两个相邻信号之间可能有0个或多个低位，如0110010，011000010
 * 4） 同一个信号中可以有连续的高位，如01110101011110001010，前14位是一个具有连续高位的信号
 * 5） 完全连续交替方波是指10交替，如01010是完全连续交替方波，0110不是
 * 输入描述: 输入信号字符串（长度>=3且<=1024）： 0010101010110000101000010 注：输入总是合法的，不用考虑异常情况
 * 输出描述: 输出最长的完全连续交替方波信号串： 01010 若不存在完全连续交替方波信号串，输出 -1
 * 示例1
 * 输入
 * 00101010101100001010010
 * 输出
 * 01010
 * 备注:
 * 输入信号串中有三个信号：0 010101010110(第一个信号段) 00 01010(第二个信号段) 010(第三个信号段)
 * <p>
 * 第一个信号虽然有交替的方波信号段，但出现了11部分的连续高位，不算完全连续交替方波，在剩下的连续方波信号串中01010最长
 */
public class M_N_T_24 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();

        extracted_2(line);
    }

    private static void extracted_2(String line) {
        Pattern pattern = Pattern.compile("00*0"); // 匹配出方波信号之间的间隔点
        Matcher matcher = pattern.matcher(line);
        String replace_line = matcher.replaceAll("0 0"); // 替换为空格隔开

        String[] strings = replace_line.split(" "); // 切割

        int len = 0;
        String lenStr = "";
        for (String string : strings) {
            boolean b = string.matches("0(10)+"); // 判断得到的方波信号是否为完全连续交替方波信号

            if (b && string.length() > len) {
                len = strings.length;
                lenStr = string;
            }
        }

        System.out.println(lenStr.equals("") ? -1 : str);
    }
}

原解法：

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 标题：最长方连续方波信号 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
 * 输入一串方波信号，求取最长的完全连续交替方波信号，并将其输出，如果有相同长度的交替方波信号，输出任一即可，方波信号高位用1标识，低位用0标识，如图：
 * 说明：
 * 1） 一个完整的信号一定以0开始然后以0结尾，即010是一个完整信号，但101，1010，0101不是
 * 2）输入的一串方波信号是由一个或多个完整信号组成
 * 3） 两个相邻信号之间可能有0个或多个低位，如0110010，011000010
 * 4） 同一个信号中可以有连续的高位，如01110101011110001010，前14位是一个具有连续高位的信号
 * 5） 完全连续交替方波是指10交替，如01010是完全连续交替方波，0110不是
 * 输入描述: 输入信号字符串（长度>=3且<=1024）： 0010101010110000101000010 注：输入总是合法的，不用考虑异常情况
 * 输出描述: 输出最长的完全连续交替方波信号串： 01010 若不存在完全连续交替方波信号串，输出 -1
 * 示例1
 * 输入
 * 00101010101100001010010
 * 输出
 * 01010
 * 备注:
 * 输入信号串中有三个信号：0 010101010110(第一个信号段) 00 01010(第二个信号段) 010(第三个信号段)
 * <p>
 * 第一个信号虽然有交替的方波信号段，但出现了11部分的连续高位，不算完全连续交替方波，在剩下的连续方波信号串中01010最长
 */
public class M_N_T_24 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();

        ArrayList<Integer> integers = new ArrayList<>();
        integers.add(-1);
        for (int i = 0; i < line.length(); i++) {
            if (line.charAt(i) == 49) {
                integers.add(i);
            }
        }
        integers.add(line.length());

        int le = -1;
        int ri = -1;
        int len = 0;
        boolean isPer = true;
        String str = "";
        for (int i = 0; i < integers.size() - 1; i++) {
            int sumOf_0 = integers.get(i + 1) - integers.get(i) - 1;

            if (i == 0) {
                if (sumOf_0 >= 1) {
                    le = integers.get(i + 1) - 1;
                }
            }

            if (i == integers.size() - 2) {
                if (sumOf_0 >= 1) {
                    ri = integers.get(i) + 1;
                    if (isPer && ri - le + 1 > len) {
                        len = ri - le + 1;
                        str = line.substring(le, ri + 1);
                    }
                    isPer = true;
                }
            }

            if (i > 0 && i < integers.size() - 2) {
                if (sumOf_0 == 0) {
                    isPer = false;
                }
                if (sumOf_0 >= 2) {
                    ri = integers.get(i) + 1;
                    if (isPer && ri - le + 1 > len) {
                        len = ri - le + 1;
                        str = line.substring(le, ri + 1);
                    }
                    le = integers.get(i + 1) - 1;
                    isPer = true;
                }
            }
        }

        System.out.println(str.equals("") ? -1 : str);
    }
}