Java教程

两道前缀和算法

本文主要是介绍两道前缀和算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:二维区域和检索

解法:

class NumMatrix {
    int[][] sum;
    public NumMatrix(int[][] matrix) {
        int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
        // 与「一维前缀和」一样,前缀和数组下标从 1 开始,因此设定矩阵形状为 [n + 1][m + 1](模板部分)
        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] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int x1, int y1, int x2, int y2) {
        // 求某一段区域和 [i, j] 的模板是 sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];(模板部分)
        // 但由于我们源数组下标从 0 开始,因此要在模板的基础上进行 + 1
        x1++; y1++; x2++; y2++;
        return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
    }
}


题目:矩形区域不超过 K 的最大数值和

解法:

这个很明显也是一个前缀和的问题,关键在于寻找满足题意的区域,正常来讲需要枚举上,下,左,右四个边界,就有4层循环,时间复杂度太高

我们之前在求两数和是,除了双层循环枚举外,还可以枚举其中一个数,另一个数用hashmap寻找(比如a+b=c则=b-a)该题同理,我们可以枚举上下右边界,同时使用有序集合存储访问过的右边界作为可选择的左边界

class Solution {
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;

        // 预处理前缀和
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        int ans = Integer.MIN_VALUE;
        // 遍历子矩阵的上边界
        for (int top = 1; top <= m; top++) {
            // 遍历子矩阵的下边界
            for (int bot = top; bot <= m; bot++) {
                // 使用「有序集合」维护所有遍历到的右边界
                TreeSet<Integer> ts = new TreeSet<>();
                ts.add(0);
                // 遍历子矩阵的右边界
                for (int r = 1; r <= n; r++) {
                    // 通过前缀和计算 right
                    int right = sum[bot][r] - sum[top - 1][r];
                    // 通过二分找 left
                    Integer left = ts.ceiling(right - k);
                    if (left != null) {
                        int cur = right - left;
                        ans = Math.max(ans, cur);
                    }
                    // 将遍历过的 right 加到有序集合
                    ts.add(right);
                }
            }
        }
        return ans;
    }
}

这篇关于两道前缀和算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!