Day60力扣打卡

打卡记录

在这里插入图片描述
1682分了记录下,希望下回能突破1700捏。作为一个菜鸟,知道自己很菜,一步步走到现在还是很开心的,从以前的周赛稳定1题到稳定2题,到现在的时有时无的3题。每次刷题都期盼有所长进,虽然更多的时候收到的是遗憾。最近六级 + 期末,尽量维持每日一题,等后面有空的时候再多刷刷题。


用邮票贴满网格图(二维前缀和 + 二维差分)

链接
通过贪心,在能贴邮票的地方就直接贴入尽管重叠。如何判断能贴邮票的位置,通过判断枚举不同位置上的二位前缀和,若为0则邮票可以粘贴,粘贴部分用二维差分收集,最后再累加起来,得到贴完邮票的网格图,若无位置为0则可以贴满。

class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        n, m = len(grid), len(grid[0])
        s = [[0] * (m + 1) for _ in range(n + 1)]
        for i, row in enumerate(grid):
            for j, w in enumerate(row):
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + w
        d = [[0] * (m + 2) for _ in range(n + 2)]
        for ex in range(stampHeight, n + 1):
            for ey in range(stampWidth, m + 1):
                sx, sy = ex - stampHeight + 1, ey - stampWidth + 1
                if s[ex][ey] - s[sx - 1][ey] - s[ex][sy - 1] + s[sx - 1][sy - 1] == 0:
                    d[sx][sy] += 1
                    d[sx][ey + 1] -= 1
                    d[ex + 1][sy] -= 1
                    d[ex + 1][ey + 1] += 1
        for i, row in enumerate(grid):
            for j, w in enumerate(row):
                d[i + 1][j + 1] += d[i + 1][j] + d[i][j + 1] - d[i][j]
                if w == 0 and d[i + 1][j + 1] == 0:
                    return False
        return True

相关推荐

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-15 08:18:02       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-15 08:18:02       100 阅读
  3. 在Django里面运行非项目文件

    2023-12-15 08:18:02       82 阅读
  4. Python语言-面向对象

    2023-12-15 08:18:02       91 阅读

热门阅读

  1. WPF中DataGrid设置默认选中行

    2023-12-15 08:18:02       57 阅读
  2. OpenCV开发:编译安装opencv

    2023-12-15 08:18:02       66 阅读
  3. 【✅面试编程题:如何用队列实现一个栈】

    2023-12-15 08:18:02       59 阅读
  4. AUTOSAR从入门到精通-中间件通信DDS(一)

    2023-12-15 08:18:02       61 阅读
  5. Ubuntu无法解析域名DNS指向127.0.0.53问题处理

    2023-12-15 08:18:02       67 阅读
  6. CAN总线协议

    2023-12-15 08:18:02       51 阅读
  7. SQL信息系统 - 客观题复习

    2023-12-15 08:18:02       53 阅读
  8. React Hooks学习指北

    2023-12-15 08:18:02       50 阅读