Leetcode第344场周赛解题报告

又是手速场

2682. 找出转圈游戏输家

知识点：模拟
复杂度：$O(n)$

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]: 
        vis = [0] * n
        s = 1
        now = 0
        while vis[now] == 0:
            vis[now] += 1
            now += s * k
            s += 1
            now %= n
        ans = []
        for i in range(n):
            if vis[i] == 0:
                ans.append(i+1)
        return ans

2683. 相邻值的按位异或

知识点：模拟
复杂度：$O(n)$

from typing import List

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        n = len(derived)
        now = 0
        for i in range(n - 1):
            now = derived[i] ^ now

        if now ^ 0 == derived[n - 1]:
            return True

        now = 1
        for i in range(n - 1):
            now = derived[i] ^ now

        if now ^ 1 == derived[n - 1]:
            return True

        return False

2684. 矩阵中移动的最大次数

知识点：记忆化搜索
复杂度：$O(n)$
经典寻路问题，使用@lru_cache记录搜索过程即可

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        xx,yy = len(grid[0]),len(grid)
        @lru_cache(maxsize=None)
        def dfs(x,y):
            n = grid[y][x]
            mx = 0
            for dx,dy in [[1,-1],[1,0],[1,1]]:
                nx , ny = x + dx, y + dy
                if xx > nx >= 0 and yy > ny >= 0 \
                    and grid[ny][nx] > n:
                    mx = max(mx, dfs(nx,ny)+1)
            return mx
        return max(dfs(0,i) for i in range(yy))

2685. 统计完全连通分量的数量

知识点：搜索
复杂度：$O(2*n)$

• 1. 找到所有联通快
• 2. 统计是否完全联通

from typing import List

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        def dfs(node, visited, graph):
            visited.add(node)
            component.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor, visited, graph)
        
        def is_complete_component(component, n):
            size = len(component)
            for node in component:
                if len(graph[node]) != size - 1:
                    return False
            return True

        graph = {i: [] for i in range(n)}
        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])

        visited = set()
        count = 0
        for i in range(n):
            if i not in visited:
                component = set()
                dfs(i, visited, graph)
                if is_complete_component(component, n):
                    count += 1

        return count