LWC 63: 750. Number Of Corner Rectangles

LWC 63: 750. Number Of Corner Rectangles

传送门:750. Number Of Corner Rectangles

Problem:

Given a grid where each entry is only 0 or 1, find the number of corner rectangles. A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

Example 1:

Input: grid = [[1, 0, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0], [1, 0, 1, 0, 1]] Output: 1 Explanation: There is only one corner rectangle, with corners grid1[2], grid1[4], grid[3][2], grid[3][4].

Example 2:

Input: grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]] Output: 9 Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

Example 3:

Input: grid = [[1, 1, 1, 1]] Output: 0 Explanation: Rectangles must have four distinct corners.

Note:

The number of rows and columns of grid will each be in the range [1, 200].

Each grid[i][j] will be either 0 or 1.

The number of 1s in the grid will be at most 6000.

思路: 暴力搜索,实际上如果矩形的纵向边被确定了,只要有两条以上自然能构成矩形,所以只需要遍历不同的两行,找能够构成纵向边的个数,再组合一波即可。

Java版本:

    public int countCornerRectangles(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ret = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int np = 0;
                for (int k = 0; k < m; ++k) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        np ++;
                    }
                }
                ret += np * (np - 1) / 2;
            }
        }
        return ret;
    }

Python版本:

    def countCornerRectangles(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        m = len(grid[0])
        res = 0
        for i in xrange(n):
            for j in xrange(i + 1, n):
                np = 0
                for k in xrange(m):
                    if grid[i][k] and grid[j][k]:
                        np += 1

                res += np * (np - 1) / 2
        return res  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java架构师进阶

Java程序员实现完美代码的十大要素

对于方法的注释应该包含详细的入参和结果说明,有异常抛出的情况也要详细叙述;类的注释应该包含类的功能说明、作者和修改者。

822
来自专栏10km的专栏

fastjson:javabean按字段(field)序列化存储为Map并反序列化改进

需求说明 最近的项目应用到redis数据库,需要将java bean存储在redis数据库。因为需要对数据库中的某个字段进行修改,所以在redis上不能用简单的...

2008
来自专栏web前端

JavaScript基础学习--13字符串、查找高亮显示

Demos:   https://github.com/jiangheyan/JavaScriptBase 一、字符串      1、str.length; ...

2066
来自专栏deepcc

js数字格式化-四舍五入精简版

3696
来自专栏python3

python 入门知识拾遗

Python 3最重要的新特性大概要算是对文本和二进制数据作了更为清晰的区分。文本总是Unicode,由str类型表示,二进制数据则由bytes类型表示。Pyt...

894
来自专栏King_3的技术专栏

leetcode-17-电话号码的字母组合

vector<string> letterCombinations(string digits) 

813
来自专栏机器学习算法与Python学习

笔记 | 史上最全的正则表达式

原文:http://www.cnblogs.com/zxin/archive/2013/01/26/2877765.html 点击文末阅读原文即可 很多不太懂正...

31011
来自专栏进击的程序猿

Laravel之Pipeline1. 背景2. 基本操作3. 动手实现4. Laravel中Pipeline实现5. 总结

在Laravel中经常需要对一个对象,经过多个中间层处理后,才到真正处理的函数,Laravel将这种常用操作抽象出来,叫做Pipeline

732
来自专栏Hongten

让你一看就明白什么是聚合-java版本_源码下载

=================================================

1893
来自专栏华仔的技术笔记

iOS中的正则表达式,一篇就够了

37410

扫码关注云+社区