骨骼店面面经顺便问一下约昂赛

啊lch 发表于 2017-12-7 01:23
我觉得不行吧，你这样没有考虑对角线的情况，比如说：
0 1 0 1
1 0 1 0

对角线的情况叫“菱形”吧。。

penggeqiang 发表于 2017-12-7 01:29
对角线的情况叫“菱形”吧。。

不是啊，有时候是菱形有时候是矩形，像我举的例子就是个正方形

啊lch 发表于 2017-12-7 01:45
不是啊，有时候是菱形有时候是矩形，像我举的例子就是个正方形

对，我想错了。

啊lch 发表于 2017-12-7 01:23
我觉得不行吧，你这样没有考虑对角线的情况，比如说：
0 1 0 1
1 0 1 0

同意，没想到这个case。如果考虑对角线的话，是不是需要单独考虑了，通过比较列坐标的方法就不适用于菱形。

啊lch 发表于 2017-12-7 01:23
我觉得不行吧，你这样没有考虑对角线的情况，比如说：
0 1 0 1
1 0 1 0

感觉这道题general是不是不需要考虑这种情况吧

马克一下 谢谢楼主！

siy 发表于 2017-12-6 05:18
对每一行，得到每一对1的列坐标pair，存到set里，遍历行如果有重复就true， complexity是n * m * m。应该 ...

谢谢楼主分享
这么解的话就是说这道题不用考虑组成斜的矩形的情形了吧？

大家看这个思路行不行。
把每行看成二进制数字，所以首先把矩阵转成n个数字的数组，然后每两个数做“与”操作，结果里面有2个1，就说明可以组成矩形。
如果行数多于列数，我们可以改成把每列转成数字，所以总时间复杂度应该是O(m * n)

得看长宽多少 要是超过32位 位数组内部也只能每32个每32个与一下

LUOLUOLNSH 发表于 2017-12-6 22:58
多谢lz分享 ~~ 想问问如果用HashMap存的话 key 和value 都分别是什么泥？key 是行吗？

key是一个纵坐标，set里面放另一个纵坐标。因为是按行遍历，不需要考虑横坐标的。如果你是按列遍历就反过来就行