23.03.10 Today’s Leetcode

382. Linked List Random Node (medium)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.arr = []
        cur = head
        while cur:
            self.arr.append(cur.val)
            cur = cur.next

    def getRandom(self) -> int:
        return random.choice(self.arr)
        

# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()

398. Random Pick Index (medium)

class Solution:

    def __init__(self, nums: List[int]):
        self.d = defaultdict(list)
        for index, num in enumerate(nums):
            self.d[num].append(index)

    def pick(self, target: int) -> int:
        return random.choice(self.d[target])
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)

227. Basic Calculator II (medium)

Stack Approach.
문득 예전에 배웠던 prefix, postfix, infix가 생각난다. Data Structure 수업때 들었던 내용인데, 간단하게만 설명하자면 prefix는 연산이 피연산자 보다 앞에 표기되는 형식이고, postfix는 연산자가 피연산자 뒤에 표기되는 형식이다. infix는 우리가 사용하는 흔한 괄호를 이용한 방식이다. 컴퓨터에서는 postfix 연산으로 표기된 수식을 쉽게 계산할 수 있기 때문에 infix를 postfix로 변환하는 과제가 나왔었다. 과제링크

class Solution:
    def calculate(self, s):
        num, op, stack = 0, '+', [0]
        ops = {'+':lambda x, y: y, 
                '-':lambda x, y: -y, 
                '*':lambda x, y: x*y, 
                '/':lambda x, y: (int)(float(x)/float(y))}
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            if not c.isdigit() and c != ' ' or i == len(s) - 1
                prev = 0 if op in '+-' else stack.pop()
                stack.append(ops[op](prev, num))
                num, op = 0, c
                # print(stack)
        return sum(stack)

222. Count Complete Tree Nodes (medium)

# 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 countNodes(self, root: Optional[TreeNode]) -> int:

        res = 0

        def dfs(node):
            if not node:
                return (0, 0)
            left = dfs(node.left)
            right = dfs(node.right)
            height = max(left[0], right[0]) + 1
            counts = left[1] + right[1] + 1
            if 2 ** (height - 1) <= counts and counts < 2 ** height:
                nonlocal res
                res += 1
            return (height, counts)

        dfs(root)
        return res

##