23.04.07 Today’s Leetcode

1020. Number of Enclaves (medium)

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= n:
                return
            if grid[x][y] == 0:
                return
            grid[x][y] = 0
            dirs = [1, 0, -1, 0, 1]
            for i in range(4):
                dfs(x + dirs[i], y + dirs[i + 1])
        
        for i in range(m):
            dfs(i, 0)
            dfs(i, n - 1)
        
        for j in range(n):
            dfs(0, j)
            dfs(m - 1, j)
        
        print(grid)
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    # dfs(i, j)
                    count += 1
        return count

1019. Next Greater Node In Linked List (medium)

class Solution:
    def nextLargerNodes(self, head):
        res, stack = [], []
        while head:
            while stack and stack[-1][1] < head.val:
                res[stack.pop()[0]] = head.val
            stack.append([len(res), head.val])
            res.append(0)
            head = head.next
        return res

394. Decode String (medium)

class Solution:
    def decodeString(self, s: str) -> str:

        def find(s):
            n = len(s)
            a, b = -1, -1
            count = 0
            for i in range(n):
                if s[i] == '[':
                    if count == 0:
                        a = i
                    count += 1
                if s[i] == ']':
                    if count > 0:
                        count -= 1
                    if count == 0:
                        b = i
                        break
            return a, b

        def dfs(s):
            if not s:
                return ''
            # print(s)
            if s.isalpha():
                return s
            if s[0].isnumeric():
                k = 0
                while s[k].isnumeric():
                    k += 1
                a, b = find(s)
                return int(s[0:k]) * dfs(s[a + 1:b]) + dfs(s[b + 1:])
            if s[0].isalpha():
                return s[0] + dfs(s[1:])
            return ''
        
        return dfs(s)

416. Partition Equal Subset Sum (medium)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_v = sum(nums)
        n = len(nums)
        if sum_v % 2 == 1:
            return False

        dp = [[-1] * ((sum_v // 2) + 1) for _ in range(n)]
        def dfs(cur, index):
            # print(cur)
            if cur > sum_v // 2 or index >= n:
                return False
            if cur == sum_v // 2:
                return True
            if dp[index][cur] == 1:
                return True
            if dp[index][cur] == 0:
                return False
            temp = dfs(cur + nums[index], index + 1) or dfs(cur, index + 1)
            dp[index][cur] = 1 if temp else 0    
            return temp
        
        return dfs(0, 0)