Skip to content

Instantly share code, notes, and snippets.

@GSkoba
Last active August 27, 2022 17:07
Show Gist options
  • Save GSkoba/3de05b4bdeb26beb4abfdd677b4d0da1 to your computer and use it in GitHub Desktop.
Save GSkoba/3de05b4bdeb26beb4abfdd677b4d0da1 to your computer and use it in GitHub Desktop.
Public Interview LeetCode 27 Aug
https://leetcode.com/problems/deepest-leaves-sum/
1. In root (bin tree)
Сумму самых глубоких вершин в этом дереве
2
/ \
1 3
/ / \
4 1 2
/
2
2 - 1 - 3 - 4 - 5 - 6
Node:
left
right
val
def findSum(root):
queue = [(root, 0)]
sums = defaultdict(int)
while queue:
node, level = queue.pop(0)
sums[level] += node.val
if node.right:
queue.append((node.right, level+1))
if node.left:
queue.append((node.left, level+1))
return sums[max(sums.keys())]
2
1 3
q = [(1,1), (3, 1)]
{
0: 2,
1: 4,
}
https://leetcode.com/problems/find-all-anagrams-in-a-string/
s, p
найти все анаграммы p в s
ret все начальные индексы
s = "abacbab"
p = "aba"
[0, 3]
start, end = 0, 2
counterP = {a: 2, b: 1}
posA = {a: 2, b: 1}
res = []
res = [0]
start = 1
posA = {a: 1, b: 1, c: 1}
end = 3
res = [0]
def findAnagrams(s, p) -> List[int]:
if len(s) < len(p):
return []
counter_p = Counter(p) # len P
start, end = 0, len(p) - 1
possibleAnagram = s[start:end] # len p
res = []
while end < len(s):
if counter_p == possibleAnagram:
res.append(start)
start_char = s[start]
possibleAnagram[start_char] -= 1
if possibleAnagram[start_char] == 0:
del possibleAnagram[start_char]
start += 1
end += 1
if end < len(s):
end_char = s[end]
possibleAnagram[end_char] += 1
return res
len(s) * len(p) if len(p) == 1 => len(s)^2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment