首页 > 试题广场 >

交错序列

[编程题]交错序列

热度指数：2629 时间限制：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

输出

算法知识视频讲解

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)

Python

爱运动的妹妹

def function(n,num):
    k = 0
    for i in range(1,n):
        if abs(num[i]-num[i-1])==1:
            k +=1
    print(k+1)
if __name__ == '__main__':
    n =int(input())
    num = list(map(int,input().split(' ')))
    function(n,num)

发表于 2019-04-15 18:58:35 回复(0)

Python

小小cx猿

while(True):
try:
n = int(input())
s = input()
ans1 = 0
ans2 = 0
for c in s:
if(ans1 % 2 == 0 and c == '0'):
ans1 += 1
if(ans1 % 2 == 1 and c == '1'):
ans1 += 1
if(ans2 % 2 == 0 and c == '1'):
ans2 += 1
if(ans2 % 2 == 1 and c == '0'):
ans2 += 1
print (max(ans1, ans2))
except:
break

发表于 2019-03-27 14:42:56 回复(0)