Dada una cola de enteros. La tarea es verificar si los elementos consecutivos en la cola son consecutivos por pares.
Ejemplos:
Input: 1 2 5 6 9 10 Output: Yes Input: 2 3 9 11 8 7 Output: No
Acercarse :
- Tome una variable n para almacenar el tamaño de la cola.
- Empuje un elemento a la cola que actúa como marcador.
- Ahora, si el tamaño de la cola es impar, comience a hacer estallar un par mientras n > 2. Además, mientras hace estallar estos pares, verifique su diferencia y disminuya n en 2, si la diferencia no es igual a 1, establezca el indicador en falso.
- Si el tamaño de la cola es par, comience a extraer un par mientras n > 1. Además, mientras extrae estos pares, verifique su diferencia y disminuya n en 2, si su diferencia no es igual a 1, establezca el indicador en falso.
- Finalmente, marque la bandera, si es verdadera, significa que los elementos en la cola están ordenados por pares, de lo contrario no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if successive // pair of numbers in the queue are // consecutive or not #include <bits/stdc++.h> using namespace std; // Function to check if elements are // pairwise consecutive in queue bool pairWiseConsecutive(queue<int> q) { // Fetching size of queue int n = q.size(); // Pushing extra element to the queue // which acts as marker q.push(INT_MIN); // Result flag bool result = true; // If number of elements in the // queue is odd pop elements while // its size is greater than 2. // Else, pop elements while its // size is greater than 1 if (n % 2 != 0) { while (n > 2) { int x = q.front(); q.pop(); q.push(x); n--; int y = q.front(); q.pop(); q.push(y); n--; if (abs(x - y) != 1) { result = false; } } // Popping the last element of queue // and pushing it again. // Also, popping the extra element // that we have pushed as marker q.push(q.front()); q.pop(); q.pop(); } else { while (n > 1) { int x = q.front(); q.pop(); q.push(x); n--; int y = q.front(); q.pop(); q.push(y); n--; if (abs(x - y) != 1) { result = false; } } // popping the extra element that // we have pushed as marker q.pop(); } return result; } // Driver program int main() { // Pushing elements into the queue queue<int> q; q.push(4); q.push(5); q.push(-2); q.push(-3); q.push(11); q.push(10); q.push(5); q.push(6); q.push(8); if (pairWiseConsecutive(q)) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
Java
import java.util.LinkedList; import java.util.Queue; // Java program to check if successive // pair of numbers in the queue are // consecutive or not public class GFG { // Function to check if elements are // pairwise consecutive in queue static boolean pairWiseConsecutive(Queue<Integer> q) { // Fetching size of queue int n = q.size(); // Pushing extra element to the queue // which acts as marker q.add(Integer.MAX_VALUE); // Result flag boolean result = true; // If number of elements in the // queue is odd pop elements while // its size is greater than 2. // Else, pop elements while its // size is greater than 1 if (n % 2 != 0) { while (n > 2) { int x = q.peek(); q.remove(); q.add(x); n--; int y = q.peek(); q.remove(); q.add(y); n--; if (Math.abs(x - y) != 1) { result = false; } } // Popping the last element of queue // and pushing it again. // Also, popping the extra element // that we have pushed as marker q.add(q.peek()); q.remove(); q.remove(); } else { while (n > 1) { int x = q.peek(); q.remove(); q.add(x); n--; int y = q.peek(); q.remove(); q.add(y); n--; if (Math.abs(x - y) != 1) { result = false; } } // popping the extra element that // we have pushed as marker q.remove(); } return result; } // Driver program static public void main(String[] args) { // Pushing elements into the queue Queue<Integer> q = new LinkedList<>(); q.add(4); q.add(5); q.add(-2); q.add(-3); q.add(11); q.add(10); q.add(5); q.add(6); q.add(8); if (pairWiseConsecutive(q)) { System.out.println("Yes"); } else { System.out.println("No"); } } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to check if successive # pair of numbers in the queue are # consecutive or not import sys, queue # Function to check if elements are # pairwise consecutive in queue def pairWiseConsecutive(q): # Fetching size of queue n = q.qsize() # Pushing extra element to the # queue which acts as marker q.put(-sys.maxsize); # Result flag result = bool(True) # If number of elements in the # queue is odd pop elements while # its size is greater than 2. # Else, pop elements while its # size is greater than 1 if (n % 2 != 0): while (n > 2): x = q.queue[0] q.get() q.put(x) n -= 1 y = q.queue[0] q.get() q.put(y) n -= 1 if (abs(x - y) != 1): result = bool(False) # Popping the last element of queue # and pushing it again. # Also, popping the extra element # that we have pushed as marker q.put(q.queue[0]) q.get() q.get() else: while (n > 1): x = q.queue[0] q.get() q.put(x) n -= 1 y = q.queue[0] q.get() q.put(y) n -= 1 if (abs(x - y) != 1): result = bool(False) # popping the extra element that # we have pushed as marker q.get() return result # Driver code # Pushing elements into the queue q = queue.Queue() q.put(4) q.put(5) q.put(-2) q.put(-3) q.put(11) q.put(10) q.put(5) q.put(6) q.put(8) if (bool(pairWiseConsecutive(q))): print("Yes") else: print("No") # This code is contributed by divyeshrabadiya07
C#
// C# program to check if successive // pair of numbers in the queue are // consecutive or not using System; using System.Collections.Generic; class GFG { // Function to check if elements are // pairwise consecutive in queue static Boolean pairWiseConsecutive(Queue<int> q) { // Fetching size of queue int n = q.Count; // Pushing extra element to the queue // which acts as marker q.Enqueue(int.MaxValue); // Result flag Boolean result = true; // If number of elements in the // queue is odd pop elements while // its size is greater than 2. // Else, pop elements while its // size is greater than 1 if (n % 2 != 0) { while (n > 2) { int x = q.Peek(); q.Dequeue(); q.Enqueue(x); n--; int y = q.Peek(); q.Dequeue(); q.Enqueue(y); n--; if (Math.Abs(x - y) != 1) { result = false; } } // Popping the last element of queue // and pushing it again. // Also, popping the extra element // that we have pushed as marker q.Enqueue(q.Peek()); q.Dequeue(); q.Dequeue(); } else { while (n > 1) { int x = q.Peek(); q.Dequeue(); q.Enqueue(x); n--; int y = q.Peek(); q.Dequeue(); q.Enqueue(y); n--; if (Math.Abs(x - y) != 1) { result = false; } } // popping the extra element that // we have pushed as marker q.Dequeue(); } return result; } // Driver Code static public void Main(String[] args) { // Pushing elements into the queue Queue<int> q = new Queue<int>(); q.Enqueue(4); q.Enqueue(5); q.Enqueue(-2); q.Enqueue(-3); q.Enqueue(11); q.Enqueue(10); q.Enqueue(5); q.Enqueue(6); q.Enqueue(8); if (pairWiseConsecutive(q)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } // This code is contributed by Rajput-Ji
Producción:
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(1)