„Talk with You', Serie Nr. 1

**Das Titelbild spiegelt die Stimmung zum Zeitpunkt des Postens wider

Ich möchte mit dem Gedanken beginnen, dass ich seit einiger Zeit die Angewohnheit habe, Herausforderungen und ihre möglichen Lösungen aufzuschreiben, mit denen ich täglich konfrontiert war, sei es im Rahmen meiner Arbeit oder meiner Freizeitaktivitäten.

Ab diesem Beitrag habe ich beschlossen, die Serie „Talk with You“ einzuführen, in der ich sie hier veröffentlichen würde (zumindest vorerst, höchstens alle paar Tage), um sie der Öffentlichkeit zugänglich zu machen.

Einerseits werfe ich jetzt ab und zu einen Blick hierher, statt meiner gut strukturierten Notizen, um ein paar Informationen zu überarbeiten, und DevCommunity kümmert sich um die Speicherung, die Navigation in aufsteigender Reihenfolge und all die anderen Dinge, andererseits glaube ich an die Dinge Ich schreibe hier, vielleicht finde das Publikum nicht nur in meinem Namen. Anschnallen, los geht’s.

Vorkommen zählen

Bei der Arbeit mit DS müssen Sie häufig die Anzahl der Vorkommen von Werten und Nachwörtern zählen, um diese effizient abzufragen, vorzugsweise Zeit O(1).

Natürlich könnten Sie darüber nachdenken, eine HashTable zu erstellen und dann DS zu durchlaufen und die HashTable zu füllen. Das stimmt und könnte so aussehen:

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

Heute stand ich vor einem alternativen Ansatz, der perfekt für Ziffernlisten funktioniert und die Verwendung von HashTable vermeidet (manchmal könnte dies eine Notwendigkeit sein).

Die Idee dahinter besteht zunächst darin, den Maximalwert aus der Liste abzurufen und eine neue Liste mit der Länge des Maximalwerts zu erstellen, die als Indexzuordnung verwendet wird.

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

Lassen Sie uns nun die ursprüngliche Liste durchgehen und das Vorkommen jedes Werts in der Indexliste abbilden.

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

Was gerade passiert ist. Nun, im Grunde genommen haben wir den Wert aus der Originalliste genommen und ihn als Index in unserer Indexliste verwendet (und den Wert am Index erhöht).

Wenn wir nun unsere Ergebnisse mithilfe einer Zuordnungsliste darstellen möchten, könnten wir sagen, dass es 0 Nullen gibt, weil wir bei Index 0 den Wert 0 haben, bei Index 1 haben wir den Wert 2, was bedeutet, dass es 2 Einsen gibt -s, bei Index 2 haben wir den Wert 1, was bedeutet, dass es 1 Zweier usw. gibt.

Spiegelelemente in der Matrix

Auch wenn ich einen BSc- und einen MSc-Abschluss habe, habe ich immer noch ein faszinierendes Gefühl, wenn ich einen neuen Mathe-Trick herausfinde, auch bekannt als „Meine Güte, das ist so einfach und funktioniert“.

Okay, zurück zum Thema. Nehmen wir an, Sie haben eine Matrix aus N*N und müssen Zeilen und Spalten so vertauschen, dass Sie die maximale Summe aller Elemente erhalten (Zeile für Zeile).

matrix 4*4

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

Vielleicht wissen Sie auf den ersten Blick nicht, wo Sie anfangen sollen. Aber hier ist der Trick mit gespiegelten Elementen.

matrix 4*4

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

Der entscheidende Punkt hier ist, dass A in der Matrix möglicherweise nur durch ein anderes A-s ausgetauscht wird. Stellen wir uns vor, wir befinden uns in der oberen linken Ecke A (das ist 1) und wir würden gerne wissen, ob es ein weiteres A (nur gespiegeltes A) gibt, das größer ist. Und tatsächlich haben wir so etwas in der rechten oberen Ecke (9).

Wenn wir der Logik folgen und uns an das ursprüngliche Problem erinnern (maximale Summe, die Zeilen und Spalten umkehrt), könnten wir zu dem Schluss kommen, dass wir in Wirklichkeit keine umgekehrten Operationen durchführen müssen, sondern einfach den Maximalwert unter den gespiegelten Operationen nachschlagen müssen. Und das ist es.

Stapel. Kompromiss zwischen zeitlicher und räumlicher Komplexität.

Angenommen, Sie haben die Aufgabe, einen Stack-Wrapper mit nur drei Funktionalitäten zu implementieren: (1) pop (2) push (3) get_min. Sie können die Stack-Schnittstelle für (1) Pop und (2) Push verwenden, müssen jedoch noch (3) get_min implementieren. Annnd get_min() sollte für O(1)-Zeit funktionieren.

Nun, als ich mich zum ersten Mal mit dem Problem befasste, habe ich einen Kompromiss völlig vergessen, der besagt: „Wenn Sie die Zeitleistung optimieren, werden Sie mit Space wahrscheinlich schlechter und umgekehrt.“ Warum es wichtig ist, denn ich begann über optimierte DS nachzudenken, die mich zu HashTables führten, aber ich vermisste wirklich naive Listen, die auch für O(1) (amortisiert) funktionieren könnten.

Also bin ich an dem Punkt angelangt, an dem ich eine HashTable erstellt habe, in der ich jeden Status einer Wrapper-Klasse speichern könnte ... ich höre hier auf, weil „einfacher eine bessere Option ist“ (manchmal). Sehen wir uns die Implementierung mit einer zusätzlichen Liste zum Speichern des Mindestwerts für jeden Stapelstatus an.

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]

So einfach es ist.

Abschließend

• Codieren und entwickeln Sie weiter
• Denken Sie an Kompromisse und machen Sie es nicht zu kompliziert (wenn Sie nicht gefragt werden)

Das obige ist der detaillierte Inhalt von„Talk with You', Serie Nr. 1. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!