Dada una lista muy larga de URL, averigüe la última URL única. Solo se permite un recorrido de todas las URL.
Ejemplos:
Input: https://www.geeksforgeeks.org https://www.geeksforgeeks.org/quiz-corner-gq/ http://qa.geeksforgeeks.org https://practice.geeksforgeeks.org https://ide.geeksforgeeks.org https://write.geeksforgeeks.org https://www.geeksforgeeks.org/quiz-corner-gq/ https://practice.geeksforgeeks.org https://ide.geeksforgeeks.org https://www.geeksforgeeks.org/quiz-corner-gq/ http://qa.geeksforgeeks.org https://practice.geeksforgeeks.org Output: https://write.geeksforgeeks.org
Podemos resolver este problema en un recorrido utilizando Triecon una Lista Doblemente Vinculada (Podemos insertar y borrar en tiempo O(1)). La idea es insertar todas las URL en Trie una por una y verificar si está duplicada o no. Para saber si nos hemos encontrado previamente con la URL, debemos marcar el último Node de cada URL como Node hoja. Si encontramos una URL por primera vez, la insertamos en la lista doblemente vinculada y mantenemos un puntero a ese Node en la lista vinculada en el Node hoja del trie. Si encontramos una URL que ya está en el trie y tiene un puntero a la url en la lista vinculada, eliminamos el Node de la lista vinculada y establecemos su puntero en el trie en nulo. Una vez procesadas todas las URL, la lista vinculada solo contendrá las URL distintas y el Node al principio de la lista vinculada será la última URL única.
// C++ program to print distinct URLs using Trie // and Doubly Linked List #include <bits/stdc++.h> using namespace std; // Alphabet size (# of symbols) const int ALPHABET_SIZE = 256; // A linked list node struct DLLNode { string data; DLLNode* next, * prev; }; // trie node struct TrieNode { TrieNode* children[ALPHABET_SIZE]; // isLeaf is true if the node represents // end of a word bool isLeaf; DLLNode* LLptr; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(DLLNode*& head_ref, string new_data) { DLLNode* new_node = new DLLNode; // put in the data new_node->data = new_data; // Make next of new node as head and previous // as NULL new_node->next = (head_ref); new_node->prev = NULL; // change prev of head node to new node if(head_ref != NULL) head_ref->prev = new_node; // move the head to point to the new node head_ref = new_node; } /* Function to delete a node in a Doubly Linked List. head_ref --> pointer to head node pointer. del --> pointer to node to be deleted. */ void deleteNode(DLLNode*& head_ref, DLLNode* del) { // base case if (head_ref == NULL || del == NULL) return; // If node to be deleted is head node if (head_ref == del) head_ref = del->next; // Change next only if node to be deleted is // NOT the last node if (del->next != NULL) del->next->prev = del->prev; // Change prev only if node to be deleted is // NOT the first node if (del->prev != NULL) del->prev->next = del->next; // Finally, free the memory occupied by del delete(del); return; } // Returns new trie node (initialized to NULLs) TrieNode* getNewTrieNode(void) { TrieNode* pNode = new TrieNode; if (pNode) { pNode->isLeaf = false; for (int i = 0; i < ALPHABET_SIZE; i++) pNode->children[i] = NULL; pNode->LLptr = NULL; } return pNode; } // If not present, inserts key into trie // If the key is prefix of trie node, just marks leaf node void insert(TrieNode* root, string key, DLLNode*& head) { int index; TrieNode* pCrawl = root; for (int level = 0; level < key.length(); level++) { index = int(key[level]); if (!pCrawl->children[index]) pCrawl->children[index] = getNewTrieNode(); pCrawl = pCrawl->children[index]; } if (pCrawl->isLeaf) { // cout << "Duplicate Found " << key << endl; // delete from linked list if (pCrawl->LLptr) deleteNode(head, pCrawl->LLptr); pCrawl->LLptr = NULL; } else { // mark last node as leaf pCrawl->isLeaf = true; // insert to linked list push(head, key); pCrawl->LLptr = head; } } // Driver function int main() { string urls[] = { "https://www.geeksforgeeks.org", "https://write.geeksforgeeks.org", "http://quiz.geeksforgeeks.org", "http://qa.geeksforgeeks.org", "https://practice.geeksforgeeks.org", "https://ide.geeksforgeeks.org", "http://quiz.geeksforgeeks.org", "https://practice.geeksforgeeks.org", "https://ide.geeksforgeeks.org", "http://quiz.geeksforgeeks.org", "http://qa.geeksforgeeks.org", "https://practice.geeksforgeeks.org" }; TrieNode* root = getNewTrieNode(); // Start with the empty list DLLNode* head = NULL; int n = sizeof(urls)/sizeof(urls[0]); // Construct Trie from given URLs for (int i = 0; i < n; i++) insert(root, urls[i], head); // head of linked list will point to last // distinct URL cout << head->data << endl; return 0; }
Producción:
https://write.geeksforgeeks.org
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA