首页 > 试题广场 >

交错序列

[编程题]交错序列

热度指数：2630 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

我们定义一个由数字 0 和 1 组成的序列是交错序列，当且仅当在这个序列中 0 和 1 是轮流出现的，比如，0，010，10101 都是交错序列。

现在给出了一个由数字 0 和 1 组成的序列𝐴，它可能不是一个交错序列，但是你可以从这个序列中选择一些数字出来，按他们在序列𝐴中原有的相对顺序排列(即选取𝐴的一个子序列)，使得你最后得到的是一个交错序列。问这样能得到的交错序列的最长长度是多少。

数据范围： $1 \le n \le 10^5 \$ ，序列中只包含 0 和 1。

输入描述:

第一行包含一个整数𝑛，表示输入序列的长度。
第二行包含 𝑛 个 0 或 1，表示对应的序列。

输出描述:

输出能够得到的最长交错序列的长度。

示例1

输入

3
0 1 0

输出

示例2

输入

8
1 1 0 0 1 1 0 0

输出

算法知识视频讲解

Java

阿英要上岸

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        ArrayList<Integer> list = new ArrayList<>();
        int len = 1;
        for(int i=0; i<n; i++){
            list.add(in.nextInt());
        }
        int pre = list.get(0);
        
        for(int i=1; i<n; i++){
            if(list.get(i) != pre){
                len++;
                pre = list.get(i);
            }
        }
        System.out.println(len);
    }
}

发表于 2022-08-06 14:03:49 回复(0)

Java

Mono_Chrome

import java.util.Scanner;

public class Main {



    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int count = 1;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if (i > 0) {
                if (arr[i] != arr[i - 1]) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

发表于 2019-06-16 11:30:22 回复(0)