[PYTHON] Lassen Sie Code Tag 11 ab Null "1315. Summe der Knoten mit gleichwertigen Großeltern"

Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.

Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.

Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.

Letztes Mal Leet Code Day10 ab Null "1431. Kinder mit der größten Anzahl an Süßigkeiten"

Problem

1315. Sum of Nodes with Even-Valued Grandparent

Der Schwierigkeitsgrad ist Mittel.

Bei einer Dichotomie sollten Sie das übergeordnete Element dieses übergeordneten Elements zurückgeben, den Gesamtwert der "Knoten, deren Großeltern einen geraden Wert haben". Wenn es nicht existiert, wird "0" zurückgegeben.

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] Output: 18 Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Constraints: The number of nodes in the tree is between 1 and 10^4. The value of nodes is between 1 and 100.

Ein Beispiel sieht so aus, wobei "6" und "8" die Bedingung sind, Großeltern und sogar zu sein, und "[2,7,1,3]" die Enkel von 6 sind. Der Gesamtwert von "[5]", der der Enkel von 8, "18" ist, wird zurückgegeben.

Lösung

Als ich das Problem sah, kam mir die Idee, dass der aktuelle Knoten, der übergeordnete Knoten und der Großelternknoten verschoben und gehalten werden. Wenn der Großelternknoten vorhanden ist und sein Wert durch 2 geteilt wird, ist der Rest 0. Die Idee ist beispielsweise, den aktuellen Knoten zum Gesamtwert hinzuzufügen. Das Folgende ist eine Implementierung dieser Idee.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    ans = 0
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(cur:TreeNode,par:TreeNode,gra:TreeNode):
            if gra and gra.val % 2 == 0:
                self.ans += cur.val
            if cur.left:
                dfs(cur.left,cur,par)
            if cur.right:
                dfs(cur.right,cur,par)

        dfs(root,None,None)
        return self.ans
# Runtime: 92 ms, faster than 98.47% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.
# Memory Usage: 17.3 MB, less than 100.00% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.

Dieses Mal schien die Denkweise effizient zu sein, deshalb habe ich es sehr einfach gemacht. Es ist schnell genug und ich denke, ich habe eine ziemlich gute Antwort bekommen.

Einige Leute mögen neugierig auf die Position von ans sein, aber in Python ist es nicht möglich, auf eine globale Variable in der Mitte einer Funktion zu verweisen und sie auf halber Strecke in eine lokale Variable neu zu definieren, und sie ist irgendwo in der Funktion lokal. Eine als Variable definierte Variable wird beim Eintritt in die Funktion von Anfang an als lokale Variable behandelt. So sieht es also aus.

Es war irgendwie unangenehm, also habe ich es nachgeschlagen und festgestellt, dass Python eine "nichtlokale" Variable hat. Wenn eine Funktion innerhalb einer Funktion definiert wird, scheint sie verwendet zu werden, um die Variablen in der äußeren Funktion von der inneren Funktion zu ändern, und sie kann damit geschrieben werden.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(cur:TreeNode,par:TreeNode,gra:TreeNode):
            if gra and gra.val % 2 == 0:
                nonlocal ans
                ans += cur.val
            if cur.left:
                dfs(cur.left,cur,par)
            if cur.right:
                dfs(cur.right,cur,par)
        ans = 0
        dfs(root,None,None)
        return ans
# Runtime: 92 ms, faster than 98.47% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.
# Memory Usage: 17.3 MB, less than 100.00% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.

Die Geschwindigkeit ändert sich nicht, und diese ist sauberer und ich persönlich mag es vielleicht.