力扣周赛394(20240421)

第三题100290. 使矩阵满足条件的最少操作次数

  • 题目大意：给定一个大小为 m x n 的二维矩形 grid，每次操作可以将任意格子的值修改为任意非负整数。完成所有操作后，需要确保每个格子 grid[i][j] 的值满足以下条件：如果下面相邻格子存在的话，它们的值相等；如果右边相邻格子存在的话，它们的值不相等。返回需要的最少操作次数。

记忆化

  • 实现思路：首先，统计每一列中各个数字的出现次数。然后，使用动态规划的方法，定义函数dfs(i, pre)，表示处理到第i列时，前一列的值为pre时的最大操作次数。在dfs中，对于当前列的每个数字，考虑是否修改当前列的值，然后递归处理下一列。利用缓存来避免重复计算。最后返回总的操作次数。
class Solution:
    # 如果你想不出来，1、你不知道这个知识点 2、 你知道这个知识点但是方向错了
    def minimumOperations(self, g: List[List[int]]) -> int:
        n, m = len(g), len(g[0])
        cnt = [[0]*10 for _ in range(m)]

        for row in g:
            for k, v in enumerate(row):
                cnt[k][v]+=1
        
        @cache
        def dfs(i, pre):
            if i<0:
                return 0
            res = 0
            for v in range(10):
                if v!=pre:
                    res = max(res, dfs(i-1, v) + cnt[i][v])
            return res

        return m*n - dfs(m-1, -1)

递推

  • 实现思路：首先，对每一列进行遍历，并统计每列中每个数字的出现次数。然后，通过动态规划的方法，使用两个变量f0和f1分别表示当前列处理时，前一列最大能保留的个数和次大能够保留的个数。接着，通过遍历每列中的每个数字，计算当前列的最大操作次数，并更新f0和f1。最后返回总的操作次数。
class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        f0, f1, pre = 0, 0, -1
        for col in zip(*grid):
            mx, mx2, x = f0, f1, -1
            for v, c in Counter(col).items():
                res = (f0 if v!=pre else f1) + c 
                if res > mx:
                    mx, mx2, x = res, mx, v
                elif res > mx2:
                    mx2 = res
            f0, f1, pre = mx, mx2, x
        return m*n - f0

第四题100276. 最短路径中的边

  • 题目大意：给定一个包含n个节点的无向带权图，节点编号从0到n-1，总共有m条边。对于节点0为出发点，节点n-1为结束点的所有最短路，需要返回一个长度为m的布尔数组，如果edges[i]至少在其中一条最短路上，则answer[i]为true，否则为false。

  • 实现思路：首先构建图的邻接表表示。然后使用Dijkstra算法求解最短路径，并记录最短路径的长度。接着，从结束点开始反向遍历最短路径，标记经过的边。最后返回标记结果。

class Solution:
    # 多动脑子，把外界的干扰降到最低，人生永远充满着干扰
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        m = len(edges)
        g = defaultdict(list)
        INF = 0x3f3f3f3f
        dis, st = [INF]*(n+5), [False]*(n+5)

        for i, val in enumerate(edges):
            x, y, w = val
            g[x].append((y, w, i))
            g[y].append((x, w, i))

        def dijkstra():
            dis[0]=0
            h=[]
            heappush(h, (0, 0))
            while h:
                dist, ver = heappop(h)
                if st[ver]:
                    continue
                st[ver]=True
                for y, w, _ in g[ver]:
                    if dis[y]>dis[ver]+w:
                        dis[y]=dis[ver]+w
                        heappush(h, (dis[y], y))
            if dis[n-1]==INF:
                return -1
            else:
                return dis[n-1]
        res = [False]*m
        dn = dijkstra()
        if dn==-1:
            return res
        
        q = deque()
        q.append(n-1)
        while q:
            f = q.popleft()
            for y, w, i in g[f]:
                if dis[y]+w == dis[f]:
                    res[i]=True
                    q.append(y)

        return res