Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.
En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.
Un site qui forme une puissance algorithmique capable de résister aux tests de codage dont on parle très tôt.
Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.
Table de codes Leet commençant à zéro
Dernière fois Leet Code Day 43 "5. Longest Palindromic Substring" commençant à zéro
En ce moment, je résous le support des 100 questions les plus appréciées Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.
Twitter Je le fais.
Le niveau de difficulté est facile. Extrait des 100 questions les plus appréciées.
J'ai trouvé que je l'avais résolu mais j'ai oublié d'écrire un article, donc je vais l'écrire!
Le problème reçoit une dichotomie. Il examine le diamètre de l'arbre et conçoit un algorithme qui renvoie la longueur du plus long chemin du nœud entre les deux points.
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Dans ce cas, 3 est renvoyé.
# 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: 40 ms, faster than 89.86% of Python3 online submissions for Diameter of Binary Tree.
# Memory Usage: 16 MB, less than 34.48% of Python3 online submissions for Diameter of Binary Tree.
La profondeur est mesurée par la recherche de priorité de profondeur, et comme il s'agit du diamètre, elle passera éventuellement par le parent, de sorte qu'elle peut être résolue en ajoutant +1.
Si vous pouvez comprendre la structure de l'arborescence, vous pouvez l'implémenter relativement facilement.
~~ On ne peut pas dire que c'était sobre ... ~~
Jusqu'à ici pour cette fois. Je vous remercie pour votre travail acharné!
Recommended Posts