Dada una cuadrícula Matrix [][] de tamaño NxM donde N es el número de filas y M es el número de columnas. La tarea es formar un rectángulo a partir de los elementos límite de grid[][] usando una lista enlazada que tiene cuatro punteros, a saber , anterior , siguiente , superior e inferior . Imprima la lista enlazada final.
Ejemplos:
Entrada: A = [[13, 42, 93, 88],
[26, 38, 66, 42],
[75, 63, 78, 12]]
Salida: 13 42 93 88 42 12 78 63 75 26Explicación:
1. Haga A[0][0] y el Node principal
2. Recorra la fila 0 y cree un Node para cada elemento y conéctelos a través del siguiente puntero.
3. Atraviese la columna (m-1) y cree un Node para cada elemento y conéctelos a través del puntero inferior.
4. Atraviese la fila (n-1) y cree un Node para cada elemento y conéctelos a través del puntero anterior.
5. Recorra la columna 0 y cree un Node para cada elemento y conéctelos a través del puntero superior.
6. Los pasos 2, 3, 4, 5 se repiten hasta temp. La parte superior se vuelve igual a la cabeza.Entrada: A = [[1, 2, 3]
[8, 9, 4]
[7, 6, 5]]
Salida: 1 2 3 4 5 6 7 8
Enfoque: este problema se puede resolver realizando un cruce de límites de la array y creando Nodes para cada elemento y vinculándolos usando siguiente, anterior, inferior o superior y creando una lista vinculada.
Siga los pasos a continuación:
Paso 1: haga grid[0][0] como el encabezado de la lista Vinculada e inicialice temp como el encabezado .
Paso 2: recorra la primera fila de j=1 a j=m-1 donde i=0 y cree un Node para cada elemento y vincúlelos a través del siguiente puntero.
Paso 3: Recorra la última columna desde i=0 hasta i=n-1 donde j=m-1 y cree un Node para cada elemento y vincúlelos a través de un puntero inferior .
Paso 4: atravesar la última fila desde j=m-1a j=0 donde i=n-1 y cree un Node para cada elemento y vincúlelos a través del puntero anterior .
Paso 5: recorra la primera columna desde i=n-1 hasta i=0 donde j=0 y cree un Node para cada elemento y vincúlelos a través del puntero superior .
Paso 6: Los pasos 2, 3, 4, 5 se repiten hasta que temp.top sea igual a head .
Paso 7: Imprima la Lista Vinculada requerida.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Node Class struct Node { int data; Node* next; Node* prev; Node* top; Node* bottom; // Constructor to initialize the node object Node(int data) { this->data = data; next = NULL; prev = NULL; top = NULL; bottom = NULL; } }; // Linked List class struct LinkedList { // initialize head Node* head = NULL; // function to form square // linked list of matrix. void Quad(vector<vector<int> > grid, int n, int m) { // initialising A[0][0] as head. head = new Node(grid[0][0]); // head is assigned to head. Node* temp = head; // i is row index, j is column index int i = 0; int j = 1; // loop till temp.top become equal to head. while (temp != NULL and temp->top != head) { // as we iterating over boundary // of matrix so we will iterate // over first(0) and last(n-1) row // and first(0) and last(m-1) column. // iterating over first i.e 0th row // and connecting node. if (j < m && i == 0) { temp->next = new Node(grid[i][j]); temp = temp->next; j += 1; } // iterating over last i.e (m-1)th // column and connecting Node. else if (j == m && i < n - 1) { i = i + 1; temp->bottom = new Node(grid[i][j - 1]); temp = temp->bottom; } // iterating over last i.e (n-1)th row // and connecting Node. else if (i == n - 1 && j <= m && j >= 1) { if (j == m) j = j - 1; j = j - 1; temp->prev = new Node(grid[i][j]); temp = temp->prev; } // iterating over first i.e 0th column // and connecting Node. else if (i <= n - 1 && j == 0) { i = i - 1; temp->top = new Node(grid[i][j]); temp = temp->top; if (i == 1) temp->top = head; } } } // function to print Linked list. void printList(Node* root) { Node* temp = root; // printing head of linked list cout << temp->data << " "; // loop till temp.top // become equal to head while (temp->top != root) { // printing the node if (temp->next) { cout << temp->next->data << " "; temp = temp->next; } if (temp->prev) { cout << temp->prev->data << " "; temp = temp->prev; } if (temp->bottom) { cout << temp->bottom->data << " "; temp = temp->bottom; } if (temp->top) { cout << temp->top->data << " "; temp = temp->top; } } } }; // Driver Code int main() { vector<vector<int> > grid = { { 13, 42, 93, 88 }, { 26, 38, 66, 42 }, { 75, 63, 78, 12 } }; // n is number of rows int n = grid.size(); // m is number of columns int m = grid[0].size(); // creation of object LinkedList* l = new LinkedList(); // Call Quad method to create Linked List. l->Quad(grid, n, m); // Call Quad method to create Linked List. l->printList(l->head); return 0; } // The code is contributed by Gautam goel (gautamgoel962)
Java
// Java program for above approach // Node Class class Node { int data; Node next; Node prev; Node top; Node bottom; // Constructor to initialize the node object Node(int data) { this.data = data; next = null; prev = null; top = null; bottom = null; } } class GFG { // initialize head public Node head = null; // function to form square linked list of matrix. public void Quad(int[][] grid, int n, int m) { // initialising A[0][0] as head. head = new Node(grid[0][0]); // head is assigned to head. Node temp = head; // i is row index, j is column index int i = 0; int j = 1; // loop till temp.top become equal to head. while (temp.top != head) { // as we iterating over boundary // of matrix so we will iterate // over first(0) and last(n-1) row // and first(0) and last(m-1) column. // iterating over first i.e 0th row // and connecting node. if (j < m && i == 0) { temp.next = new Node(grid[i][j]); temp = temp.next; j += 1; } // iterating over last i.e (m-1)th // column and connecting Node. else if (j == m && i < n - 1) { i = i + 1; temp.bottom = new Node(grid[i][j - 1]); temp = temp.bottom; } // iterating over last i.e (n-1)th row // and connecting Node. else if (i == n - 1 && j <= m && j >= 1) { if (j == m) { j = j - 1; } j = j - 1; temp.prev = new Node(grid[i][j]); temp = temp.prev; } // iterating over first i.e 0th column // and connecting Node. else if (i <= n - 1 && j == 0) { i = i - 1; temp.top = new Node(grid[i][j]); temp = temp.top; if (i == 1) { temp.top = head; } } } } // function to print Linked list. public void printList(Node root) { Node temp = root; // printing head of linked list System.out.print(temp.data + " "); // loop till temp.top // become equal to head while (temp.top != root) { // printing the node if (temp.next != null) { System.out.print(temp.next.data + " "); temp = temp.next; } if (temp.prev != null) { System.out.print(temp.prev.data + " "); temp = temp.prev; } if (temp.bottom != null) { System.out.print(temp.bottom.data + " "); temp = temp.bottom; } if (temp.top != null) { System.out.print(temp.top.data + " "); temp = temp.top; } } } public static void main(String[] args) { int[][] grid = new int[][] { { 13, 42, 93, 88 }, { 26, 38, 66, 42 }, { 75, 63, 78, 12 } }; // n is number of rows int n = grid.length; // m is number of columns int m = grid[0].length; GFG l = new GFG(); // Call Quad method to create Linked List. l.Quad(grid, n, m); // Call Quad method to create Linked List. l.printList(l.head); } } // This code is contributed by lokesh (lokeshmvs21).
Python3
# Python program for above approach # Node Class class Node: # Constructor to initialize the node object def __init__(self, val): self.data = val self.next = None self.prev = None self.top = None self.bottom = None # Linked List class class LinkedList: # Constructor to initialize head def __init__(self): self.head = None # function to form square # linked list of matrix. def Quad(self, grid, n, m): # initialising A[0][0] as head. self.head = Node(grid[0][0]) # head is assigned to head. temp = self.head # i is row index, j is column index i = 0 j = 1 # loop till temp.top become equal to head. while temp.top != self.head: # as we iterating over boundary # of matrix so we will iterate # over first(0) and last(n-1) row # and first(0) and last(m-1) column. # iterating over first i.e 0th row # and connecting node. if j < m and i == 0: temp.next = Node(grid[i][j]) temp = temp.next j += 1 # iterating over last i.e (m-1)th # column and connecting Node. elif j == m and i < n - 1: i = i + 1 temp.bottom = Node(grid[i][j - 1]) temp = temp.bottom # iterating over last i.e (n-1)th row # and connecting Node. elif i == n - 1 and j <= m and j >= 1: if j == m: j = j - 1 j = j - 1 temp.prev = Node(grid[i][j]) temp = temp.prev # iterating over first i.e 0th column # and connecting Node. elif i <= n - 1 and j == 0: i = i - 1 temp.top = Node(grid[i][j]) temp = temp.top if i == 1: temp.top = self.head # function to print Linked list. def printList(self, root): temp = root # printing head of linked list print(temp.data, end =" ") # loop till temp.top # become equal to head while temp.top != root: # printing the node if temp.next: print(temp.next.data, end =" ") temp = temp.next if temp.prev: print(temp.prev.data, end =" ") temp = temp.prev if temp.bottom: print(temp.bottom.data, end =" ") temp = temp.bottom if temp.top: print(temp.top.data, end =" ") temp = temp.top # Driver Code grid = [[13, 42, 93, 88], [26, 38, 66, 42], [75, 63, 78, 12]] # n is number of rows n = len(grid) # m is number of column m = len(grid[0]) # creation of object l = LinkedList() # Call Quad method to create Linked List. l.Quad(grid, n, m) # Call printList method to print list. l.printList(l.head)
Javascript
<script> // Javascript program for above approach // Node Class class Node{ // Constructor to initialize the node object constructor(val){ this.data = val this.next = null this.prev = null this.top = null this.bottom = null } } // Linked List class class LinkedList{ // Constructor to initialize head constructor(){ this.head = null } // function to form square // linked list of matrix. Quad(grid, n, m){ // initialising A[0][0] as head. this.head = new Node(grid[0][0]) // head is assigned to head. let temp = this.head // i is row index, j is column index let i = 0 let j = 1 // loop till temp.top become equal to head. while(temp.top != this.head){ // as we iterating over boundary // of matrix so we will iterate // over first(0) and last(n-1) row // and first(0) and last(m-1) column. // iterating over first i.e 0th row // and connecting node. if(j < m && i == 0){ temp.next = new Node(grid[i][j]) temp = temp.next j += 1 } // iterating over last i.e (m-1)th // column and connecting Node. else if (j == m && i < n - 1){ i = i + 1 temp.bottom = new Node(grid[i][j - 1]) temp = temp.bottom } // iterating over last i.e (n-1)th row // and connecting Node. else if (i == n - 1 && j <= m && j >= 1){ if (j == m) j = j - 1 j = j - 1 temp.prev = new Node(grid[i][j]) temp = temp.prev } // iterating over first i.e 0th column // and connecting Node. else if (i <= n - 1 && j == 0){ i = i - 1 temp.top = new Node(grid[i][j]) temp = temp.top if(i == 1) temp.top = this.head } } } // function to print Linked list. printList(root){ let temp = root // printing head of linked list document.write(temp.data + " ") // loop till temp.top // become equal to head while(temp.top != root){ // printing the node if(temp.next){ document.write(temp.next.data + " ") temp = temp.next } if(temp.prev){ document.write(temp.prev.data + " ") temp = temp.prev } if(temp.bottom){ document.write(temp.bottom.data + " ") temp = temp.bottom } if(temp.top){ document.write(temp.top.data + " ") temp = temp.top } } } } // Driver Code let grid = [[13, 42, 93, 88], [26, 38, 66, 42], [75, 63, 78, 12]] // n is number of rows let n = grid.length // m is number of column let m = grid[0].length // creation of object let l = new LinkedList() // Call Quad method to create Linked List. l.Quad(grid, n, m) // Call printList method to print list. l.printList(l.head) // This code is contributed by gfgking. </script>
13 42 93 88 42 12 78 63 75 26
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por harshdeepmahajan88 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA