[Mock] Facebook 4

345. Reverse Vowels of a String

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both cases.

My Answer 1: Accepted (Runtime: 1484 ms - 5.09% / Memory Usage: 15.5 MB - 33.19%)

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = ["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"]
        v = []
        for i in range(len(s)):
            if s[i] in vowels:
                v.append(s[i])
        
        for i in range(len(s)):
            if s[i] in vowels:
                s = s[:i] + v[-1] + s[i+1:]
                v.pop()
        
        return s

vowels 에 대소문자 모음들 저장

s 에 포함된 모음들만 v 에 저장

다시 s 를 보면서 원래 모음 (s[i]) 을 v 의 맨 끝값 (v[-1]) 부터 역순으로 교환
=> s = s[:i] + v[-1] + s[i+1:] & v.pop()

문자열을 슬라이싱 하는 것보다는
리스트에 ["h", "e", "l", "l", "o"] 식으로 바꿔서 s[i] = v[-1] 하는게 더 빠름

---

515. Find Largest Value in Each Tree Row

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

My Answer 1: Wrong Answer (25 / 78 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 largestValues(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        
        ans = [root.val]
        queue = [root]
        level = 1
        cnt = 0
        m = 0
        
        while queue:
            r = queue.pop(0)
            
            if r:
                if r.left:
                    queue.append(r.left)
                    m = max(r.left.val, m)
                if r.right:
                    queue.append(r.right)
                    m = max(r.right.val, m)
                cnt += 2
            
            if cnt == 2 ** level:
                ans.append(m)
                m = 0
                cnt = 0
                level += 1
        
        return ans

트리를 level-order 로 순회하면서 각 level 마다 최댓값을 구하도록 했으나..

머리가 굳었는지 level 이 바뀌는 시점을 제대로 설정하지 못함..^^

트리가 꽉 차 있지 않다는 점이 골 때리게 했네요

Solution 1: Accepted (Runtime: 52 ms - 29.32% / Memory Usage: 16.4 MB - 60.13%)

# 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 largestValues(self, root: TreeNode) -> List[int]:
        ans = []
        if root is None:
            return ans
        queue  = [root]
        while queue:
            ans.append(max(x.val for x in queue))
            new_queue = []
            for node in queue:
                if node.left:
                    new_queue.append(node.left)
                if node.right:
                    new_queue.append(node.right)
            queue = new_queue
        return ans

노드 개수로 레벨 계산하고 할 것 없이 걍 반복문 두개 써서 level-order 로 보기..

그럼 첫번째 반복문에서 queue 에 있는 값들 중 최댓값을 ans 에 넣어주면 됨..