Parlez avec vous série #1

**l'image de couverture reflète l'humeur au moment de la publication

Je veux commencer par penser que depuis un certain temps, j'ai l'habitude d'écrire les défis et leurs solutions potentielles auxquels je faisais face quotidiennement, que cela fasse partie de mon travail ou de mes activités de temps libre.

À partir de ce post, j'ai décidé de présenter la série "Talk with You", dans laquelle je les publierais ici (au moins pour l'instant, au plus une fois dans quelques jours) pour les repérer au public.

D'un côté maintenant, je vais jeter un coup d'œil ici de temps en temps au lieu de mes notes bien structurées pour réorganiser certaines informations et DevCommunity va gérer le stockage, la navigation par ordre croissant et tout le reste, d'un autre côté, je crois aux choses J'écris ici pourrait trouver le public non seulement en mon nom. Attachez, commençons.

Compter les occurrences

Très souvent, en travaillant avec DS, vous devez compter un certain nombre d'occurrences de valeurs et de postfaces pour les interroger de manière efficace, de préférence Time O(1).

Évidemment, vous pourriez penser à créer une HashTable, puis à parcourir DS pour remplir la HashTable. C'est vrai et cela pourrait ressembler à :

iterable = [...]
hashtable = {}
for value in iterable:
    hashtable[value] = hashtable.get(value, 0) + 1

Aujourd'hui, j'ai été confronté à une approche alternative qui fonctionnerait parfaitement sur des listes de chiffres en évitant l'utilisation de HashTable (cela pourrait parfois être une nécessité).

L'idée derrière est d'abord d'obtenir la valeur maximale de la liste et de créer une nouvelle liste de longueur de la valeur maximale, qui sera utilisée comme mappage d'indices.

list_ = [1, 1, 2, 3]
max_ = max(list_)
indices = [0] * max_   # [0, 0, 0, 0]

Maintenant, parcourons la liste d'origine et mappons l'occurrence de chaque valeur dans la liste d'indices.

1. iteration
[1, 1, 2, 3] # list
 |

[0, 1, 0, 0] # indices

2. iteration
[1, 1, 2, 3] # list
    |

[0, 2, 0, 0] # indices

3. iteration
[1, 1, 2, 3] # list
       |

[0, 2, 1, 0] # indices

4. iteration
[1, 1, 2, 3] # list
          |

[0, 2, 1, 1] # indices

Ce qui vient de se passer. Eh bien, fondamentalement, nous avons pris la valeur de la liste d'origine et l'avons utilisée comme index dans notre liste d'indices (et valeur incrémentée à l'index).

Maintenant, si nous souhaitons représenter nos résultats à l'aide d'une liste de mappage, nous pourrions dire qu'il y a 0 zéro car à l'index 0 nous avons la valeur 0, à l'index 1 nous avons la valeur 2, ce qui signifie qu'il y en a 2 un. -s, à l'index 2 nous avons la valeur 1, ce qui signifie qu'il y a 1 deux-s, etc.

Éléments miroir dans la matrice

Même si je suis titulaire de 2 diplômes BSc et MSc, lorsque je découvre une nouvelle astuce mathématique, j'éprouve toujours un sentiment de fascination, c'est-à-dire "Mon Dieu, c'est si simple et ça marche".

D'accord, revenons au sujet, supposons que vous ayez une matrice de N*N et que vous deviez inverser les lignes et les colonnes de manière à obtenir la somme maximale de tous les éléments (ligne par ligne).

matrix 4*4

1 2 3 9
0 9 8 2
5 1 7 4
8 2 6 7  

Dès le premier aperçu, vous ne savez peut-être même pas par où commencer. Mais voici l'astuce avec des éléments en miroir.

matrix 4*4

A B B A
C D D C
C D D C 
A B B A

Le point clé ici est que A dans la matrice ne peut être échangé que par un autre A. Imaginons que nous sommes dans le coin supérieur gauche A (qui vaut 1) et nous aimerions savoir s'il y a un autre A (uniquement A en miroir) qui est plus râpé. Et en effet, nous en avons dans le coin supérieur droit (9).

En suivant la logique et en rappelant le problème d'origine (somme maximale inversant les lignes et les colonnes), nous pourrions conclure qu'en réalité, nous n'avons pas besoin d'effectuer d'opérations inverses, mais simplement de rechercher la valeur maximale parmi les opérations en miroir. Et c'est tout.

Empiler. Compromis entre complexité temporelle et spatiale.

Supposons que vous ayez pour tâche d'implémenter un wrapper de pile avec seulement 3 fonctionnalités : (1) pop (2) push (3) get_min. Vous pouvez utiliser l'interface de la pile pour (1) pop et (2) push, mais vous devez toujours implémenter (3) get_min. Annnd get_min() devrait fonctionner pendant O(1) Time.

Eh bien, lorsque j'ai abordé le problème pour la première fois, j'ai complètement oublié un compromis, qui dit : "Lorsque vous optimisez les performances du Temps, votre situation empire probablement avec l'Espace et vice versa". Pourquoi c'est important, parce que j'ai commencé à penser à des DS optimisés qui me conduisent à des HashTables, mais j'ai vraiment raté les listes naïves, qui pourraient également fonctionner pour O(1) (amorti).

J'ai donc atteint le point où je créais une HashTable où je pourrais stocker chaque état d'une classe wrapper... je m'arrêterai ici car "plus simple est une meilleure option" (parfois). Voyons l'implémentation avec une liste supplémentaire pour stocker la valeur minimale pour chaque état de la pile.

class Wrapper:
   def __init__(self, stack):
      self.stack = stack
      self.min = []

   # Time O(1)
   def pop(self):
      self.stack.pop()
      self.min.pop()

   # Time O(1)
   def push(self, value):
      self.stack.push(value=value)
      min_ = self.min[-1]
      if value < min_:
          min_ = value
      self.min.append(min_)

   # Time O(1)
   def get_min(self):
      return self.min[-1]

Aussi simple que cela puisse paraître.

Conclusion

• continuez à coder et à développer
• n'oubliez pas les compromis et ne compliquez pas trop (quand on ne vous le demande pas)

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!