leetcode热题 - 2

子矩阵元素加 1问题描述给你一个正整数 n 表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat 矩阵中填满了 0 。另给你一个二维整数数组 query 。针对每个查询 query[i] [row1i, col1i, row2i, col2i] 请你执行下述操作找出 左上角 为 (row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i x row2i 和 col1i y col2i 的 mat[x][y] 加 1 。返回执行完所有操作后得到的矩阵 mat 。真题链接子矩阵元素加 1解题思路如果之前了解过二维数组差分的朋友们很容易就可以解决这个问题所以这里着重给没了解过的朋友们介绍一下。来自deepseek二维差分数组是一种通过O(1)时间记录子矩阵更新、再通过二维前缀和还原的技术。具体来说要对原矩阵中某个矩形区域统一加一个值只需在差分数组的四个角做标记起点加该值、右侧和下方的边界外减该值、右下角外再加回该值最后对差分数组求二维前缀和就能得到每个位置被累计更新的总量从而高效处理大量批量区域更新问题。简单来说就像差分数组一样我们只需要在一个二维数组的[0, 0]位置放上一个 1就可以实现整个二维数组的每一个位置都是1。下面笔者将以可视化的形式带读者更清晰的认识二维差分数组二维差分数组原理图示原矩阵: 1 2 4 3 5 3 2 1 1 4 2 5 差分矩阵初始化为0: 0 0 0 0 0 0 0 0 0 0 0 01. 单点更新以左上角(1,1)到右下角(2,2)矩形区域3为例差分矩阵操作点假设行列从1开始计数 (1,1) 3 (1,3) - 3 (3,1) - 3 (3,3) 3 更新后差分矩阵 3 0 -3 0 0 0 0 0 -3 0 3 02. 前缀和还原矩阵通过二维前缀和计算还原修改后的原矩阵第一行递推 1→4→1→1 原值1344(-3)1101 其他行列类似递推... 最终原矩阵 4 5 1 3 5 3 2 1 -2 1 5 5可视化辅助图操作区域示意图 (1,1)───────(1,2) │ 3 │ │ │ (2,1)───────(2,2) 差分矩阵影响点 ● (1,1) c ○ (1,3) -c ○ (3,1) -c ● (3,3) c代码实现参考一维差分a[i] diff[i] a[i-1]二维差分a[i][j] diff[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]有了上面关于二维差分数组的基本理解我们再来看题目就很容易了。我们只需要在每一个标记的点的位置将他 1并平衡数组等全部的位置标记完成后再进行二维差分数组的复原即可。代码实现classSolution{public:vectorvectorintrangeAddQueries(intn,vectorvectorintqueries){vectorvectorintret(n,vectorint(n,0));intx1,y1,x2,y2;for(inti0;iqueries.size();i){x1queries[i][0],y1queries[i][1],x2queries[i][2],y2queries[i][3];ret[x1][y1]1;if(x2n-1)ret[x21][y1]-1;if(y2n-1)ret[x1][y21]-1;if(x2n-1y2n-1)ret[x21][y21]1;}for(inti0;in;i){for(intj0;jn;j){if(i0)ret[i][j]ret[i-1][j];if(j0)ret[i][j]ret[i][j-1];if(i0j0)ret[i][j]-ret[i-1][j-1];}}returnret;}};复杂度分析项目复杂度时间复杂度O(N^2M)空间复杂度O(M)总结二维差分核心区间加操作 → O(1) 修改差分数组的 4 个角点最后求二维前缀和还原 → O(n²)关键细节差分数组直接复用在结果矩阵上无需额外空间边界判断x21 n防止越界还原公式a[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]使数组所有元素变成1的最少操作次数问题描述给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作任意次选择一个满足 0 i n - 1 的下标 i 将 nums[i] 或者 nums[i1] 两者之一替换成它们的最大公约数。请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 请你返回 -1 。两个正整数的最大公约数指的是能整除这两个数的最大正整数。真题链接使数组所有元素变成1的最少操作次数解题思路要解决这个问题我们可以换一种方法首先我们需要先判断一下是否可以实现把所有元素都变成 1即所有数的最大公约数是否为 1如果不可以不要犹豫直接返回 -1。因为这种情况下不可能将所有元素都变成 1。如果可以我们先寻找一个最小的len在这个区间内数组的最大公约数为 1所需要将这个区间中一个元素变成1这个操作的次数就为len - 1有一个 1 之后如果要将整个数组都变成1只需要再进行n-1次扩散即可。所有使整个数组变成1的操作次数就是nlen-2最小操作次数只需要我们找出这个最小的minlen即可。代码实现classSolution{public:intminOperations(vectorintnums){intnnums.size();intnum10,g0;for(intx:nums){if(x1)num1;ggcd(g,x);}if(num10)returnn-num1;if(g1)return-1;// 找到一个最小的可以区间可以使区间所有数组gcd 1intminlenn;for(inti0;in;i){intg0;for(intji;jn;j){ggcd(g,nums[j]);if(g1){minlenmin(minlen,j-i1);break;}}}returnminlenn-2;}};复杂度分析维度最优解时间复杂度 O(n^2 logN)双重循环 gcd 计算log M 为数值范围空间复杂度 O(1)无法再优化因为不需要额外存储总结三步走策略预判断统计已有的 1 的个数num1计算全局gcd若 1 则返回 -1不可能全变成 1特殊情况如果已有 1直接返回n - num1每个 1 可扩散一次一般情况寻找最短的gcd1的子数组长度为minlen需要minlen - 1次操作在该区间内造出一个 1再用n - 1次操作将这个 1 扩散到整个数组总操作数 minlen n - 2