23.05.05 Today’s Leetcode

1456. Maximum Number of Vowels in a Substring of Given Length (medium)

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        n = len(s)
        counter = Counter(s[:k])
        res = -1
        for i in range(k, n):
            res = max(res, counter['a'] + counter['e'] + counter['i'] + counter['o'] + counter['u'])
            a, b = s[i], s[i - k]
            counter[a] += 1
            counter[b] -= 1
        
        res = max(res, counter['a'] + counter['e'] + counter['i'] + counter['o'] + counter['u'])
        
        return res

1457. Pseudo-Palindromic Paths in a Binary Tree (medium)

class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:

        def check_palindrome(his):
            odd = even = 0
            for num in his:
                if num % 2 == 0:
                    even += 1
                else:
                    odd += 1
            return odd <= 1

        def dfs(cur, his):
            if not cur:
                return 0
            his[cur.val] += 1
            if not cur.left and not cur.right:
                val = 1 if check_palindrome(his) else 0
                his[cur.val] -= 1
                return val
            
            temp = 0
            temp += dfs(cur.left, his)
            temp += dfs(cur.right, his)
            his[cur.val] -= 1

            return temp
        
        return dfs(root, [0] * 10)

1458. Max Dot Product of Two Subsequences (hard)

class Solution:
    def maxDotProduct(self, A, B):
        n, m = len(A), len(B)
        dp = [[0] * (m) for i in range(n)]
        for i in range(n):
            for j in range(m):
                dp[i][j] = A[i] * B[j]
                if i and j: dp[i][j] += max(dp[i - 1][j - 1], 0)
                if i: dp[i][j] = max(dp[i][j], dp[i - 1][j])
                if j: dp[i][j] = max(dp[i][j], dp[i][j - 1])
        return dp[-1][-1]

497. Random Point in Non-overlapping Rectangles (medium)

넓이를 통한 접근.

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.areas = []
        self.total_area = 0
        
        # Calculate the total area covered by all the rectangles
        for rect in rects:
            area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1)
            self.total_area += area
            self.areas.append(self.total_area)
        
    def pick(self) -> List[int]:
        # Generate a random integer between 0 and the total area covered by all the rectangles
        r = random.randint(1, self.total_area)
        
        # Loop through each rectangle, subtracting its area from r
        for i in range(len(self.rects)):
            if r <= self.areas[i]:
                # Once we find the rectangle, generate a random point inside it
                rect = self.rects[i]
                x = random.randint(rect[0], rect[2])
                y = random.randint(rect[1], rect[3])
                return [x, y]