73. 矩阵置零

73. 矩阵置零

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 0:
                    self.set_ele(matrix, i, j)
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] is None:
                    matrix[i][j] = 0

    def set_ele(self, matrix, x, y):
        for i in range(len(matrix)):
            if matrix[i][y] == 0:
                continue
            matrix[i][y] = None
        for i in range(len(matrix[x])):
            if matrix[x][i] == 0:
                continue
            matrix[x][i] = None

LCR 120. 寻找文件副本

LCR 120. 寻找文件副本

class Solution:
    def findRepeatDocument(self, documents: List[int]) -> int:
        s = set()
        for i in range(len(documents)):
            if documents[i] in s:
                return documents[i]
            s.add(documents[i])

25. K 个一组翻转链表

25. K 个一组翻转链表

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        head = ListNode(0, head)
        p = head
        length = 0
        while p.next:
            p = p.next
            length += 1
        tail = ListNode(0, None)
        p.next = tail
        front_prev = head
        for i in range(length // k):
            front = front_prev.next
            end = front
            for j in range(k - 1):
                end = end.next
            end_next = end.next
            end = self.reverse(front_prev, front, end_next)
            front_prev = end
        head = head.next
        p = head
        while p.next != tail:
            p = p.next
        p.next = None
        return head


    def reverse(self, front_prev, front, end_next):
        prev = None
        curr = front
        while curr != end_next:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        front_prev.next = prev
        front.next = end_next
        return front

1504. 统计全 1 子矩形

1504. 统计全 1 子矩形

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        ans = 0
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                ans += self.calc(mat, i, j)
        return ans

    def calc(self, matrix, x, y) -> int:
        if matrix[x][y] != 1:
            return 0
        i = 0
        j = 0
        cnt = -1
        while x + i < len(matrix):
            if matrix[x + i][y] == 1:
                cnt += 1
                i += 1
            else:
                break
        while y + j < len(matrix[x]):
            if matrix[x][y + j] == 1:
                cnt += 1
                j += 1
            else:
                break
        for m in range(x + 1, x + i):
            for n in range(y + 1, y + j):
                if matrix[m][n] == 1:
                    cnt += 1
                else:
                    j = n - y
                    break
        return cnt

95. 不同的二叉搜索树 II

95. 不同的二叉搜索树 II

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        return self.generate([i for i in range(1, n + 1)])

    def generate(self, candidate_val: list):
        if not candidate_val:
            return [None]
        if len(candidate_val) == 1:
            return [TreeNode(val=candidate_val[0])]
        ans = []
        for i in range(len(candidate_val)):
            left = self.generate(candidate_val[:i])
            right = self.generate(candidate_val[i + 1:])
            for j in range(len(left)):
                for k in range(len(right)):
                    ans.append(TreeNode(candidate_val[i], left[j], right[k]))
        return ans

1971. 寻找图中是否存在路径

1971. 寻找图中是否存在路径

并查集

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        path = [i for i in range(n)]

        def find(x):
            if path[x] != x:
                path[x] = find(path[x])
            return path[x]

        for i, j in edges:
            path[find(i)] = find(j)
        return find(source) == find(destination)

深度优先搜索

from collections import defaultdict


class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        path: Dict[int, list] = defaultdict(list)
        for i in range(len(edges)):
            path[edges[i][0]].append(edges[i][1])
            path[edges[i][1]].append(edges[i][0])
        detected = set()
        return self.dfs(path, source, detected, destination)

    def dfs(self, path: Dict[int, list], now: int, detected: set, destination):
        if now == destination:
            return True
        detected.add(now)
        for i in range(len(path[now])):
            if path[now][i] in detected:
                continue
            ret = self.dfs(path, path[now][i], detected, destination)
            if ret:
                return True
        return False