优化枚举的基本思路与进阶内容 |周末学习

简介: 优化枚举的基本思路与进阶内容 |周末学习

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 1074. 元素和为目标值的子矩阵数量 ,难度为 困难


Tag : 「前缀和」、「哈希表」


给出矩阵 matrix 和目标值 target,返回元素总和等于目标值的非空子矩阵的数量。


子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。


如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同(如:x1 != x1'),那么这两个子矩阵也不同。

 

示例 1:


网络异常,图片无法展示
|


输入:matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出:4
解释:四个只含 0 的 1x1 子矩阵。
复制代码


示例 2:


输入:matrix = [[1,-1],[-1,1]], target = 0
输出:5
解释:两个 1x2 子矩阵,加上两个 2x1 子矩阵,再加上一个 2x2 子矩阵。
复制代码


示例 3:


输入:matrix = [[904]], target = 0
输出:0
复制代码


提示:


  • 1 <= matrix.length <= 100
  • 1 <= matrix[0].length <= 100
  • -1000 <= matrix[i] <= 1000
  • -10^8108 <= target <= 10^8108


朴素二维前缀和



从题面来看显然是一道「二维前缀和」的题目,如果你还不了解「二维前缀和」,可以看看 (题解)304. 二维区域和检索 - 矩阵不可变。本题预处理前缀和的复杂度为 O(m * n)O(mn)


搜索所有子矩阵需要枚举「矩形左上角」和「矩形右下角」,复杂度是 O(m^2 * n^2)O(m2n2)


因此,如果把本题当做二维前缀和模板题来做的话,整体复杂度是 O(m^2 * n^2)O(m2n2)


数据范围是 10^2102,对应的计算量是 10^8108,处于超时边缘,但当我们枚举「矩形左上角」(i,j)(i,j) 的时候,我们只需要搜索位于 (i,j)(i,j) 的右下方的点 (p,q)(p,q) 作为「矩形右下角」,所以其实我们是取不满 m^2 * n^2m2n2 的,但仍然具有超时风险(2021/05/29 Java 测试可通过)。


代码:


class Solution {
    public int numSubmatrixSumTarget(int[][] mat, int t) {
        int n = mat.length, m = mat[0].length;
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int p = 1; p <= i; p++) {
                    for (int q = 1; q <= j; q++) {
                        if (sum[i][j] - sum[p - 1][j] - sum[i][q - 1] + sum[p - 1][q - 1] == t) ans++;
                    }
                }
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:O(m^2 * n^2)O(m2n2)
  • 空间复杂度:O(m * n)O(mn)


优化枚举 + 哈希表



上述分析是从「点」上来确定一个子矩阵,在 nnmm 同阶的情况下,复杂度是 O(n^4)O(n4) 的。


事实上,我们能从「边」的角度来确定一个子矩阵,通过枚举三条边,然后加速找第四条边的过程,这样可以将复杂度降到 O(n^3)O(n3)


这个分析思路在 (题解)363. 矩形区域不超过 K 的最大数值和 详细讲过,没有印象的同学可以翻翻。这道题一定程度上是那道题的简化版,在本题我们只需要找到矩阵和为 targettarget 的值,因此只需要使用「哈希表」来记录出现过的值即可,而在 (原题)363. 矩形区域不超过 K 的最大数值和 中,我们需要找到和不超过 kk 的最大子矩阵,因此还涉及「有序集合 + 二分」。


具体的,我们仍然需要先预处理出一个二维前缀和。然后通过枚举确定「子矩阵的上下边界」,在将「子矩阵右边界」不断右移的过程中,把「子矩阵右边界」到「原矩阵左边界」行程的矩阵和存入哈希表(因为要统计数量,存储格式为 {"面积”:"出现次数"} ),然后通过容斥原理来找到目标的「子矩阵左边界」。


假设当前我们「子矩阵的上下边界」已经固定,当枚举到某个「子矩阵右边界」时,我们先通过二维前缀和计算出「子矩阵右边界」和「原矩阵左边界」形成的矩阵和 curcur,由于我们希望找到矩阵和为 targettarget 的子矩阵,即希望找到一个「子矩阵左边界」使得矩阵和满足要求,这等价于从「哈希表」中找到一个 xx,使得 cur - x = targetcurx=target,这是一个 O(1)O(1) 操作。


网络异常,图片无法展示
|


代码:


class Solution {
    public int numSubmatrixSumTarget(int[][] mat, int t) {
        int n = mat.length, m = mat[0].length;
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        int ans = 0;
        for (int top = 1; top <= n; top++) {
            for (int bot = top; bot <= n; bot++) {
                int cur = 0;
                Map<Integer, Integer> map = new HashMap<>();
                for (int r = 1; r <= m; r++) {
                    cur = sum[bot][r] - sum[top - 1][r];
                    if (cur == t) ans++;
                    if (map.containsKey(cur - t)) ans += map.get(cur - t);
                    map.put(cur, map.getOrDefault(cur, 0) + 1);
                }
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:O(m * n^2)O(mn2)
  • 空间复杂度:O(m * n)O(mn)


进阶



  1. 【时间复杂度】在上述解法中,我们采用的是固定上下边界,移动右边界,通过哈希表找左边界的做法,复杂度为 O(m * n^2)O(mn2);自然也能改为固定左右边界,移动下边界,通过哈希表找上边界做法,复杂度为 O(m^2 * n)O(m2n)。那么我们要如何调整代码,才能最大化「哈希表」带来的优化效果呢?此时的复杂度又是多少?
  2. 【空间复杂度】我们空间复杂度的瓶颈在「二维前缀和」上,但注意到无论我们采取「固定上下边界」还是「固定左右边界」的做法,扫描原矩阵的方向都是固定的,那么是否可以不预处理「二维前缀和」呢?从而将空间复杂度降低到 O(\max(n, m))O(max(n,m)) 呢?


上述两问,你都可以在 (题解)363. 矩形区域不超过 K 的最大数值和 中找到答案。


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1074 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


相关文章
|
安全 数据安全/隐私保护 Ruby
5分钟带你重置Gitlab管理员账户密码
5分钟带你重置Gitlab管理员账户密码
3923 1
|
数据挖掘 API 开发者
​Email API有哪些,最好的3个API接口有哪些
Email API如SendGrid、Mailgun和AOKSend是企业自动化邮件通信的关键工具。它们提供邮件发送、接收和管理功能,提升效率,优化客户体验。SendGrid以其高可靠性、强大分析和易于集成备受青睐;Mailgun以灵活性和高发送率著称;而AOKSend则以其高效、详细分析和易用性脱颖而出。通过使用这些API,企业能实现定制化邮件服务,跟踪性能,提升邮件营销效果。
|
8月前
|
存储 算法 索引
【狂热算法篇】探秘差分数组:算法星河中闪耀的区间掌控之星
【狂热算法篇】探秘差分数组:算法星河中闪耀的区间掌控之星
|
存储 算法 Java
【算法练习】有趣的括号匹配问题(思路+ 图解 +优化)基于java实现
1.题目描述 小洛看着一堆只包含’(‘和’)‘的括号序列犯愁了,小洛想知道这串序列里最长正确匹配的序列长度是多少,你能帮帮小洛吗?
【算法练习】有趣的括号匹配问题(思路+ 图解 +优化)基于java实现
|
10月前
|
监控 数据可视化 测试技术
如何通过有效沟通提升项目管理效率?
本文分享了一位产品经理关于项目管理的实战经验,涵盖从启动到收尾的全流程,强调了明确目标、风险管理、沟通协调的重要性,并提供了实用的方法和教训,帮助新手产品经理避免常见错误,提升项目成功率。文章还介绍了如何利用工具提高管理效率。
|
安全 网络虚拟化 数据安全/隐私保护
Windows 10系统自带VPN客户端配置连接PPTP VPN服务器
Windows 10系统自带VPN客户端配置连接PPTP VPN服务器
6197 1
|
机器学习/深度学习 数据采集 数据可视化
SAS逻辑回归logistic在对鲍鱼年龄识别中的应用可视化
SAS逻辑回归logistic在对鲍鱼年龄识别中的应用可视化
|
存储 编译器 C++
【C++】多态的实现及其底层原理
【C++】多态的实现及其底层原理
|
消息中间件 存储 缓存
【PCIe页请求服务】到底到底到底是啥?半年搜遍全网找不到一篇介绍文章,没人写那我来写吧
【PCIe页请求服务】到底到底到底是啥?半年搜遍全网找不到一篇介绍文章,没人写那我来写吧
1835 0
【PCIe页请求服务】到底到底到底是啥?半年搜遍全网找不到一篇介绍文章,没人写那我来写吧
|
机器学习/深度学习 人工智能 PyTorch
CVPR2022 oral | MetaFormer才是探索Transformer的源泉,衍生PoolFormer速度喜人(二)
CVPR2022 oral | MetaFormer才是探索Transformer的源泉,衍生PoolFormer速度喜人(二)
200 0