[Mock] Random 24

shsh·2021년 6월 22일

Mock-Phone-Interview

590. N-ary Tree Postorder Traversal

260. Single Number III

Mock

목록 보기

66/93

590. N-ary Tree Postorder Traversal

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

My Answer 1: Accepted (Runtime: 52 ms - 63.24% / Memory Usage: 16 MB - 67.10%)

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        def func(r):
            if r is None:
                return
            
            for i in range(len(r.children)):
                func(r.children[i])
            self.ans.append(r.val)
        
        self.ans = []
        func(root)
        
        return self.ans

left, right 있는 일반 트리 형태일 줄 알았는데.. 아니었음

그래서 각 children 을 다 보고나서 val 값을 self.ans 에 append

260. Single Number III

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

My Answer 1: Accepted (Runtime: 56 ms - 86.99% / Memory Usage: 16.2 MB - 18.73%)

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        cnt = collections.Counter(nums)
        
        ans = []
        for k, v in cnt.items():
            if v == 1:
                ans.append(k)
        
        return ans

O(N), O(1) 을 신경쓰지 않고 그냥 냅다 풀었을 때...

Counter 로 개수 세준 후 1 개인 숫자들만 ans 에 append

근데 Medium 인 이유가 있었다...
linear runtime complexity & only constant extra space

도저히 안떠오름...

Solution 1: Accepted (Runtime: 56 ms - 86.99% / Memory Usage: 16 MB - 43.19%)

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # "xor" all the nums 
        tmp = 0
        for num in nums:
            tmp ^= num
        # find the rightmost "1" bit
        i = 0
        while tmp & 1 == 0:
            tmp >>= 1
            i += 1
        tmp = 1 << i
        # compute in two seperate groups
        first, second = 0, 0
        for num in nums:
            if num & tmp:
                first ^= num
            else:
                second ^= num
        return [first, second]

모든 수에 XOR 을 해주면 짝이 있는 숫자들은 서로 만나서 0 이 되고 single number 들만 남음

맨마지막 값이 1 인 위치를 찾아서 0 과 1 두 그룹으로 나누는데.. 뭘까

비트 연산은 정말 모르겠다....