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 31 "581. Le sous-tableau continu non trié le plus court" à partir de zéro
En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.
Twitter Je le fais.
Au fait, cela a duré un mois. Toutes nos félicitations.
437. Path Sum III Le niveau de difficulté est facile. Facile parmi les 100 questions les plus appréciées, insérez ceci et il ne reste que 3 questions.
Chaque nœud reçoit une dichotomie qui contient une valeur entière.
Trouvez le nombre de chemins qui additionnent les valeurs des nœuds pour donner une valeur particulière «somme».
La route n'a pas besoin de commencer ou de se terminer au niveau du parent ou de la feuille, mais elle doit se déplacer vers le bas (uniquement du nœud parent au nœud enfant).
Notez que le nombre de nœuds dans l'arborescence est de 1 000 ou moins et que la plage de valeurs est comprise entre -1 000 000 et 1 000 000.
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
- 5 -> 3
Je l'ai résolu avec dfs en utilisant récursif.
# 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 pathSum(self, root: TreeNode, sum: int) -> int:
def dfs(root,sums,start):
if not root:
return 0
sums -= root.val
if sums == 0:
self.ans += 1
dfs(root.left,sums,False)
dfs(root.right,sums,False)
if start:
dfs(root.left,sum,True)
dfs(root.right,sum,True)
dfs(root,sum,True)
return self.ans
# Runtime: 940 ms, faster than 24.67% of Python3 online submissions for Path Sum III.
# Memory Usage: 15.1 MB, less than 6.82% of Python3 online submissions for Path Sum III.
Au début, je pensais que je pourrais simplement appeler avec root et sums, mais je ne pouvais pas écrire avec ça seul (je pourrais peut-être l'écrire, mais je ne pouvais pas y penser maintenant), alors quand j'ai regardé dans la discussion Presque la même réponse, où boolean est utilisé pour traiter le nœud actuel comme point de départ. Je l'utilise, et comme j'ai pu l'implémenter très proprement, je le posterai tel quel.
Même ainsi, les gens avec des algorithmes puissants sont incroyables ...
Vous devez travailler plus dur.
S'il y a une bonne réponse, je l'ajouterai.
Recommended Posts