Ruby mit AtCoder 14 lernen [3. Algorithmus Praktischer Test Sprinkler] Hash-Erstellung, Schlüssel- / Wertschöpfung

Einführung

Teilnahme an wettbewerbsfähiger Programmierung als Teil des Lernens von Ruby und Algorithmen. Hier geben wir aus, was wir während des Lernens gelernt haben.

Diesmal über Hash. Der Grund für das Schreiben dieses Artikels war der 3. praktische Algorithmus-Test, Frage 5 "Sprinkler".

Dieses Problem konnte problemlos mit Hash beantwortet werden. Ich hatte wenig Verständnis für Hashing und konnte diese Frage während des Tests nicht beantworten ...

Also diesmal

① Beantworten Sie diese Frage mit einem Hash ② Überlegen Sie anhand der Antwort, wie Hash verwendet werden soll

Mit dieser Art von Fluss möchte ich es auf meine eigene Weise zusammenfassen.

Problem

Ein ungerichteter Graph, bestehend aus N Eckpunkten mit den Nummern 1,2,3, ..., N und M ungerichteten Seiten mit den Nummern 1,2,3, ..., M. Gegeben. Die Seite i verbindet die Eckpunkte ui und vi in beide Richtungen.

Jeder Scheitelpunkt kann gefärbt werden, zunächst wird der Scheitelpunkt i mit der Farbe ci gemalt. (In diesem Problem wird die Farbe durch eine Ganzzahl größer oder gleich 1 und kleiner oder gleich 10 ** 5 dargestellt.)

An jeder Spitze sind Sprinkler installiert. Wenn Sie den Sprinkler am Scheitelpunkt i starten, Die Farbe aller Scheitelpunkte neben dem Scheitelpunkt i wird beim Starten des Sprinklers mit der Farbe des Scheitelpunkts i neu gestrichen.

Verarbeiten Sie die Q-Abfragen s1, s2,…, sQ im folgenden Format der Reihe nach. --Geben Sie die aktuelle Farbe des Scheitelpunkts x aus. Starten Sie dann den Sprinkler am Scheitelpunkt x. Gegeben in der Form 1 x. --Geben Sie die aktuelle Farbe des Scheitelpunkts x aus. Überschreiben Sie dann die Farbe des Scheitelpunkts x mit y. Gegeben in der Form 2 x y.

** Einschränkungen **

• Alle angegebenen Eingaben sind Ganzzahlen
• 1≤N,Q≤200
• 0≤M≤N(N−1)/2
• 1≤ui,vi≤N
• 1≤ci≤10**5 --i ist eine Zeichenfolge in einem der folgenden Formate
  • '1 x'(1≤x≤N)
  • '2 x y' (1≤x≤N,1≤y≤10**5)
• In einem bestimmten Diagramm gibt es keine Mehrfachseiten oder Selbstschleifen

Die Eingabe erfolgt in folgender Form.

N M Q
u1 v1
⋮
uM vM
c1 c2 ⋯ cN
s1
⋮
sQ

Eingabebeispiel
3 2 3
1 2
2 3
5 10 15
1 2
2 1 20
1 1

Ausgabebeispiel
10
10
20

Das Bild des Problems sieht folgendermaßen aus:

Antworten

Dieses Mal gab ich eine Antwort, indem ich mich auf die Antworten anderer Leute bezog.

N, M, Q = gets.split(" ").map(&:to_i)

H = Hash.new{|hash, key| hash[key] = []}　#① Erstellen Sie einen leeren Hash

M.times do
  u, v = gets.split(" ").map(&:to_i) 
  H[u].push(v) #② Ergänzung zu Hash
  H[v].push(u) #② Ergänzung zu Hash
end

C = gets.split(" ").map(&:to_i)
C.insert(0, nil)

Q.times do 
  x,y,z = gets.split(" ").map(&:to_i)
  puts C[y]
  if x == 1
    H[y].each{|i| C[i]=C[y] }
  else
    C[y] = z
  end
end

Über diese Antwort Informationen zum Erstellen eines Hashs und zum Hinzufügen von Schlüsseln und Werten zum Hash Ich werde versuchen, es zusammenzufassen, damit ich das Bild für die nächste Antwort erfassen kann.

① Erstellen Sie einen leeren Hash

In der obigen Lösung wird ein leerer Hash vorbereitet, indem der neuen Methode der Hash-Klasse ein Block {} zugewiesen wird.

H = Hash.new{|hash, key| hash[key] = []}

Jedes Mal, wenn Sie dem Hash einen Schlüssel und einen Wert hinzufügen, wird der Block ausgewertet und ein Objekt erstellt. Im obigen Code ist ein leeres Array der Standardwert für den Wert. Dies liegt daran, dass die diesmal zu beantwortende Frage eine Frage ist, bei der mehrere Werte für einen Schlüssel vorhanden sein können. (Der Schlüssel enthält einen Scheitelpunkt, und der Wert enthält den Scheitelpunkt neben diesem Scheitelpunkt (durch eine Seite verbunden).)

② Ergänzung zu Hash

Das von der Standardeingabe empfangene Objekt wird dem Hash als Schlüssel und Wert hinzugefügt. In dieser Antwort wird der Wert als Element zu dem als Standardwert festgelegten Array hinzugefügt.

u, v = gets.split(" ").map(&:to_i) 
H[u].push(v) #u als Schlüssel und v als Wert
#Da es eine Ergänzung zum Array ist, "<<Sie können auch das Symbol "" verwenden.
H[u] << v

Ich habe versucht, die bisherigen Bilder auf meine eigene Weise zusammenzufassen.

Es ist ein wenig überladen, aber ich habe das Gefühl, dass ich das Bild endlich verstanden habe.

Wenn Sie Hash verwenden möchten (1) Stellen Sie die Beziehung zwischen dem Schlüssel und dem Wert im Block ein. (2) Jedes Mal, wenn dem Hash ein Schlüssel hinzugefügt wird, wird ein Wert gemäß (1) erstellt. (3) Befolgen Sie beim Hinzufügen oder Ändern des Werts die Form des Standardwerts.

Vorerst stellte ich fest, dass ich dieses Problem auf diese Weise angehen konnte.

Schließlich

Bisher habe ich die Erstellung von Hashes und das Hinzufügen von Schlüsseln und Werten auf meine eigene Weise zusammengefasst. Ich möchte den Hash immer mehr verwenden und ihn zu meinem eigenen machen.

Ich beabsichtige, es beim Lesen der Referenz usw. zusammenzufassen. Wenn Sie Fehler haben, wäre ich Ihnen dankbar, wenn Sie darauf hinweisen könnten.