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 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【专业技术】STL hash_map使用(一)

今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。 hash_map类在头文件hash_map中,和所有其...

2998
来自专栏小樱的经验随笔

洛谷 P1019 单词接龙【经典DFS,温习搜索】

P1019 单词接龙 题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”...

3186
来自专栏机器学习从入门到成神

java之Vector使用(与ArrayList区分)

ArrayList会比Vector快,他是非同步的,如果设计涉及到多线程,还是用Vector比较好一些 import java.util.*;

391
来自专栏http://www.cnblogs.com

生成器&迭代器

一.生成器 在介绍生成器表达式之前,先看下列表表达式: 1 >>> l = [i for i in range(50) if i % 2] #生成...

33210
来自专栏听雨堂

深入理解字符串和字节数组转换

      前文中,论及字符串和字节数组的转换,虽然能够找到某个代码页,保证转换的可逆,但是在实际处理中,仍然还有一些细节问题需要注意.       最重要的...

1668
来自专栏社区的朋友们

sizeof 知多少? (上)

稍熟悉 C/C++ 的朋友,对于 sizeof 肯定不陌生,通过它我们可以知晓某个类型或者实例的内存大小( 以字节计 ),网上关于这个话题的信息其实挺多的,但是...

1140
来自专栏Golang语言社区

Go语言中反射的正确使用

介绍 反射是元数据编程的一种形式,指的是程序获得本身结构的一种能力。不同语言的反射模型实现不一样,本文中的反射,仅仅指的是Go语言中的反射模型。 反射有两个问题...

3426
来自专栏开发与安全

算法:静态查找表(Static Search Table)(顺序查找、二分查找、插值查找、斐波纳契查找)

查找表(Search table)是由同一类型的数据元素(或记录)构成的集合。关键字(key)是数据元素中某个数据项的值,又称为键值,用它可以表示一个数据元素,...

2035
来自专栏HTML5学堂

游戏开发 - Math对象相关知识讲解

前几期小编给大家总结了JavaScript的基础知识,为我们后期深入学习JS打下了一定的基础。在后面的几期文章当中我们要来进行JS小游戏的开发,但是开发小游戏的...

27410
来自专栏ACM算法日常

leetcode题解 | 78. 子集

这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

743

扫码关注云+社区