Public Interview LeetCode 27 Aug

gistfile1.txt

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