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 的情況。通過三個主要步驟來解決這個問題：

1. 讀取輸入并初始化矩陣：讀取一個 n x n 的矩陣，并構建前綴和矩陣 m 和 sum。
2. 計算前綴和：通過構建前綴和矩陣，可以快速計算任何子矩陣的元素和。
3. 檢查子矩陣：對于每個可能的子矩陣，檢查其是否滿足條件。

什么是前綴和矩陣

前綴和矩陣是一種用于快速計算二維數組（矩陣）中子矩陣元素之和的數據結構。通過預先計算和存儲每個位置的前綴和，我們可以在常數時間內計算任意子矩陣的元素和。

前綴和矩陣的構建

給定一個大小為 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，因為這些位置不可能有左上方的矩陣。

解決方案

我們將通過以下步驟來解決這個問題：

1. 讀取輸入并初始化矩陣：我們將讀取輸入的矩陣，并使用兩個矩陣 nums 和 m 來存儲矩陣元素和前綴和。
2. 計算前綴和：前綴和矩陣 m 可以幫助我們快速計算任何子矩陣的元素和。前綴和矩陣的計算公式為： m[i][j]=m[i?1][j]+m[i][j?1]?m[i?1][j?1]+nums[i][j]
3. 檢查子矩陣：對于每個可能的子矩陣，我們通過前綴和矩陣快速計算其元素和，并檢查其是否滿足條件。

代碼實現

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);}}
}

代碼解析

1. 初始化矩陣和前綴和矩陣：
   • nums 用于存儲輸入的二進制矩陣。
   • m 用于存儲前綴和矩陣，通過累加計算得到。
2. 計算前綴和：
   • 前綴和矩陣 m[i][j] 通過公式 m[i][j] = m[i-1][j] + m[i][j-1] - m[i-1][j-1] + nums[i][j] 計算得到。
   • 這樣可以在常數時間內計算任何子矩陣的元素和。
3. 遍歷子矩陣：
   • 對于每個可能的子矩陣，計算其元素和 sum。
   • 檢查該和是否等于 k*k/2，如果是，則計數器 ans 增加。

總結

任何子矩陣的元素和。
3. 遍歷子矩陣：

• 對于每個可能的子矩陣，計算其元素和 sum。
• 檢查該和是否等于 k*k/2，如果是，則計數器 ans 增加。

總結

通過使用前綴和矩陣，可以高效地計算出所有邊長為 k 的子矩陣中包含特定數量 1 的情況。這種方法大大減少了時間復雜度，能夠在合理的時間內解決較大的輸入規模。