23.04.09 Today’s Leetcode

1857. Largest Color Value in a Directed Graph (hard)

failed 39/83

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        tree = defaultdict(list)
        m, n = len(edges), len(colors)
        for a, b in edges:
            if a == b:
                return -1
            tree[a].append(b)
        
        print(tree)
        
        res = -1
        hasCycle = False
        visited = [False] * n
        def dfs(cur, prev, his):
            nonlocal hasCycle, res
            if hasCycle or visited[cur]:
                hasCycle = True
                return

            visited[cur] = True
            his[colors[cur]] += 1

            res = max(res, max(his.values()))

            for node in tree[cur]:
                if node != prev:
                    dfs(node, cur, his)

            visited[cur] = False
            his[colors[cur]] -= 1
        
        if hasCycle:
            return -1

        for i in range(n):
            dfs(i, -1, defaultdict(int))
        return res

What is indegree in Graph?

class Solution:
    def solve1(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        graph = collections.defaultdict(list)
        indegrees = [0] * n
        dp = [[0] * 26 for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            indegrees[v] += 1

        q = collections.deque()
        for i in range(n):
            if indegrees[i] == 0:
                q.append(i)

        while q:
            u = q.popleft()
            dp[u][ord(colors[u])-ord('a')] += 1
            for v in graph[u]:
                # different u could merge in a node but not form a cycle
                # u1 \
                # u2 - v ; we find the max of colors from u1, u2, and u3 in v
                # u3 /
                dp[v] = list(map(max, dp[u], dp[v]))
                indegrees[v] -= 1
                if indegrees[v] == 0:
                    q.append(v)

        # tricky on determine if a graph has a cycle
        return -1 if sum(indegrees) else max(max(dp[i]) for i in range(n))
    
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        return self.solve1(colors, edges)

740. Delete and Earn (medium)

TLE : 23/50

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        counter = Counter(nums)
        res = 0
        def dfs(cur, his):
            nonlocal res
            res = max(res, cur)
            keys = set(his.keys())
            for key in keys:
                if his[key] == 0:
                    continue
                a, b, c = his[key - 1], his[key], his[key + 1]
                his[key - 1] = his[key] = his[key + 1] = 0
                dfs(cur + key * b, his)
                his[key - 1], his[key], his[key + 1] = a, b, c
        
        dfs(0, counter)
        return res

class Solution:

    def deleteAndEarn(self, nums: List[int]) -> int:
        list1 = [0] * 10001
        for i in nums:
            list1[i] += i
        rob1 = rob2 = 0
        for n in list1:
            rob1, rob2 = rob2, max(rob1 + n,rob2)
        return rob2