[Mock] Facebook 9

958. Check Completeness of a Binary Tree

Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

My Answer 1: Wrong Answer (111 / 119 test cases passed.)

# 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 isCompleteTree(self, root: TreeNode) -> bool:
        queue = [root]
        level = 0
        is_full = 1
        
        while queue:
            num = len(queue)
            if is_full == 0:
                return False
            for i in range(num):
                r = queue.pop(0)
                if i == num-1 and r.left is None and r.right:
                    return False
                if i != num-1:
                    if (r.left and r.right is None) or (r.left is None and r.right):
                        return False
                
                if r.left:
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)
            
            if 2 ** level != num:
                is_full = 0
            level += 1
        
        return True

level-order 로 보면서 부모들이 꽉 차지 않았거나 (is_full == 0)
자식이 오른쪽에만 있을 경우,
마지막 자식이 아닌데 한 자식만 있을 경우 return False

뭔가 풀릴 거 같았는데 시간이 부족했네요..^^

Solution 1: Accepted (Runtime: 32 ms - 87.16% / Memory Usage: 14.2 MB - 52.87%)

# 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 isCompleteTree(self, root: TreeNode) -> bool:
        bfs = [root]
        i = 0
        while bfs[i]:
            bfs.append(bfs[i].left)
            bfs.append(bfs[i].right)
            i += 1
        return not any(bfs[i:])

BFS 이용

None 값도 다 넣어줘서 None 노드 뒤에 다른 노드가 있는지만 보면 됨..

천재 같다~~

---

1027. Longest Arithmetic Subsequence

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Recall that a subsequence of an array nums is a list nums[i1], nums[i2], ..., nums[ik] with 0 <= i1 < i2 < ... < ik <= nums.length - 1, and that a sequence seq is arithmetic if seq[i+1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

My Answer 1: Time Limit Exceeded (38 / 62 test cases passed.)

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        ans = 0
        
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                dif = nums[j] - nums[i]
                tmp = 2  # [nums[i], nums[j]]
                prev = nums[j]
                for k in range(j+1, len(nums)):
                    if nums[k] - prev == dif:
                        tmp += 1
                        prev = nums[k]
                ans = max(ans, tmp)
        
        return ans

무려 3중 for 문이를 돌려서 같은 차이 값을 갖는 숫자를 만날 때마다 tmp + 1

타임리밋 걸릴 줄 알았읍니다...^^

Solution 1: Accepted (Runtime: 3472 ms - 52.48% / Memory Usage: 66.8 MB - 22.11%)

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        dp = {}
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                dp[j, nums[j] - nums[i]] = dp.get((i, nums[j] - nums[i]), 1) + 1
        return max(dp.values())

DP 사용

dp[index, diff] 에 i 와 이어진 같은 diff 의 값들 + 1 을 저장

dp 값을 가져올 때 없으면 default 값 = 1