졸리 점퍼 시퀀스 - 매우 정확한

n개의 숫자로 구성된 시퀀스(n< 3000) is called 졸리 점퍼 연속된 요소 간의 차이의 절대값이 1부터 n-1까지 가능한 모든 값을 취하는 경우. 정의는 단일 정수의 모든 시퀀스가 유쾌한 점퍼임을 의미합니다.

예:

  Input:   1 4 2 3   Output:   True This sequence 1 4 2 3 is Jolly Jumper because the absolute differences are 3 2 and 1.   Input:   1 4 2 -1 6   Output:   False The absolute differences are 3 2 3 7. This does not contain all the values from 1 through n-1. So this sequence is not Jolly.   Input:   11 7 4 2 1 6   Output:   True

아이디어는 연속 요소의 절대 차이 세트를 저장하기 위해 부울 배열을 유지하는 것입니다.

두 요소 간의 절대 차이가 n-1 또는 0보다 크면 false를 반환합니다.
절대 차이가 반복되면 1에서 n-1까지의 모든 절대 차이가 존재할 수 없습니다( 비둘기집 원리 ) 거짓을 반환합니다.

아래는 위의 아이디어를 바탕으로 구현한 것입니다.

C++

// Program for Jolly Jumper Sequence #include   using namespace std; // Function to check whether given sequence is // Jolly Jumper or not bool isJolly(int a[] int n) {  // Boolean vector to diffSet set of differences.  // The vector is initialized as false.  vector<bool> diffSet(n false);  // Traverse all array elements  for (int i=0; i < n-1 ; i++)  {  // Find absolute difference between current two  int d = abs(a[i]-a[i+1]);  // If difference is out of range or repeated  // return false.  if (d == 0 || d > n-1 || diffSet[d] == true)  return false;  // Set presence of d in set.  diffSet[d] = true;  }  return true; } // Driver Code int main() {  int a[] = {11 7 4 2 1 6};  int n = sizeof(a)/ sizeof(a[0]);  isJolly(a n)? cout << 'Yes' : cout << 'No';  return 0; }

Java

// Program for Jolly Jumper Sequence import java.util.*; class GFG { // Function to check whether given sequence  // is Jolly Jumper or not static boolean isJolly(int a[] int n) {  // Boolean vector to diffSet set of differences.  // The vector is initialized as false.  boolean []diffSet = new boolean[n];  // Traverse all array elements  for (int i = 0; i < n - 1 ; i++)  {  // Find absolute difference   // between current two  int d = Math.abs(a[i] - a[i + 1]);  // If difference is out of range or repeated  // return false.  if (d == 0 || d > n - 1 ||   diffSet[d] == true)  return false;  // Set presence of d in set.  diffSet[d] = true;  }  return true; } // Driver Code public static void main(String[] args)  {  int a[] = {11 7 4 2 1 6};  int n = a.length;  if(isJolly(a n))  System.out.println('Yes');  else  System.out.println('No'); } } // This code is contributed by Rajput-Ji

Python3

# Python3 Program for Jolly Jumper # Sequence # Function to check whether given  # sequence is Jolly Jumper or not def isJolly(a n): # Boolean vector to diffSet set  # of differences. The vector is  # initialized as false. diffSet = [False] * n # Traverse all array elements for i in range(0 n-1): # Find absolute difference between # current two d = abs(a[i]-a[i + 1]) # If difference is out of range or # repeated return false. if (d == 0 or d > n-1 or diffSet[d] == True): return False # Set presence of d in set. diffSet[d] = True return True # Driver Code a = [11 7 4 2 1 6] n = len(a) print('Yes') if isJolly(a n) else print('No') # This code is contributed by # Smitha Dinesh Semwal

// Program for Jolly Jumper Sequence using System; class GFG { // Function to check whether given sequence  // is Jolly Jumper or not static Boolean isJolly(int []a int n) {  // Boolean vector to diffSet set of differences.  // The vector is initialized as false.  Boolean []diffSet = new Boolean[n];  // Traverse all array elements  for (int i = 0; i < n - 1 ; i++)  {  // Find absolute difference   // between current two  int d = Math.Abs(a[i] - a[i + 1]);  // If difference is out of range or repeated  // return false.  if (d == 0 || d > n - 1 ||   diffSet[d] == true)  return false;  // Set presence of d in set.  diffSet[d] = true;  }  return true; } // Driver Code public static void Main(String[] args)  {  int []a = {11 7 4 2 1 6};  int n = a.Length;  if(isJolly(a n))  Console.WriteLine('Yes');  else  Console.WriteLine('No'); } } // This code is contributed by PrinciRaj1992

JavaScript

<script> // Javascript program for Jolly Jumper Sequence // Function to check whether given sequence is // Jolly Jumper or not function isJolly(a n)  {    // Boolean vector to diffSet set of   // differences. The vector is  // initialized as false.  let diffSet = new Array(n).fill(false);  // Traverse all array elements  for(let i = 0; i < n - 1; i++)   {    // Find absolute difference between  // current two  let d = Math.abs(a[i] - a[i + 1]);  // If difference is out of range or repeated  // return false.  if (d == 0 || d > n - 1 ||  diffSet[d] == true)  return false;  // Set presence of d in set.  diffSet[d] = true;  }  return true; } // Driver Code let a = [ 11 7 4 2 1 6 ]; let n = a.length; isJolly(a n) ? document.write('Yes') :   document.write('No');   // This code is contributed by _saurabh_jaiswal </script>

산출:

Yes

시간 복잡도: 에)

보조공간 :O(n) 왜냐하면 우리는 크기가 n인 벡터를 사용했기 때문입니다.