怎么看别人网站怎么做的优化,wordpress稳定吗,网站集约化平台建设分析,劳务公司起名字大全免费100道面试必会算法-27-美团2024面试第一题-前缀和矩阵 问题解读
给定一个 n x n 的二进制矩阵#xff0c;每个元素是 0 或 1。我们的任务是计算矩阵中所有边长为 k 的子矩阵中#xff0c;包含特定数量 1 的情况。例如#xff0c;我们希望找到所有边长为 k 的子矩阵中包含 k…100道面试必会算法-27-美团2024面试第一题-前缀和矩阵 问题解读
给定一个 n x n 的二进制矩阵每个元素是 0 或 1。我们的任务是计算矩阵中所有边长为 k 的子矩阵中包含特定数量 1 的情况。例如我们希望找到所有边长为 k 的子矩阵中包含 k*k/2 个 1 的子矩阵数量。
输入格式 第一行一个整数 n表示矩阵的大小。
接下来的 n 行每行包含一个长度为 n 的二进制字符串表示矩阵中的一行。输出格式 对于每个可能的子矩阵边长 k输出一个整数表示边长为 k 且包含特定数量 1 的子矩阵的数量。如果 k 是奇数计算一个大小为 n x n 的矩阵中所有边长为 k 的子矩阵中包含特定数量的 1 的情况。通过三个主要步骤来解决这个问题
读取输入并初始化矩阵读取一个 n x n 的矩阵并构建前缀和矩阵 m 和 sum。计算前缀和通过构建前缀和矩阵可以快速计算任何子矩阵的元素和。检查子矩阵对于每个可能的子矩阵检查其是否满足条件。
什么是前缀和矩阵
前缀和矩阵是一种用于快速计算二维数组矩阵中子矩阵元素之和的数据结构。通过预先计算和存储每个位置的前缀和我们可以在常数时间内计算任意子矩阵的元素和。
前缀和矩阵的构建
给定一个大小为 n x n 的矩阵 nums我们可以构建一个前缀和矩阵 m。前缀和矩阵的每个元素 m[i][j] 表示从矩阵的左上角 (1,1) 到位置 (i,j) 的所有元素的和。其递推公式为
m[i][j]m[i−1][j]m[i][j−1]−m[i−1][j−1]nums[i][j]
在边界条件下
m[i][0] 和 m[0][j] 初始为 0因为这些位置不可能有左上方的矩阵。
解决方案
我们将通过以下步骤来解决这个问题
读取输入并初始化矩阵我们将读取输入的矩阵并使用两个矩阵 nums 和 m 来存储矩阵元素和前缀和。计算前缀和前缀和矩阵 m 可以帮助我们快速计算任何子矩阵的元素和。前缀和矩阵的计算公式为 m[i][j]m[i−1][j]m[i][j−1]−m[i−1][j−1]nums[i][j]检查子矩阵对于每个可能的子矩阵我们通过前缀和矩阵快速计算其元素和并检查其是否满足条件。
代码实现
import java.util.Scanner;public class Meituan {public static void main(String[] args) {Scanner input new Scanner(System.in);int n input.nextInt();char[] chars;int[][] m new int[n 1][n 1];int[][] nums new int[n 1][n 1];// 初始化矩阵和前缀和矩阵for (int i 1; i n; i) {chars input.next().toCharArray();for (int j 1; j n; j) {nums[i][j] chars[j - 1] - 0;m[i][j] m[i - 1][j] m[i][j - 1] - m[i - 1][j - 1] nums[i][j];}}// 遍历每个可能的子矩阵边长 kfor (int k 1; k n; k) {if (k % 2 ! 0) {System.out.println(0);continue;}int ans 0;// 遍历每个可能的子矩阵for (int i 1; i k - 1 n; i) {for (int j 1; j k - 1 n; j) {int x i k - 1;int y j k - 1;int sum m[x][y] - m[i - 1][y] - m[x][j - 1] m[i - 1][j - 1];if (sum k * k / 2) ans;}}System.out.println(ans);}}
}
代码解析
初始化矩阵和前缀和矩阵 nums 用于存储输入的二进制矩阵。m 用于存储前缀和矩阵通过累加计算得到。 计算前缀和 前缀和矩阵 m[i][j] 通过公式 m[i][j] m[i-1][j] m[i][j-1] - m[i-1][j-1] nums[i][j] 计算得到。这样可以在常数时间内计算任何子矩阵的元素和。 遍历子矩阵 对于每个可能的子矩阵计算其元素和 sum。检查该和是否等于 k*k/2如果是则计数器 ans 增加。
总结
任何子矩阵的元素和。 3. 遍历子矩阵
对于每个可能的子矩阵计算其元素和 sum。检查该和是否等于 k*k/2如果是则计数器 ans 增加。
总结
通过使用前缀和矩阵可以高效地计算出所有边长为 k 的子矩阵中包含特定数量 1 的情况。这种方法大大减少了时间复杂度能够在合理的时间内解决较大的输入规模。
