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.
Letztes Mal Leet Code Tag 25 "70. Klettertreppen" ab Null
Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.
Twitter Ich mache es.
543. Diameter of Binary Tree Der Schwierigkeitsgrad ist einfach. Auszug aus den 100 beliebtesten Fragen.
Geben Sie bei einem dichotomisierten Baum den Durchmesser dieses Baums zurück. Der Durchmesser bezieht sich hier auf den Durchgang, der den längsten Abstand zwischen jedem Knoten hin und her geht.
Example:
Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
In diesem Fall ist die längste von 4 bis 3 und von 5 bis 3, und die Anzahl der dazwischen liegenden Zweige beträgt 3, sodass 3 zurückgegeben wird.
Es war eine Suche nach Tiefenpriorität.
# 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 diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 0
def dfs(node):
if not node:
return 0
right = dfs(node.right)
left = dfs(node.left)
self.ans = max(self.ans,left+right)
return max(left,right) + 1
dfs(root)
return self.ans
# Runtime: 44 ms, faster than 72.73% of Python3 online submissions for Diameter of Binary Tree.
# Memory Usage: 15.9 MB, less than 51.72% of Python3 online submissions for Diameter of Binary Tree.
Der Grundablauf ist der gleiche wie bei der allgemeinen Suche nach Tiefenprioritäten. Da diesmal jedoch die Länge überprüft werden muss, habe ich dafür eine Variable ans vorbereitet und eine Berechnung hinzugefügt.
Selbst mit den Problemen von Bäumen in der Vergangenheit schreibe ich nur Suchen mit Tiefenpriorität, daher denke ich, dass ich bald Suchen mit Breitenpriorität studieren sollte. Heute ist es zu spät, also das war's, danke.
Wenn es eine andere gute Antwort gibt, werde ich sie hinzufügen.
Recommended Posts