文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個只包含 0 和 1 的網格，找出其中角矩形的數量。

一個「角矩形」是由四個不同的在網格上的 1 形成的軸對稱的矩形。
注意只有4角的位置才需要為 1。并且，4 個 1 需要是不同的。

示例 1： 輸入：grid = [[1, 0, 0, 1, 0],[0, 0, 1, 0, 1],[0, 0, 0, 1, 0],[1, 0, 1, 0, 1]] 輸出：1 解釋：只有一個角矩形，角的位置為 grid[1][2], grid[1][4], grid[3][2], grid[3][4]。示例 2： 輸入：grid = [[1, 1, 1],[1, 1, 1],[1, 1, 1]] 輸出：9 解釋：這里有 4 個 2x2 的矩形，4 個 2x3 和 3x2 的矩形和 1 個 3x3 的矩形。示例 3： 輸入：grid = [[1, 1, 1, 1]] 輸出：0 解釋：矩形必須有 4 個不同的角。提示： 網格 grid 中行和列的數目范圍為 [1, 200]。 每個網格 grid[i][j] 中的值不是 0 就是 1 。 網格中 1 的個數不會超過 6000。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-corner-rectangles
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• dp[c1][c2] 表示兩列為 c1, c2 的時候，前綴n行的該兩列同時為1的次數

class Solution { public:int countCornerRectangles(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size(), r, c1, c2, count = 0;vector<vector<int>> dp(n, vector<int>(n, 0));for(r = 0; r < m; ++r){for(c1 = 0; c1 < n; ++c1){if(grid[r][c1]){for(c2 = c1+1; c2 < n; ++c2){if(grid[r][c2]){count += dp[c1][c2];dp[c1][c2]++;}}}}}return count;} };

184 ms 22.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 750. 角矩形的数量（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。