802. 找到最终的安全状态

802. 找到最终的安全状态

标记环

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        color = [0 for i in range(len(graph))]
        return [i for i in range(len(graph)) if self.process(i, color, graph)]

    def process(self, x, color, graph):
        if color[x] > 0:
            return color[x] == 2
        color[x] = 1
        for i in graph[x]:
            if not self.process(i, color, graph):
                return False
        color[x] = 2
        return True

210. 课程表 II

210. 课程表 II

拓扑排序

from collections import deque
from typing import List


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        new_prerequisites = [[] for i in range(numCourses)]
        du = {i: 0 for i in range(numCourses)}
        queue = deque([])
        for i in range(len(prerequisites)):
            du[prerequisites[i][0]] += 1
            new_prerequisites[prerequisites[i][1]].append(prerequisites[i][0])
        for k, v in du.items():
            if v == 0:
                queue.append(k)
        res = []
        while queue:
            popped_course = queue.popleft()
            du.pop(popped_course)
            res.append(popped_course)
            for i in range(len(new_prerequisites[popped_course])):
                du[new_prerequisites[popped_course][i]] -= 1
                if du[new_prerequisites[popped_course][i]] <= 0:
                    queue.append(new_prerequisites[popped_course][i])
        return res if not bool(du) else []
        

207. 课程表

207. 课程表

拓扑排序

from collections import deque


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        new_prerequisites = [[] for i in range(numCourses)]
        du = {i: 0 for i in range(numCourses)}
        queue = deque([])
        for i in range(len(prerequisites)):
            du[prerequisites[i][0]] += 1
            new_prerequisites[prerequisites[i][1]].append(prerequisites[i][0])
        for k, v in du.items():
            if v == 0:
                queue.append(k)
        while queue:
            popped_course = queue.popleft()
            du.pop(popped_course)
            for i in range(len(new_prerequisites[popped_course])):
                du[new_prerequisites[popped_course][i]] -= 1
                if du[new_prerequisites[popped_course][i]] <= 0:
                    queue.append(new_prerequisites[popped_course][i])
                    # du.pop(new_prerequisites[popped_course][i])
        return not bool(du)

面试题 10.01. 合并排序的数组

面试题 10.01. 合并排序的数组

应该倒序处理

from typing import List


class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        pa = 0
        for pb in range(n):
            while pa < m:
                if B[pb] < A[pa]:
                    for i in range(len(A) - 1, pa, -1):
                        A[i] = A[i - 1]
                    A[pa] = B[pb]
                    m += 1
                    break
                pa += 1
            if pa >= m:
                A[pa] = B[pb]
                pa += 1

2679. 矩阵中的和

2679. 矩阵中的和

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        m = len(nums)
        n = len(nums[0])
        for i in range(m):
            nums[i].sort()
        ans = 0
        for i in range(n):
            max_list = []
            for j in range(m):
                max_list.append(nums[j].pop())
            ans += max(max_list)
        return ans