. Structure de données All O`one

432. Structure de données All O`one

Difficulté : Difficile

Sujets : Table de hachage, liste chaînée, conception, liste doublement chaînée

Concevez une structure de données pour stocker le nombre de chaînes avec la possibilité de renvoyer les chaînes avec des nombres minimum et maximum.

Implémentez la classe AllOne :

• AllOne() Initialise l'objet de la structure de données.
• inc(String key) Incrémente le nombre de clés de chaîne de 1. Si la clé n'existe pas dans la structure de données, insérez-la avec le nombre 1.
• dec(String key) Décrémente le nombre de clés de chaîne de 1. Si le nombre de clés est 0 après la décrémentation, supprimez-le de la structure de données. Il est garanti que la clé existe dans la structure de données avant la décrémentation.
• getMaxKey() Renvoie l'une des clés avec le nombre maximal. Si aucun élément n'existe, renvoie une chaîne vide "".
• getMinKey() Renvoie l'une des clés avec le nombre minimum. Si aucun élément n'existe, renvoie une chaîne vide "".

Notez que chaque fonction doit s'exécuter avec une complexité temporelle moyenne O(1).

Exemple 1 :

• Entrée : ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["bonjour"], ["bonjour"], [], [], ["leet"], [], []]
• Sortie : [null, null, null, "bonjour", "bonjour", null, "bonjour", "leet"]
• Explication : AllOne allOne = new AllOne(); allOne.inc("bonjour"); allOne.inc("bonjour"); allOne.getMaxKey(); // renvoie "bonjour" allOne.getMinKey(); // renvoie "bonjour" allOne.inc("leet"); allOne.getMaxKey(); // renvoie "bonjour" allOne.getMinKey(); // renvoie "leet"

Contraintes :

• 1 <= clé.longueur <= 10
• la clé se compose de lettres anglaises minuscules.
• Il est garanti que pour chaque appel à dec, la clé existe dans la structure de données.
• Au maximum 5 * 10⁴ les appels seront effectués vers inc, dec, getMaxKey et getMinKey.

Solution :

Nous devons implémenter une structure de données qui permet d'incrémenter, de décrémenter et de récupérer des clés avec le nombre minimum et maximum en temps constant (O(1)).

Informations clés :

1. Table de hachage (pour le nombre de chaînes) :
   Nous avons besoin d'une table de hachage (comptes) qui mappe chaque chaîne (clé) à son nombre. Cela permet un accès O(1) lors de l'incrémentation ou de la décrémentation du nombre.

2. Liste doublement liée (pour les comptes) :
   Pour garder une trace des décomptes minimum et maximum, nous pouvons utiliser une liste doublement chaînée où chaque nœud représente un décompte unique. Le nœud stockera toutes les chaînes avec ce nombre dans un ensemble. La liste chaînée aidera à récupérer les comptes min et max en temps constant en gardant une trace des nœuds de tête (min) et de queue (max).

3. Deux cartes de hachage :

   • Une carte de hachage (key_to_node) mappera chaque chaîne (clé) au nœud de la liste doublement chaînée qui stocke son décompte. Cela nous permet de déplacer la clé d'un nœud de comptage à un autre en un temps O(1) lorsque nous incrémentons ou décrémentons le nombre.
   • Une autre carte de hachage (comptes) mappera chaque compte à son nœud correspondant dans la liste doublement chaînée, garantissant que nous pouvons localiser le nœud pour n'importe quel compte en un temps O(1).

Plan:

• inc(clé) :

  • Si la clé existe, augmentez son nombre de 1 et déplacez-la vers le nœud suivant (créez un nouveau nœud si nécessaire).
  • Si la clé n'existe pas, créez un nouveau nœud avec le compte 1 et insérez-le.

• déc(clé) :

  • Diminuez le nombre de clés de 1.
  • Si le décompte devient zéro, supprimez la clé de la structure de données.

• getMaxKey() et getMinKey() :

  • Renvoie la première clé du nœud de queue (nombre maximum) ou du nœud de tête (nombre minimum) en temps constant.

Implémentons cette solution en PHP : 432. Structure de données All O`one

inc($key);
 * $obj->dec($key);
 * $ret_3 = $obj->getMaxKey();
 * $ret_4 = $obj->getMinKey();
 */

// Example usage
$allOne = new AllOne();
$allOne->inc("hello");
$allOne->inc("hello");
echo $allOne->getMaxKey(); // returns "hello"
echo $allOne->getMinKey(); // returns "hello"
$allOne->inc("leet");
echo $allOne->getMaxKey(); // returns "hello"
echo $allOne->getMinKey(); // returns "leet"
?>





  
  
  Explication:




Structure des données :



key_to_node : mappe chaque clé au nœud correspondant dans la liste doublement liée.

counts : mappe chaque compte à son nœud correspondant dans la liste doublement chaînée.

head and tail : nœuds factices de tête et de queue pour une manipulation plus facile de la liste doublement chaînée.



Méthodes :


inc($key): If the key exists, it increments its count and moves it to the appropriate node in the list. If not, it inserts it with count 1.

dec($key): Decreases the key’s count and either removes it or moves it to the appropriate node.

getMaxKey(): Returns the key from the node at the tail of the doubly linked list (max count).

getMinKey(): Returns the key from the node at the head of the doubly linked list (min count).





  
  
  Complexity:



All operations are designed to run in O(1) average time complexity.


Let me know if you need further clarifications!

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!