[Mock] Facebook 5

349. Intersection of Two Arrays

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

My Answer 1: Accepted (Runtime: 48 ms - 56.61% / Memory Usage: 14.4 MB - 72.39%)

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = set()
        
        nums1.sort()
        nums2.sort()
        
        i = 0
        j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                ans.add(nums1[i])
                i += 1
                j += 1
            else:
                if nums1[i] < nums2[j]:
                    i += 1
                else:
                    j += 1
        
        return list(ans)

nums1, nums2 정렬 후 같은 숫자들만 ans 에 저장

숫자가 다르면 작은 숫자에 해당하는 인덱스 값 + 1

중복을 없애기 위해 set 로 쓰다가 list 로 return

My Answer 2: Accepted (Runtime: 48 ms - 56.61% / Memory Usage: 14.3 MB - 90.15%)

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        
        n1 = collections.Counter(nums1)
        n2 = collections.Counter(nums2)
        
        if len(n1) < len(n2):
            n1, n2 = n1, n2
        else:
            n1, n2 = n2, n1
        
        for k, v in n1.items():
            if k in n2:
                ans.append(k)
        
        return ans

중복이 포함되지 않는다면 Counter 가 더 편할듯

각각 Counter 를 구해주고 둘 중에 더 짧은 걸 n1 으로, 긴 걸 n2 로 정한 후

두가지 모두에 포함되는 값만 ans 에 저장

---

865. Smallest Subtree with all the Deepest Nodes

Given the root of a binary tree, the depth of each node is the shortest distance to the root.

Return the smallest subtree such that it contains all the deepest nodes in the original tree.

A node is called the deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is tree consisting of that node, plus the set of all descendants of that node.

Note: This question is the same as 1123: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/

My Answer 1: Accepted (Runtime: 32 ms - 84.89% / Memory Usage: 14.5 MB - 23.70%)

# 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 subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        ## pre-order
        
        ## [1] deepest node 들의 경로 알아내기
        ## deepest way -> self.deeplist 에 저장
        def func(root, cnt, way):
            if root is None:
                ## 더 깊은 걸 만나면 self.deeplist 초기화 후 update
                if len(way) > len(self.deeplist[0]):
                    self.deeplist = []
                    self.deeplist.append(way)
                ## 같은 길이의 way 추가
                elif len(way) == len(self.deeplist[0]):
                    self.deeplist.append(way)
                return
            
            ## self.deep 에는 deepest 길이 저장
            if cnt > self.deep:
                self.deep = cnt
            
            func(root.left, cnt+1, way+[root.val])
            func(root.right, cnt+1, way+[root.val])
        
        self.deep = 0
        self.deeplist = [[]]
        
        func(root, 0, [])
        
        ## [2] self.deeplist 중에 공통되는 노드의 값 찾기 (s)
        s = self.deeplist[0][0]
        for i in range(len(self.deeplist[0])):
            tmp = self.deeplist[0][i]
            for j in range(len(self.deeplist)):
                if tmp != self.deeplist[j][i]:
                    tmp = -1
                    break
            if tmp != -1:
                s = tmp
            else:
                break
        
        ## [3] 실제 s 값을 가진 노드 찾기
        def func2(root, s):
            if root is None:
                return None
            
            if root.val == s:
                return root
            
            a = func2(root.left, s)
            b = func2(root.right, s)
            
            if a:
                return a
            if b:
                return b
        
        return func2(root, s)

1. deepest node 들의 경로 알아내기
2. self.deeplist 중에 공통되는 노드의 값 찾기 (s)
3. 실제 s 값을 가진 노드 찾기

시간이 없어서 이런 노가다로라도 풀어봤읍니다..^^

Solution 1: Accepted (Runtime: 40 ms - 24.08% / Memory Usage: 14.4 MB - 58.83%)

# 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 subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        def deep(root):
            if not root: return 0, None
            l, r = deep(root.left), deep(root.right)
            if l[0] > r[0]: return l[0] + 1, l[1]
            elif l[0] < r[0]: return r[0] + 1, r[1]
            else: return l[0] + 1, root
        return deep(root)[1]

이렇게 간단히 풀 수 있다니..?

근데 이해는 못함...

if root == null,
return pair(0, null)

if left depth == right depth,
deepest nodes both in the left and right subtree,
return pair (left.depth + 1, root)

if left depth > right depth,
deepest nodes only in the left subtree,
return pair (left.depth + 1, left subtree)

if left depth < right depth,
deepest nodes only in the right subtree,
return pair (right.depth + 1, right subtree)

왼쪽, 오른쪽의 깊이를 비교
...한다고 하네요