23.05.27 Today’s Leetcode

1406. Stone Game III (hard)

prefixSum and DFS

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:

        arr = [0]
        for num in stoneValue[::-1]:
            arr.append(arr[-1] + num)
        arr = arr[::-1]

        @cache
        def dfs(cur):
            if cur >= len(stoneValue):
                return 0
            res = -math.inf
            prev = cur
            for i in range(3):
                cur += 1
                res = max(res, arr[prev] - dfs(cur))
            return res

        a = dfs(0)
        b = arr[0] - a
        if a > b: return "Alice"
        elif a < b: return "Bob"
        else: return "Tie"

2679. Sum in a Matrix (medium)

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        m, n = len(nums), len(nums[0])
        arr = []
        for row in nums:
            temp = []
            for num in row:
                heappush(temp, -num)
            arr.append(temp)

        res = []
        for i in range(n):
            temp = -1
            for j in range(m):
                temp = max(temp, -heappop(arr[j]))
            res.append(temp)

        return sum(res)

388. Longest Absolute File Path (medium)

Stack

class Solution:
    def lengthLongestPath(self, s: str) -> int:
        paths = s.split('\n')
        stack, ans = [0], 0 # initialize the stack with 0 to handle the case when there's no directory
        for path in paths:
            p = path.split('\t')
            depth, name = len(p) - 1, p[-1]
            while len(stack) > depth + 1: # pop directories that are deeper than the current one
                stack.pop()
            if '.' in name: # if it's a file, update the answer
                ans = max(ans, stack[-1] + len(name))
            else: # if it's a directory, push its length to the stack
                stack.append(stack[-1] + len(name) + 1)
        return ans