[Mock] Google 13

1672. Richest Customer Wealth

You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the ith customer has in the jth bank. Return the wealth that the richest customer has.
A customer's wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

My Answer 1: Accepted (Runtime: 52 ms - 79.45% / Memory Usage: 14.2 MB - 83.95%)

class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        ans = 0
        for i in range(len(accounts)):
            ans = max(ans, sum(accounts[i]))
        
        return ans

accountsの和の中の最低価格を探し出して、ansの中に入れます

1506. Find Root of N-Ary Tree

My Answer 1: Time Limit Exceeded (37 / 39 test cases passed.)

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':
        while None in tree:
            tree.remove(None)
        
        if tree is None:
            return []
        
        num = len(tree)
        self.dic = {}
        
        def func(root, level):
            if root is None:
                return level
            
            lev = 0
            for i in range(len(root.children)):
                if root.children[i] in self.dic:
                    lev = max(lev, self.dic[root.children[i]])
                else:
                    lev = max(lev, func(root.children[i], level + 1))
            
            return level + lev
        
        for i in range(len(tree)):
            if tree[i] == None:
                continue
            self.dic[tree[i]] = func(tree[i], 1)
        
        m = max(self.dic.values())
        
        for k, v in self.dic.items():
            if v == m:
                return k
                
        return []

再帰関数を使用して各ノードのレベルを計算し、最大レベルを持つノードを返します.
レベルはdicに格納されています
childrenに既に存在する値はdicです

Solution 1: Accepted

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':        
        c = {}
        n = {}
        for node in tree:            
            n[node.val] = node
            if node.children is not None:
                for ch in node.children:                    
                    c[ch.val] = True
        for k in n:
            if k not in c:
                return n[k]
        return None

親ノードなしを返す
応用テストケースが複雑すぎて…^^

429. N-ary Tree Level Order Traversal

Given an n-ary tree, return the level order 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 - 70.71% / Memory Usage: 16.1 MB - 58.16%)

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

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if root is None:
            return []
        
        ans = [[root.val]]
        queue = [root]
        
        while queue:
            num = len(queue)    # 같은 level 의 개수
            tmp = []
            for _ in range(num):
                r = queue.pop(0)

                if r.children:
                    for i in range(len(r.children)):
                        tmp.append(r.children[i].val)
                        queue.append(r.children[i])
            if tmp:
                ans.append(tmp)
        
        return ans

rootがNoneの場合の異常処理

ans、初期値は[root.val]です.queueを使用してlevel-orderを表示

queueの長さ=各レベルのノード数
=>for文の長さをpopノードに変換し、childrenがある場合、tmpはvalを記憶し、queueはchildrenを記憶する

ansに追加されるのは、levelに1つ以上の値がある場合のみです.

この問題ではありません.^^