南宁网站建设制作后台,微信里的小程序怎么删除,王也道长高清头像 微信,网站首页做跳转文章目录1. 题目2. 解题1. 题目
给定一个只包含 0 和 1 的网格#xff0c;找出其中角矩形的数量。
一个「角矩形」是由四个不同的在网格上的 1 形成的轴对称的矩形。 注意只有4角的位置才需要为 1。并且#xff0c;4 个 1 需要是不同的。
示例 1#xff1a;
输入#xf…
文章目录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(vectorvectorint grid) {int m grid.size(), n grid[0].size(), r, c1, c2, count 0;vectorvectorint dp(n, vectorint(n, 0));for(r 0; r m; r){for(c1 0; c1 n; c1){if(grid[r][c1]){for(c2 c11; 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阿明一起加油、一起学习进步
