[Mock] Microsoft 10

1469. Find All The Lonely Nodes

외동이면 Lonely Node

My Answer 1: Accepted (Runtime: 48 ms - 90.07% / Memory Usage: 14.8 MB - 82.66%)

# 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 getLonelyNodes(self, root: TreeNode) -> List[int]:
        ans = []
        queue = [root]

        while queue:
            r = queue.pop(0)

            if r:
                if r.left and r.right is None:
                    ans.append(r.left.val)
                elif r.right and r.left is None:
                    ans.append(r.right.val)
                
                if r.left:
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)

        return ans

level-order 로 보면서 left, right 중에 하나만 있으면 ans 에 append

---

1381. Design a Stack With Increment Operation

Design a stack which supports the following operations.

Implement the CustomStack class:

• CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
• void push(int x) Adds x to the top of the stack if the stack hasn't reached the maxSize.
• int pop() Pops and returns the top of stack or -1 if the stack is empty.
• void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

My Answer 1: Accepted (Runtime: 136 ms - 53.74% / Memory Usage: 14.8 MB - 92.13%)

class CustomStack:

    def __init__(self, maxSize: int):
        self.stack = []
        self.size = maxSize

    def push(self, x: int) -> None:
        if len(self.stack) != self.size:
            self.stack.append(x)

    def pop(self) -> int:
        if len(self.stack) == 0:
            return -1
        return self.stack.pop()

    def increment(self, k: int, val: int) -> None:
        length = len(self.stack)
        if k < len(self.stack):
            length = k
        for i in range(length):
            self.stack[i] += val


# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)

1. init
   stack 과 size 생성

2. push
   stack 의 크기가 maxSize 보다 작을 경우에만 append

3. pop
   stack 이 empty 면 return -1 아니면 pop() 으로 맨 마지막 값 return

4. increment
   stack 의 길이와 k 중에 짧은 것으로 length 를 잡고 0 ~ length 값에 val 를 더해줌

Solution 1: Accepted (Runtime: 80 ms - 95.37% / Memory Usage: 14.9 MB - 74.31%)

class CustomStack:

    def __init__(self, maxSize: int):
        self.n = maxSize
        self.stack = []
        self.inc = []

    def push(self, x: int) -> None:
        if len(self.inc) < self.n:
            self.stack.append(x)
            self.inc.append(0)

    def pop(self) -> int:
        if not self.inc: return -1
        if len(self.inc) > 1:
            self.inc[-2] += self.inc[-1]
        return self.stack.pop() + self.inc.pop()

    def increment(self, k: int, val: int) -> None:
        if self.inc:
            self.inc[min(k, len(self.inc)) - 1] += val


# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)

size, stack, inc 세가지를 이용하는데

increment 에서 더해지는 val 값을 stack 에 저장하지 않고 inc 에 저장해서
pop 할 때 stack 값 + inc 값 return

increment 에서 반복문을 사용하지 않아서 더 빠른가봅니다..

O(1) time & space 라네요