23.02.24 Today’s Leetcode

1675. Minimize Deviation in Array (hard)

Priority-Queue Approach
모든 수를 짝수로 만들고, 어짜피 deviation의 minimum은 minimum과 maximum 그 사이의 어딘가에 있을테니 짝수중 가장 큰 수 부터 2로 나누어 deviation을 계산한다.

import heapq

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        if not nums:
            return float('inf')
        
        evens = []
        min_val = float('inf')
        
        for num in nums:
            if num % 2 == 0:
                heapq.heappush(evens, -num)
                min_val = min(num, min_val)
            else:
                heapq.heappush(evens, -num * 2)
                min_val = min(num * 2, min_val)
                
        res = float('inf')
        while evens[0] % 2 == 0:
            max_val = -heapq.heappop(evens)
            res = min(res, max_val - min_val)
            new_num = max_val // 2
            heapq.heappush(evens, -new_num)
            min_val = min(new_num, min_val)
            
        res = min(-evens[0] - min_val, res)
        return res

344. Reverse String (easy)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for i in range(len(s) // 2):
            s[i], s[-(i + 1)] = s[-(i + 1)], s[i]

        return s

557. Reverse Words in a String III (easy)

class Solution:
    def reverseWords(self, s: str) -> str:
        split = s.split()
        split = [word[::-1] for word in split]
        return ' '.join(split) 

111. Minimum Depth of Binary Tree (easy)

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        res = 10**9
        if root.left:
            res = min(res, self.minDepth(root.left))
        if root.right:
            res = min(res, self.minDepth(root.right))
        if res != 10**9:
            return res + 1
        return res

105. Construct Binary Tree from Preorder and Inorder Traversal (medium)

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0:
            return None
        head_value = preorder[0]
        node = TreeNode(head_value)
        if len(preorder) == 1:
            return node
        index = inorder.index(head_value)
        node.left = self.buildTree(preorder[1:1 + index], inorder[:index])
        node.right = self.buildTree(preorder[1 + index:], inorder[index + 1:])
        return node