有趣的跳跃

题意

若长度为 $n$ 的序列相邻差绝对值排序后恰好是 $1$ 到 $n-1$ ，输出 Jolly，否则输出 Not jolly。

思路

用 zip(numbers, numbers[1:]) 枚举相邻对，收集绝对差到集合。若集合恰好等于 set(range(1, length))，说明每个要求的差都出现过且没有重复或越界值。

当 $n=1$ 时，两边都是空集合，也自然得到 Jolly。

代码

Python代码

python

1
2
3
4data = list(map(int, input().split()))
length, numbers = data[0], data[1:]
differences = {abs(right - left) for left, right in zip(numbers, numbers[1:])}
print("Jolly" if differences == set(range(1, length)) else "Not jolly")

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include <cstdio>

/* 对差值进行记数 ,a[1] = 1*/
int cnt[3005] = {0};

int main(){
    int n;
    scanf("%d",&n);
    int i;
    int a,b;
    scanf("%d",&a);
    for (i=2;i<=n;i++){
        scanf("%d",&b);
        int cha = b - a;
        if( cha < 0)
            cha = -cha;
        cnt[cha]++;
        a = b;
    }

    for(i=1;i<=n-1;i++){
        if( cnt[i] != 1){
            printf("Not jolly");
            return 0;
        }
    }
    printf("Jolly");
    return 0;
}

复杂度

时间复杂度为 $O(n)$ ，集合使用 $O(n)$ 空间。

总结

判定一组值是否刚好构成目标集合时，集合相等比较简洁且能同时检查重复。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结