首页 > 试题广场 >

交错序列

[编程题]交错序列

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

我们定义一个由数字 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

输出

算法知识视频讲解

C/C++

watle自动机

水题

1. 显然所求交错序列长度至少为1（可选取A的长度为1的子序列）

2. 从序列第i(i∈[2,n])个数字开始，比较该数字与它的前一个数字，若不同，则所求序列长度+1

#include <stdio.h>
#define maxn 100005
int n,a[maxn];
int main(){
    int i,res;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    res=1;
    for(i=1;i<n;i++){
        if(a[i-1]!=a[i])
            res++;
    }
    printf("%d\n",res);
    return 0;
}

发表于 2019-02-25 09:54:28 回复(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)

C/C++

奋斗之路不堵车

链接：https://www.nowcoder.com/questionTerminal/d00c43a0739e4f0ca299d6c5067bb4b9
来源：牛客网

解题思路：

1.读入数字个数n,使用new创建长度为n的动态数组p；

2.设置字串长度count=0,循环判断p[count]==p[i]是否成立，若不满足相等关系，则更新count+1,并设置p[count]=p[i],依次循环判断；

3.输出count+1。

C++代码实现:

#include<iostream>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int *p=new int[n];
int count=0;
for(int i=0;i<n;i++)
{
cin>>p[i];
if(p[count]!=p[i])
{
count++;
p[count]=p[i];
}
}
cout<<count+1<<endl;
delete [] p;
}
return 0;
}

发表于 2019-09-12 22:38:20 回复(0)

Shelven丶

 C++6行，不同则++

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
    int n, res = 1;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n - 1; i++) if (a[i] != a[i + 1])res++;
    cout << res;
}

发表于 2019-07-22 10:37:42 回复(0)

offer菜鸟

#注意题目并不要求连续子串，即数字发生变化长度就加 1 ，只要记录输入序列数字变化了几次即可


#include <iostream>
 
using namespace std;
 
int main()
{
    int mid,mid2,count=1;
    int length,l=1;
    cin>>length;
    cin>>mid;
    while(l!=length)
    {
        l++;
        cin>>mid2;
        if(mid2!=mid)
        {
            count++;
        }
        mid=mid2;
    }
    cout<<count<<endl;
    return 0;
}

发表于 2019-05-13 16:13:03 回复(0)

C/C++

茶月猫

其实说白了就是找序列中的交错，反转一次就count++，比如一个序列总共反转了3次，则最后组成的最长长度为4.

#include <iostream>
using namespace std;
int main(void)
{
    int len, count = 1;
    cin >> len;
    int a, b;
    cin >> a;
    for (int i = 0; i < len-1; i++)
    {
        cin >> b;
        if (a != b)
            count++;
        a = b;
    }
    cout << count << endl;
    return 0;
}

发表于 2019-05-05 23:09:19 回复(0)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        String[] strs = br.readLine().split(" ");
        int res = 1, cur = strs[0].charAt(0) - '0';
        for (int i = 1; i < strs.length; i++) {
            if(strs[i].charAt(0) - '0' == cur) continue;
            res++;
            cur = strs[i].charAt(0) - '0';
        }
        System.out.println(res);
    }
}

编辑于 2019-03-13 16:06:23 回复(0)

向宇回桌

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); sc.nextLine();
        int[] in = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        int[][] dp = new int[2][2];
        for (int i =1; i<=n; i++) {
            int x = in[i-1]; int rx = (in[i-1] + 1) % 2;
            dp[i%2][x] = Math.max(dp[(i-1)%2][rx]+1, dp[(i-1)%2][x]);
            dp[i%2][rx] = dp[(i-1)%2][rx];
        }
        System.out.println(Math.max(dp[n%2][0], dp[n%2][1]));
    }
}

发表于 2019-03-02 16:50:13 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     int n;     while(cin>>n)     {         int a[n],cnt,pre;         cin>>a[0];         pre = a[0];         cnt = 1;         for(int i=1;i<n;i++)         {             cin>>a[i];             if(a[i]!=pre)             {                 cnt++;                 pre = a[i];             }         }         cout<<cnt<<endl;     }     return 0;
}

发表于 2019-01-18 17:50:03 回复(0)

karaysn

不一定要求是连续的，那么从头开始往后面找应该就是最长的了。

要求连续的话，可以考虑用两个指针去处理吧。

发表于 2019-02-17 13:41:30 回复(0)

想回家的海螺在拧螺丝

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin>>v[i];
    }

    int pre = v[0];
    int ans = 1;
    for(int i = 1; i < n; i++) {
        if(pre != v[i]) {
            ans++;
            pre = (pre+1) % 2;
        }
    }

    cout<<ans;

    return 0;
}

发表于 2023-05-06 15:05:18 回复(0)

黑烟酰胺

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();   // 个数
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }

            int cur = nums[0];
            int res = 1;
            for (int i = 1; i < n; i++) {
                if (nums[i] == cur) continue;
                cur = nums[i];
                res++;
            }
            System.out.println(res);
        }
    }
}

发表于 2022-09-16 23:16:21 回复(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)

C++

牛客409434554号

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=0;cin>>n;
    vector<int> v(n);cin>>v[0];
    for(int i=1;i<n;i++)
    {
        cin>>v[i];
        if(v[i]!=v[i-1])    sum++;
    }
    cout<<sum+1;
}

发表于 2022-01-25 02:09:41 回复(0)

Javascript_V8

biub_

let n=readline()
let input=readline()
function solve(n, input) {
    let arr = input.split(' ').map(Number)
    let pre = arr[0]
    let cnt = 1
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] != pre) {
            cnt++
            pre = arr[i]
        }
    }
    console.log(cnt)
}
solve(n, input)

但最开始自己陷入了自己挖的坑，想着递归去了。

// 没通过 超了，但就是想留着
let n = '3'
let input = "1 1 0 0 1 1 0 0"
function solve(n, input) {
    let arr = input.split(' ').map(Number)
    if (arr.length > 1) {
        let ans = recursion(arr, arr[0])
        console.log(ans)
    }else{
        console.log(0)
    }

}
function recursion(arr, num) {
    if (arr.indexOf(num) === -1) {
        return 0
    } else {
        let index = arr.indexOf(1 - num)
        arr = arr.slice(index)
        return 1 + recursion(arr, 1 - num)

    }
}
solve(n, input)

发表于 2022-01-18 08:55:00 回复(0)

simbayx

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> v;
    int cur=-1,pre=-1;
    for(int i=0;i<n;i++){
        cin>>cur;
        if(i==0||pre!=cur) v.push_back(cur);
        pre=cur;
    }
    cout<<v.size();
    return 0;
}

时间复杂度O(n),空间复杂度O(n)

编辑于 2020-08-30 09:27:40 回复(0)

Python

攻壳机动队2

from itertools import groupby
n=int(input())
a = list(map(int, input().split()))
print(len([k for k, g in groupby(a)]))

用分组（groupby）可以直接去重

发表于 2020-08-01 16:47:09 回复(0)

Python

lx的流星

while True:
    try:
        n=int(input().strip())
        inp=list(map(int,input().strip().split(' ')))
        num=1
        for i in range(1,n):
            if inp[i]!=inp[i-1]:
                num+=1
        print(num)
    except:
        break

发表于 2019-07-27 20:29:19 回复(0)

Jurenly

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
    int a;
    cin>>a;
    int b;
    int count=1;
    vector<int>vec;
     for(int i=0;i<a;i++)
     {
         cin>>b;
         vec.push_back(b);
         if(i>=1)
         {
              if(vec[i]!=vec[i-1])
            {
            count++;
            }
         }
     }
    
    cout<<count<<endl;
    return 0;
}

发表于 2019-06-24 08:46:17 回复(0)