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 Day 44 "543. Durchmesser des Binärbaums" ab Null
Im Moment priorisiere ich das Medium der 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.
Twitter Ich mache es.
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Der Schwierigkeitsgrad ist Mittel.
Es werden zwei Binärbäume, "Original" und "geklont", angegeben, und es wird ein Verweis auf "Ziel" von "Original" angegeben.
Der duplizierte Baum ist eine Kopie des ursprünglichen Baums und gibt einen Verweis auf denselben Knoten im duplizierten Baum zurück. Sie dürfen die beiden Bäume oder das "Ziel" nicht ändern, und die Antwort muss ein Verweis auf einen Knoten im "geklonten" Baum sein.
Follow-up: Wenn der Baum Wiederholungswerte zulässt, beheben Sie das Problem.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
if not original:
return None
if original == target:
return cloned
return self.getTargetCopy(original.left,cloned.left,target) or self.getTargetCopy(original.right,cloned.right,target)
# Runtime: 672 ms, faster than 60.93% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
# Memory Usage: 23.5 MB, less than 100.00% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
Ich habe es wie oben gelöst. Ich dachte, es wäre eine relativ gute Antwort, weil ich sie einfach schreiben könnte, aber ich habe nicht so viel Geschwindigkeit bekommen, also habe ich nach anderen Antworten gesucht.
class Solution:
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
que = collections.deque([(original, cloned)]) # start at the root
while que:
nodeOrig, nodeClon = que.popleft()
if nodeOrig is target: # if original node is found - cloned node is our answer
return nodeClon
if nodeOrig.left: que.append((nodeOrig.left, nodeClon.left))
if nodeOrig.right: que.append((nodeOrig.right, nodeClon.right))
# Runtime: 656 ms, faster than 92.51% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
# Memory Usage: 23.6 MB, less than 100.00% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/discuss/539484/Simple-clean-and-fast-Python-solution-7-lines-beats-92
Diese Antwort wird mit que geschrieben, sollte aber leicht zu verstehen sein. Die Geschwindigkeit ist perfekt, und wenn Sie lernen können, wie man so antwortet und zu ihm wechselt, anstatt das Problem in einen Typ zu zwingen, den Sie lösen können, wird es Spaß machen, das Problem zu lösen!
Bis hierher für diese Zeit. Danke für deine harte Arbeit.
Recommended Posts