Dada una lista enlazada como entrada. La tarea es codificar la lista enlazada dada utilizando la codificación de longitud de ejecución . Es decir, reemplazar un bloque de caracteres contiguos por el carácter seguido de su cuenta.
Por ejemplo, en la codificación de longitud de ejecución, «a->a->a->a->a» se reemplazará por «a->5».
Nota : para los Nodes que no se repiten, no agregue el recuento 1. Por ejemplo, a->b->b se reemplazará por «a->b->2» y no por «a->1->b-> 2”.
Ejemplos:
Entrada: Lista = a->a->a->a->a->b->r->r->r->NULL
Salida: a->5->b->r->3->NULL
Explicación:
el carácter ‘a’ se repite 5 veces.
El carácter ‘b’ se repite 1 vez.
El carácter ‘r’ se repite 3 veces.
Por lo tanto, la salida es a->5->b->r->3->NULL .
Entrada: a->a->a->a->a->a->a->a->a->a->b->r->r->r->a->a-> a->NULL
Salida: a->1->0->b->r->3->a->3->NULL
Enfoque :
- Recorra la lista.
- Considere el primer carácter como c .
- Considere el carácter actual como x .
- Si el carácter es el mismo que c , incremente el conteo.
- Si los caracteres no son los mismos, agregue el conteo a la lista y agregue el siguiente carácter a la lista, restablezca el conteo a 1 .
C++
// C++ program to encode a linked list // using Run Length Encoding #include <bits/stdc++.h> using namespace std; // A linked list node struct Node { char data; struct Node* next; Node(int x) { data = x; next = NULL; } }; // Function to append nodes to a list void append(struct Node* head_ref, char new_data) { struct Node* new_node = new Node(new_data); struct Node* last = head_ref; if (head_ref == NULL) { head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } // Function to print list void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } // Function to encode the list void RLE(Node* head) { // Pointer used to traverse through // all the nodes in the list Node* p = head; // List to store the encoded message Node* temp = new Node(p->data); // Store the first character in c char c = p->data; p = p->next; // Count to count the number of // continuous elements int count = 1; // Traverse through all the // elements in the list while (p != NULL) { // Store the current character in x char x = p->data; // If the characters are same if (c == x) // Increment count count++; // Else else { // If the count is greater than 1 if (count > 1) { // Append the count to list if (count > 9) append(temp, '0' + (count / 10)); append(temp, '0' + (count % 10)); } // Reset the count count = 1; // Add the next character // to the list append(temp, x); // Take the character to check as // the current character c = x; } p = p->next; } // Add the final count if (count != 0) append(temp, '0' + count); // Print the list printList(temp); } // Driver code int main() { // Creating the linked list Node* head = new Node('a'); head->next = new Node('a'); head->next->next = new Node('a'); head->next->next->next = new Node('b'); head->next->next->next->next = new Node('r'); head->next->next->next->next->next = new Node('r'); RLE(head); return 0; }
Java
// Java program to encode a linked list // using Run Length Encoding class GFG { // A linked list node static class Node { char data; Node next; }; // Utility function to create a new Node static Node newNode(char data) { Node temp = new Node(); temp.data = data; temp.next = null; return temp; } // Function to append nodes to a list static void append(Node head_ref, char new_data) { Node new_node = newNode(new_data); Node last = head_ref; if (head_ref == null) { head_ref = new_node; return; } while (last.next != null) last = last.next; last.next = new_node; return; } // Function to print list static void printList(Node node) { while (node != null) { System.out.print(node.data+" "); node = node.next; } } // Function to encode the list static void RLE(Node head) { // Pointer used to traverse through // all the nodes in the list Node p = head; // List to store the encoded message Node temp = newNode(p.data); // Store the first character in c char c = p.data; p = p.next; // Count to count the number of // continuous elements int count = 1; // Traverse through all the // elements in the list while (p != null) { // Store the current character in x char x = p.data; // If the characters are same if (c == x) // Increment count count++; // Else else { // If the count is greater than 1 if (count > 1) { // Append the count to list if (count > 9) append(temp, (char) ('0' + (count / 10))); append(temp, (char) ('0' + (count % 10))); } // Reset the count count = 1; // Add the next character // to the list append(temp, x); // Take the character to check as // the current character c = x; } p = p.next; } // Add the final count if (count != 0) append(temp, (char) ('0' + count)); // Print the list printList(temp); } // Driver code public static void main(String[] args) { // Creating the linked list Node head = newNode('a'); head.next = newNode('a'); head.next.next = newNode('a'); head.next.next.next = newNode('b'); head.next.next.next.next = newNode('r'); head.next.next.next.next.next = newNode('r'); RLE(head); } } // This code has been contributed by 29AjayKumar
Python3
# Python3 program to encode a linked list # using Run Length Encoding # A linked list node class Node: def __init__(self, data): self.data = data self.next = None # Function to append nodes to a list def append(head_ref, new_data): _node = Node(new_data); last = head_ref; if (head_ref == None): head_ref =_node; return; while (last.next != None): last = last.next; last.next =_node; return; # Function to print list def printList(node): while (node != None): print(node.data, end = ' ') node = node.next; # Function to encode the list def RLE(head): # Pointer used to traverse through # all the nodes in the list p = head; # List to store the encoded message temp = Node(p.data); # Store the first character in c c = p.data; p = p.next; # Count to count the number of # continuous elements count = 1; # Traverse through all the # elements in the list while (p != None): # Store the current character in x x = p.data; # If the characters are same if (c == x): # Increment count count += 1 # Else else: # If the count is greater than 1 if (count > 1): # Append the count to list if (count > 9): append(temp, chr(ord('0') + (count // 10))); append(temp, chr(ord('0') + (count % 10))); # Reset the count count = 1; # Add the next character # to the list append(temp, x); # Take the character to check as # the current character c = x; p = p.next; # Add the final count if (count != 0): append(temp, chr(ord('0') + count)) # Print the list printList(temp); # Driver code if __name__=='__main__': # Creating the linked list head = Node('a'); head.next = Node('a'); head.next.next = Node('a'); head.next.next.next = Node('b'); head.next.next.next.next = Node('r'); head.next.next.next.next.next = Node('r'); RLE(head); # This code is contributed by pratham76
C#
// C# program to encode a linked list // using Run Length Encoding using System; class GFG { // A linked list node public class Node { public char data; public Node next; }; // Utility function to create a new Node static Node newNode(char data) { Node temp = new Node(); temp.data = data; temp.next = null; return temp; } // Function to append nodes to a list static void append(Node head_ref, char new_data) { Node new_node = newNode(new_data); Node last = head_ref; if (head_ref == null) { head_ref = new_node; return; } while (last.next != null) last = last.next; last.next = new_node; return; } // Function to print list static void printList(Node node) { while (node != null) { Console.Write(node.data+" "); node = node.next; } } // Function to encode the list static void RLE(Node head) { // Pointer used to traverse through // all the nodes in the list Node p = head; // List to store the encoded message Node temp = newNode(p.data); // Store the first character in c char c = p.data; p = p.next; // Count to count the number of // continuous elements int count = 1; // Traverse through all the // elements in the list while (p != null) { // Store the current character in x char x = p.data; // If the characters are same if (c == x) // Increment count count++; // Else else { // If the count is greater than 1 if (count > 1) { // Append the count to list if (count > 9) append(temp, (char) ('0' + (count / 10))); append(temp, (char) ('0' + (count % 10))); } // Reset the count count = 1; // Add the next character // to the list append(temp, x); // Take the character to check as // the current character c = x; } p = p.next; } // Add the final count if (count != 0) append(temp, (char) ('0' + count)); // Print the list printList(temp); } // Driver code public static void Main() { // Creating the linked list Node head = newNode('a'); head.next = newNode('a'); head.next.next = newNode('a'); head.next.next.next = newNode('b'); head.next.next.next.next = newNode('r'); head.next.next.next.next.next = newNode('r'); RLE(head); } } /* This code contributed by PrinciRaj1992 */
Javascript
<script> // JavaScript program to encode a linked list // using Run Length Encoding // A linked list node class Node { constructor() { this.data = 0; this.next = null; } } // Utility function to create a new Node function newNode(data) { var temp = new Node(); temp.data = data; temp.next = null; return temp; } // Function to append nodes to a list function append(head_ref, new_data) { var new_node = newNode(new_data); var last = head_ref; if (head_ref == null) { head_ref = new_node; return; } while (last.next != null) last = last.next; last.next = new_node; return; } // Function to print list function printList(node) { while (node != null) { document.write(node.data + " "); node = node.next; } } // Function to encode the list function RLE(head) { // Pointer used to traverse through // all the nodes in the list var p = head; // List to store the encoded message var temp = newNode(p.data); // Store the first character in c var c = p.data; p = p.next; // Count to count the number of // continuous elements var count = 1; // Traverse through all the // elements in the list while (p != null) { // Store the current character in x var x = p.data; // If the characters are same if (c == x) // Increment count count++; // Else else { // If the count is greater than 1 if (count > 1) { // Append the count to list if (count > 9) append( temp, String.fromCharCode("0".charCodeAt(0) + parseInt(count / 10)) ); append( temp, String.fromCharCode("0".charCodeAt(0) + (count % 10)) ); } // Reset the count count = 1; // Add the next character // to the list append(temp, x); // Take the character to check as // the current character c = x; } p = p.next; } // Add the final count if (count != 0) append(temp, String.fromCharCode("0".charCodeAt(0) + count)); // Print the list printList(temp); } // Driver code // Creating the linked list var head = newNode("a"); head.next = newNode("a"); head.next.next = newNode("a"); head.next.next.next = newNode("b"); head.next.next.next.next = newNode("r"); head.next.next.next.next.next = newNode("r"); RLE(head); </script>
a 3 b r 2
Conversión en el lugar : la idea aquí es modificar la lista existente en función de la frecuencia de los caracteres en lugar de crear una nueva lista si el sistema impone restricciones de espacio.
- Recorra la lista.
- Compara el carácter actual con el carácter siguiente. Si es lo mismo, entonces incremente el valor de conteo.
- Eliminar Nodes cuya frecuencia sea superior a 2.
- Si los caracteres no son iguales, actualice el valor de conteo.
C++
// C++ program implementing run length encoding #include<stdio.h> #include<stdlib.h> struct Node { char data; struct Node* next; Node(int x) { data = x; next = NULL; } }; // Function to add node to the list Node* insert (Node *head, int data) { if (head == NULL) return new Node(data); head->next = insert(head->next, data); return head; } // Function to print the list void printList (Node* head) { while (head != NULL) { printf ("%c ",head->data); head = head->next; } return; } void runLengthEncode (Node* head) { Node* temp = NULL; Node* ptr = NULL; int count = 0; //count the number of characters temp = head; while (temp != NULL) { ptr = temp; count = 1; //check if current data and next data is same.If same, then increment count while (temp->next != NULL && temp->data == temp->next->data) { count++; if (count > 2) { // delete only when the node value is repeated more than // twice. ptr->next = temp->next; free(temp); temp = ptr; } temp = temp->next; } // update only when the node value is repeated more than one time. if (count > 1) temp->data = count + '0'; temp = temp->next; } return; } // Driver code int main() { // Creating the linked list Node* head = new Node('a'); head->next = new Node('a'); head->next->next = new Node('a'); head->next->next->next = new Node('b'); head->next->next->next->next = new Node('r'); head->next->next->next->next->next = new Node('r'); runLengthEncode (head); printList (head); return 0; }
Java
// java program implementing run length encoding class GFG { // A linked list node static class Node { char data; Node next; }; // Utility function to create a new Node static Node newNode(char data) { Node temp = new Node(); temp.data = data; temp.next = null; return temp; } // Function to add node to the list static Node insert(Node head, char data) { if (head == null) return newNode(data); head.next = insert(head.next, data); return head; } // Function to print the list static void printList (Node head) { while (head != null) { System.out.print(head.data + " "); head = head.next; } return; } static void runLengthEncode (Node head) { Node temp; Node ptr; int count = 0; //count the number of characters temp = head; while (temp != null) { ptr = temp; count = 1; //check if current data and next data is same.If same, then increment count while (temp.next != null && temp.data == temp.next.data) { count++; if (count > 2) { // delete only when the node value is repeated more than // twice. ptr.next = temp.next; temp= null; temp = ptr; } temp = temp.next; } // update only when the node value is repeated more than one time. if (count > 1) temp.data = (char) (count + '0'); temp = temp.next; } return; } // Driver code public static void main(String [] args) { // Creating the linked list Node head = newNode('a'); head.next = newNode('a'); head.next.next = newNode('a'); head.next.next.next = newNode('b'); head.next.next.next.next = newNode('r'); head.next.next.next.next.next = newNode('r'); runLengthEncode (head); printList (head); } } // This code is contributed by AR_Gaurav
Python3
# Python3 program implementing run length encoding class Node: def __init__(self, data): self.data = data self.next = None # Function to add node to the list def insert(head, data): if (head == None): return Node(data); head.next = insert(head.next, data); return head; # Function to print the list def printList(head): while (head != None): print(head.data, end = ' ') head = head.next; return; def runLengthEncode(head): temp = None; ptr = None; count = 0; #count the number of characters temp = head; while (temp != None): ptr = temp; count = 1; # check if current data and next data # is same.If same, then increment count while (temp.next != None and temp.data == temp.next.data): count += 1 if (count > 2): # delete only when the node # value is repeated more than # twice. ptr.next = temp.next; del (temp); temp = ptr; temp = temp.next; # update only when the node value # is repeated more than one time. if (count > 1): temp.data = count ; temp = temp.next; return; # Driver code if __name__=='__main__': # Creating the linked list head = Node('a'); head.next = Node('a'); head.next.next = Node('a'); head.next.next.next = Node('b'); head.next.next.next.next = Node('r'); head.next.next.next.next.next = Node('r'); runLengthEncode(head); printList(head); # This code is contributed by rutvik_56
Javascript
<script> // JavaScript program implementing // run length encoding class Node { constructor(x) { this.data=x; this.next=null; } } // Function to add node to the list function insert (head,data) { if (head == null) return new Node(data); head.next = insert(head.next, data); return head; } // Function to print the list function printList (head) { while (head != null) { document.write(head.data+" "); head = head.next; } return; } function runLengthEncode (head) { let temp = null; let ptr = null; let count = 0; //count the number of characters temp = head; while (temp != null) { ptr = temp; count = 1; //check if current data and next data is same.If same, // then increment count while (temp.next != null && temp.data == temp.next.data) { count++; if (count > 2) { // delete only when the node value // is repeated more than // twice. ptr.next = temp.next; delete(temp); temp = ptr; } temp = temp.next; } // update only when the node value is // repeated more than one time. if (count > 1) temp.data = count ; temp = temp.next; } return; } // Driver code let head = new Node('a'); head.next = new Node('a'); head.next.next = new Node('a'); head.next.next.next = new Node('b'); head.next.next.next.next = new Node('r'); head.next.next.next.next.next = new Node('r'); runLengthEncode (head); printList (head); // This code is contributed by unknown2108 </script>
a 3 b r 2