thảo luận Leetcode mỗi ngày

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        def recursive_rotate(k, start):
            if k <= 1:
                return
            
            end = start + k - 1
            for i in range(0, k - 1):
                matrix[start][start + i], matrix[start + i][end], matrix[end][end-i], matrix[end-i][start] = \
                matrix[end-i][start], matrix[start][start + i], matrix[start + i][end], matrix[end][end-i]
            
            recursive_rotate(k-2, start + 1)
        
        recursive_rotate(len(matrix), 0)

n = len(matrix)
  
        def clock(i, n):
        
            k = n-i
            res = [(i, j) for j in range(i, k)] + \
            [(j, k-1) for j in range(i, k)] + \
            [(k-1, j) for j in range(i, k)[::-1]] + \
            [(j, i) for j in range(i+1, k)[::-1]]
            lst = []
            a = -1
            for v in res:
                if a != v:
                    lst.append(v)
                a = v
            return lst

        def roll(vals):
            for i in range(int(len(vals)/4)):
                a = vals.pop()
                vals.insert(0, a)
                # print(vals)
            return vals

        #%%
        for i in range(0, int(n/2)):
            lst = clock(i, n)
            vals = [matrix[val[0]][val[1]] for val in lst]
            vals = roll(vals)
            for idx, val in enumerate(vals):
                matrix[lst[idx][0]][lst[idx][1]] = vals[idx]

class Solution:
    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
        # Check if input is empty
        if not matrix or not matrix[0]:
            return []
        
        # Initialize variables, including sets used to keep track of visited cells
        num_rows, num_cols = len(matrix), len(matrix[0])
        pacific_reachable = set()
        atlantic_reachable = set()
        
        def dfs(row, col, reachable):
            # This cell is reachable, so mark it
            reachable.add((row, col))
            for (x, y) in [(1, 0), (0, 1), (-1, 0), (0, -1)]: # Check all 4 directions
                new_row, new_col = row + x, col + y
                # Check if the new cell is within bounds
                if new_row < 0 or new_row >= num_rows or new_col < 0 or new_col >= num_cols:
                    continue
                # Check that the new cell hasn't already been visited
                if (new_row, new_col) in reachable:
                    continue
                # Check that the new cell has a higher or equal height,
                # So that water can flow from the new cell to the old cell
                if matrix[new_row][new_col] < matrix[row][col]:
                    continue
                # If we've gotten this far, that means the new cell is reachable
                dfs(new_row, new_col, reachable)
        
        # Loop through each cell adjacent to the oceans and start a DFS
        for i in range(num_rows):
            dfs(i, 0, pacific_reachable)
            dfs(i, num_cols - 1, atlantic_reachable)
        for i in range(num_cols):
            dfs(0, i, pacific_reachable)
            dfs(num_rows - 1, i, atlantic_reachable)
        
        # Find all cells that can reach both oceans, and convert to list
        return list(pacific_reachable.intersection(atlantic_reachable))

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        import numpy as np
        matrix = np.array(heights)
        m, n = matrix.shape
        graph = {}
        for iy, ix in np.ndindex(m, n):
            val = matrix[iy, ix]
            paths = []
            if iy - 1 >= 0:
                if matrix[iy-1, ix] <= val:
                    paths.append((iy-1, ix))
            if ix - 1 >= 0:
                if matrix[iy, ix-1] <= val:
                    paths.append((iy, ix-1))
            if iy + 1 <= m - 1:
                if matrix[iy+1, ix] <= val:
                    paths.append((iy+1, ix))
            if ix + 1 <= n - 1:
                if matrix[iy, ix+1] <= val:
                    paths.append((iy, ix+1))
            # if len(paths) > 0:
            graph[(iy, ix)] = paths

        def reach_Pacific(visited: list) -> bool:
            for x in visited:
                if min(x) == 0:
                    return True
            return False

        def reach_Atlantic(visited: list, m: int, n: int) -> bool:
            for x in visited:
                if (x[1] == n-1) | (x[0] == m-1):
                    return True
            return False

        # node = (0, 3)
        def find_visited_a_node(node):
            stack = deque()
            visited = []
            stack.append(node)
            while len(stack) > 0:
                u = stack.pop()
                # print('pop', u)
                if u not in visited:
                    visited.append(u)
                    if reach_Pacific(visited) & reach_Atlantic(visited, m, n):
                        return True
                    for e in graph[u]:
                        if e in res:
                            return True
                        if e not in visited:
                            stack.append(e)
                            # print('add', e)
                            # visited.append(e)
            # print(visited)
            if reach_Pacific(visited) & reach_Atlantic(visited, m, n):
                return True
            else:
                return False

        res = []
        for node in graph:
            if find_visited_a_node(node):
                res.append(node)
                    
        return res