[Mock] Random 24

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

左、右の普通の木の形だと思っていましたが...そうでなければ.
そのため、子供一人一人を見た後、valの値をself.ansに追加します.

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数で計算すると、ansに1つの数字しか付加されません.
でも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の2つのグループに分けた.なんだろう.
私は本当にビット演算を知らない...
https://leetcode.com/problems/single-number-iii/discuss/68901/Sharing-explanation-of-the-solution
https://bhsbhs235.github.io/algorithm/2019/10/19/leetcode260.html