d097 - 10038 - Jolly Jumpers
題目描述
題目要求判斷給定的整數序列是否為 Jolly Jumper。一個 Jolly Jumper 序列的定義是，序列中相鄰兩個數字的差的絕對值，必須包含從 1 到 n-1 的所有整數，其中 n 是序列的長度。
解題思路
程式碼首先讀取序列的長度 n，然後讀取序列中的 n 個整數。接著，程式碼遍歷序列，計算相鄰兩個數字的差的絕對值。對於每個差值，程式碼將對應索引位置的 brr 陣列元素設為 0。最後，程式碼檢查 brr 陣列中是否所有從 1 到 n-1 的索引位置都設為 0。如果都是，則序列是 Jolly Jumper，否則不是。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main(){
int n=0;
bool ans=true;
while(cin >> n){
int arr[n];
int brr[n];
int range=n-1;
for(int i=0;i<n;i++){
cin >> arr[i];
}
for(int i=0;i<n-1;i++){
if(arr[i+1]-arr[i]>0){
if(arr[i+1]-arr[i]<1||arr[i+1]-arr[i]>range){
ans=false;
break;
}
else{
brr[arr[i+1]-arr[i]]=0;
}
}
else{
if(arr[i]-arr[i+1]<1||arr[i]-arr[i+1]>range){
ans=false;
break;
}
else{
brr[arr[i]-arr[i+1]]=0;
}
}
}
for(int i=1;i<n;i++){
if(brr[i]!=0){
ans=false;
}
}
if(ans==true){
cout << "Jolly" << endl;
}
else{
cout << "Not jolly" << endl;
}
ans=true;
}
}