【卖萌奔请教】搬完家，狗狗不肯在新家门口大便，怎么办 - 未名空间MITBBS历史存档

【卖萌奔请教】搬完家，狗狗不肯在新家门口大便，怎么办# pets - 心有所宠

i*n2013-12-23 08:12

1 楼

上来就做题，挂在第二题上了
1. 无序数组求逆序对的数量
逆序对就是A > A[j] 且 i-- merge sort归并的时候统计，nlogn 这个还好。。
2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
任意角度去覆盖。
那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
--算法没想出来没想出来没想出来。。。
后来想想，是不是看与1相邻的0的数目是奇数还是偶数啊？但是三角形奇数不会证。。
。求解答

c*s2013-12-23 08:12

2 楼

过去住公寓，每天早晚带狗狗到外面公共草坪大小便，到了地方，它闻闻就蹲下来开始
便便，已经养成习惯了。
刚刚搬了新家，门口有一片小草坪，但是没fence，小七是shiba inu，不敢off leash
。可能因为这片草坪从来没有狗狗便便过，他总是闻半天，最后就忘记自己要便便。然
后就开始自己玩起来。试了几次，他都不肯在家门口便便。
无奈，我只好带它走走，结果连着两次都是，刚走到邻居家门口，他就走到邻居家草上
，闻了没几秒钟，瞬间蹲下开始粑粑。。。晕死。。。我只好走到别人家草上去收拾，
还好最近邻居过节出门了，没人在家。
过去捡粑粑的时候，发现邻居家草坪上好多狗狗便便，估计是他们家狗狗的吧。
猜可能是，小七觉得我家草没有便便，是干净的所以不能在上面拉粑粑，邻居家草是脏
的，可以过去拉？
我也总不能每次都让我家狗到别人家草上大便呀。。。怎么办。。。

l*82013-12-23 08:12

3 楼

第二题。是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
cells分到三或者四条直线里。如果求得三条直线，则是三角形。四条直线是正方形。

【在 i******n 的大作中提到】

: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。

c*y2013-12-23 08:12

4 楼

leash
把小七的粑粑拿回去你家的小草坪不就有味道了

【在 c*****s 的大作中提到】

: 过去住公寓，每天早晚带狗狗到外面公共草坪大小便，到了地方，它闻闻就蹲下来开始
: 便便，已经养成习惯了。
: 刚刚搬了新家，门口有一片小草坪，但是没fence，小七是shiba inu，不敢off leash
: 。可能因为这片草坪从来没有狗狗便便过，他总是闻半天，最后就忘记自己要便便。然
: 后就开始自己玩起来。试了几次，他都不肯在家门口便便。
: 无奈，我只好带它走走，结果连着两次都是，刚走到邻居家门口，他就走到邻居家草上
: ，闻了没几秒钟，瞬间蹲下开始粑粑。。。晕死。。。我只好走到别人家草上去收拾，
: 还好最近邻居过节出门了，没人在家。
: 过去捡粑粑的时候，发现邻居家草坪上好多狗狗便便，估计是他们家狗狗的吧。
: 猜可能是，小七觉得我家草没有便便，是干净的所以不能在上面拉粑粑，邻居家草是脏

i*n2013-12-23 08:12

5 楼

噗。。这一点通还真不难。。思维定势+弱爆了要加把劲才行。。

【在 l*********8 的大作中提到】

: 第二题。是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
: cells分到三或者四条直线里。如果求得三条直线，则是三角形。四条直线是正方形。

M*o2013-12-23 08:12

6 楼

我也想说这个

【在 c*********y 的大作中提到】

:
: leash
: 把小七的粑粑拿回去你家的小草坪不就有味道了

i*n2013-12-23 08:12

7 楼

有个问题。。。边缘具体是指什么呀？
比如，你对4个连续的水平方格，沿对角线作出正方形的一条边，然后其余三条边依次
得出，他们都是连续4个水平或者竖直的方格的对角线，那这样的话，边缘的0应该不是
4条线。
如果是边缘的1的话，好像也不行，比如上面的情况，正方形的边变成5个连续方格的对
角线的话，也不是4条线。
不过。。要是把边缘的1全部去掉的话，剩下的1方格阵的边缘貌似是4条线。。不知道
对不对。。

【在 l*********8 的大作中提到】

: 第二题。是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
: cells分到三或者四条直线里。如果求得三条直线，则是三角形。四条直线是正方形。

b*r2013-12-23 08:12

8 楼

要不多给他点时间，多蹲一会。哈哈。你家MOCHI的跳蚤好了没

leash

【在 c*****s 的大作中提到】

: 过去住公寓，每天早晚带狗狗到外面公共草坪大小便，到了地方，它闻闻就蹲下来开始
: 便便，已经养成习惯了。
: 刚刚搬了新家，门口有一片小草坪，但是没fence，小七是shiba inu，不敢off leash
: 。可能因为这片草坪从来没有狗狗便便过，他总是闻半天，最后就忘记自己要便便。然
: 后就开始自己玩起来。试了几次，他都不肯在家门口便便。
: 无奈，我只好带它走走，结果连着两次都是，刚走到邻居家门口，他就走到邻居家草上
: ，闻了没几秒钟，瞬间蹲下开始粑粑。。。晕死。。。我只好走到别人家草上去收拾，
: 还好最近邻居过节出门了，没人在家。
: 过去捡粑粑的时候，发现邻居家草坪上好多狗狗便便，估计是他们家狗狗的吧。
: 猜可能是，小七觉得我家草没有便便，是干净的所以不能在上面拉粑粑，邻居家草是脏

s*n2013-12-23 08:12

9 楼

边界不规则不好找那条直线
三角形和正方形在x/y轴投影不一样，用各自的最大最小值判断。

c*n2013-12-23 08:12

10 楼

我们家的shiba，下雪之后不肯，就把她放回笼子里，半个小时后再带出来尝试，
不行再放会笼子里。如此反复后她就明白了

f*b2013-12-23 08:12

11 楼

第二题霍夫变换可以做么

c*s2013-12-23 08:12

12 楼

我感觉大致好了。在他身上没看到，每天他睡起来擦笼子的floor上面也没有flea soil
了。但是我打算过几天带他出门前，再全家喷一遍药。
真是最近多事之秋，一波未平一波又起。。。
我已经连着捡了3天的狗屎放回自己家门口了。。。一点作用都没有，它闻到自己的狗
屎就一副很嫌弃的样子绕开了，然后该怎么玩继续怎么玩。。。

【在 b*******r 的大作中提到】

: 要不多给他点时间，多蹲一会。哈哈。你家MOCHI的跳蚤好了没
:
: leash

p*t2013-12-23 08:12

13 楼

不是正三角形
投影可以是一样的吧？
边界其实不需要确定直线数值
知道是一条线就足够了比如前i行的1起始位置是递减的
到第i+1行突然变成递增了这显然就是第二条边开始了
或者到第i+1行突然没了也是一个意思
当然某些特殊钝角三角形会导致你少数出几条边
但是正方形是一定能数出4条边的

【在 s******n 的大作中提到】

: 边界不规则不好找那条直线
: 三角形和正方形在x/y轴投影不一样，用各自的最大最小值判断。

c*s2013-12-23 08:12

14 楼

谢谢~我今晚试试。。。

后再带出来尝试，

【在 c*******n 的大作中提到】

: 我们家的shiba，下雪之后不肯，就把她放回笼子里，半个小时后再带出来尝试，
: 不行再放会笼子里。如此反复后她就明白了

b*h2013-12-23 08:12

15 楼

第二题三角形是正三角形吗？
如果不是，很多情况下三角形和正方形覆盖出的1可能完全一样

n*u2013-12-23 08:12

16 楼

把别的狗狗的粑粑放你家草地上，他就会想用自己的cover

b*h2013-12-23 08:12

17 楼

正方形小的话也可能只数出来一条边
正三角形也可能投影一样，比如投影是2个连续的小方块
这道题明显是个实际问题，要方块小，三角形或正方形大的时候才能解

【在 p**t 的大作中提到】

: 不是正三角形
: 投影可以是一样的吧？
: 边界其实不需要确定直线数值
: 知道是一条线就足够了比如前i行的1起始位置是递减的
: 到第i+1行突然变成递增了这显然就是第二条边开始了
: 或者到第i+1行突然没了也是一个意思
: 当然某些特殊钝角三角形会导致你少数出几条边
: 但是正方形是一定能数出4条边的

c*s2013-12-23 08:12

18 楼

听起来很靠谱！！！！！！
我家门口到昨天为止以为遍地是它的粑粑了，但是没有一次不是从邻居家捡回来的。今
儿试试拣点邻居家的狗便便回来。。。希望他能顺利在自家门口大便。。。

【在 n******u 的大作中提到】

: 把别的狗狗的粑粑放你家草地上，他就会想用自己的cover

p*t2013-12-23 08:12

19 楼

只要够大应该不会吧。。

【在 b****h 的大作中提到】

: 第二题三角形是正三角形吗？
: 如果不是，很多情况下三角形和正方形覆盖出的1可能完全一样

H*n2013-12-23 08:12

20 楼

我有一个想法：
不考虑有图形的边平行于矩阵的边的情况：
先找值为1的最上，最下，最左，最右格子的坐标。
如果四个格子坐标各不相同，则为正方形。
如果有相同的，则为三角形。
不知道对不对

【在 i******n 的大作中提到】

: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。

p*t2013-12-23 08:12

21 楼

边长小于某个阈值的话确实存在无法区分的情况
本来嘛你像素值太低的时候三角形和正方形显示出来确实就是一样的
在这种极端情况下任何一个算法都没办法区分出到底是三角形还是正方形
因为本来就都可以。。。
所以我觉得这个题应该能想到图像识别就ok了

【在 b****h 的大作中提到】

: 正方形小的话也可能只数出来一条边
: 正三角形也可能投影一样，比如投影是2个连续的小方块
: 这道题明显是个实际问题，要方块小，三角形或正方形大的时候才能解

i*n2013-12-23 08:12

22 楼

假设矩阵中的1不少至少有10个吧，然后是任意的三角形~~~ 任意位置任意旋转~

p*t2013-12-23 08:12

23 楼

尖角未必是一个独立的格子
也有可能是2个甚至3个格子
这种情况下三角形最上最下最左最右是可以找到4个点的吧。。
比如
0 0 0 0 0
0 0 1 1 0
0 1 1 1 0
0 0 1 1 0
0 0 0 0 0
这种当然这个例子似乎也可以是正方形？

【在 H*******n 的大作中提到】

: 我有一个想法：
: 不考虑有图形的边平行于矩阵的边的情况：
: 先找值为1的最上，最下，最左，最右格子的坐标。
: 如果四个格子坐标各不相同，则为正方形。
: 如果有相同的，则为三角形。
: 不知道对不对

H*n2013-12-23 08:12

24 楼

我修改了一下。
对这种图形有边平行于矩阵边的还没想好。初步想法是这样：
对最上，记录最上的height,同时记录最上所有点的width的range.用你这个例子表示就
是最上是
height=4,width=(3,4)
这样记录四组边界条件再比较？

【在 p**t 的大作中提到】

: 尖角未必是一个独立的格子
: 也有可能是2个甚至3个格子
: 这种情况下三角形最上最下最左最右是可以找到4个点的吧。。
: 比如
: 0 0 0 0 0
: 0 0 1 1 0
: 0 1 1 1 0
: 0 0 1 1 0
: 0 0 0 0 0
: 这种当然这个例子似乎也可以是正方形？

p*a2013-12-23 08:12

25 楼

2. 三角形是普通的？
尖角覆盖不一定都是1，很可1的边界也是正方形？

【在 i******n 的大作中提到】

: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。

l*82013-12-23 08:12

26 楼

mark

M*w2013-12-23 08:12

27 楼

It is easy to calculate the area A and Perimeter P of the 1's.
for square (P/4)^2= P^2/16 = A
for triangle (P/3)^2*sqrt(3)/4= P^2/36*sqrt(3) >=A; when 3 sides are the
same, it leads to =.
using ratio of A/(P^2), it is easy to separate squares and triangles

【在 l*****8 的大作中提到】

: mark

j*32013-12-23 08:12

28 楼

第二题啥意思？完全没明白

s*w2013-12-23 08:12

29 楼

原帖写得是不大清楚。简单说就是给你一个二值图像，你需要判断是黑背景上面盖了个
可能旋转了的白方格还是白三角形。

【在 j**********3 的大作中提到】

: 第二题啥意思？完全没明白

j*32013-12-23 08:12

30 楼

为啥我觉得这个题大家想多了，其实就找到顶点就可以了，如果顶点是4个，就是正方
形，3个就是三角形

【在 s*w 的大作中提到】

: 原帖写得是不大清楚。简单说就是给你一个二值图像，你需要判断是黑背景上面盖了个
: 可能旋转了的白方格还是白三角形。

w*s2013-12-23 08:12

31 楼

第二题, 霍夫变换, 或者harris corner detector
反正问你这个问题的人脑子被驴踢过,这种问题没学过计算机视觉算法的基本都回答不
出.

【在 i******n 的大作中提到】

: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。

j*o2013-12-23 08:12

32 楼

第一题用merge sort对吗？
比如［4，3，2，1］
无序对应该有6对，｛［4，3］，［4，2］，［4，1］，［3，2］，［3，1］，［2，1
］｝
但是用merge sort的话，只能数出四对吧？
搜了一下，stack overflow上面用的是树，这个解法好像才是对的
tree = an empty balanced binary search tree
answer = 0
for each element in the array:
answer += number of the elements in the tree greater then this element
add this element to the tree

s*i2013-12-23 08:12

33 楼

第二题，4个格子的，
00
11
既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？

s*i2013-12-23 08:12

34 楼

就是用merge sort，只数出4对说明你数错了。

1
element

【在 j********o 的大作中提到】

: 第一题用merge sort对吗？
: 比如［4，3，2，1］
: 无序对应该有6对，｛［4，3］，［4，2］，［4，1］，［3，2］，［3，1］，［2，1
: ］｝
: 但是用merge sort的话，只能数出四对吧？
: 搜了一下，stack overflow上面用的是树，这个解法好像才是对的
: tree = an empty balanced binary search tree
: answer = 0
: for each element in the array:
: answer += number of the elements in the tree greater then this element

j*o2013-12-23 08:12

35 楼

想了一下，知道我哪里错了。谢谢。

j*32013-12-23 08:12

36 楼

我觉得它少了什么条件

【在 s********i 的大作中提到】

: 第二题，4个格子的，
: 00
: 11
: 既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？

c*y2013-12-23 08:12

37 楼

看上去很难啊

p*t2013-12-23 08:12

38 楼

当面积不够大的时候三角形和正方形是区分不出来的
所以可以合理假设吧

【在 s********i 的大作中提到】

: 第二题，4个格子的，
: 00
: 11
: 既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？

P*i2013-12-23 08:12

39 楼

3x3的边界一共有十几二十种模板，数一下，正方形的histogram和三角形的histogram
肯定有差别吧
1 0 0 0 0 1
1 1 1 0 1 1
1 1 1 1 1 1

c*r2013-12-23 08:12

40 楼

我怎么也数出来四对呢？
请大牛指教。

1
element

【在 j********o 的大作中提到】

: 第一题用merge sort对吗？
: 比如［4，3，2，1］
: 无序对应该有6对，｛［4，3］，［4，2］，［4，1］，［3，2］，［3，1］，［2，1
: ］｝
: 但是用merge sort的话，只能数出四对吧？
: 搜了一下，stack overflow上面用的是树，这个解法好像才是对的
: tree = an empty balanced binary search tree
: answer = 0
: for each element in the array:
: answer += number of the elements in the tree greater then this element

c*r2013-12-23 08:12

41 楼

又想了一下，知道大概错在哪了，left[i] > right[j]的话，说明从 i至leftLen的数
都大于 right[j]了，这时increment的数该是 leftLen-i;

【在 c***r 的大作中提到】

: 我怎么也数出来四对呢？
: 请大牛指教。
:
: 1
: element

n*n2013-12-23 08:12

42 楼

CLRS的习题。

【在 c***r 的大作中提到】

: 又想了一下，知道大概错在哪了，left[i] > right[j]的话，说明从 i至leftLen的数
: 都大于 right[j]了，这时increment的数该是 leftLen-i;

x*62013-12-23 08:12

43 楼

我也觉得第二题是不是找顶点，1周围四个cell有三个是0或者区域外的就是顶点。

x*32013-12-23 08:12

44 楼

能否贴一下第一题用merge sort的代码。谢谢

c*r2013-12-23 08:12

45 楼

就是在合并Left[] 和right[] array时候，当left[i] < right[j]的条件下，那个
count变量，要加上 left_length-i；因为从i开始到left array最后一个数，都会比j
大，所以从i开始，比j大的逆序pairs是 left_length-i个。

【在 x****3 的大作中提到】

: 能否贴一下第一题用merge sort的代码。谢谢

i*n2013-12-23 08:12

46 楼

上来就做题，挂在第二题上了
1. 无序数组求逆序对的数量
逆序对就是A > A[j] 且 i-- merge sort归并的时候统计，nlogn 这个还好。。
2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
任意角度去覆盖。
那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
--算法没想出来没想出来没想出来。。。
后来想想，是不是看与1相邻的0的数目是奇数还是偶数啊？但是三角形奇数不会证。。
。求解答

l*82013-12-23 08:12

47 楼

第二题。是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
cells分到三或者四条直线里。如果求得三条直线，则是三角形。四条直线是正方形。

【在 i******n 的大作中提到】

: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。

i*n2013-12-23 08:12

48 楼

噗。。这一点通还真不难。。思维定势+弱爆了要加把劲才行。。

【在 l*********8 的大作中提到】

: 第二题。是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
: cells分到三或者四条直线里。如果求得三条直线，则是三角形。四条直线是正方形。

i*n2013-12-23 08:12

49 楼

有个问题。。。边缘具体是指什么呀？
比如，你对4个连续的水平方格，沿对角线作出正方形的一条边，然后其余三条边依次
得出，他们都是连续4个水平或者竖直的方格的对角线，那这样的话，边缘的0应该不是
4条线。
如果是边缘的1的话，好像也不行，比如上面的情况，正方形的边变成5个连续方格的对
角线的话，也不是4条线。
不过。。要是把边缘的1全部去掉的话，剩下的1方格阵的边缘貌似是4条线。。不知道
对不对。。

【在 l*********8 的大作中提到】

: 第二题。是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
: cells分到三或者四条直线里。如果求得三条直线，则是三角形。四条直线是正方形。

s*n2013-12-23 08:12

50 楼

边界不规则不好找那条直线
三角形和正方形在x/y轴投影不一样，用各自的最大最小值判断。

f*b2013-12-23 08:12

51 楼

第二题霍夫变换可以做么

p*t2013-12-23 08:12

52 楼

不是正三角形
投影可以是一样的吧？
边界其实不需要确定直线数值
知道是一条线就足够了比如前i行的1起始位置是递减的
到第i+1行突然变成递增了这显然就是第二条边开始了
或者到第i+1行突然没了也是一个意思
当然某些特殊钝角三角形会导致你少数出几条边
但是正方形是一定能数出4条边的

【在 s******n 的大作中提到】

: 边界不规则不好找那条直线
: 三角形和正方形在x/y轴投影不一样，用各自的最大最小值判断。

b*h2013-12-23 08:12

53 楼

第二题三角形是正三角形吗？
如果不是，很多情况下三角形和正方形覆盖出的1可能完全一样

b*h2013-12-23 08:12

54 楼

正方形小的话也可能只数出来一条边
正三角形也可能投影一样，比如投影是2个连续的小方块
这道题明显是个实际问题，要方块小，三角形或正方形大的时候才能解

【在 p**t 的大作中提到】

: 不是正三角形
: 投影可以是一样的吧？
: 边界其实不需要确定直线数值
: 知道是一条线就足够了比如前i行的1起始位置是递减的
: 到第i+1行突然变成递增了这显然就是第二条边开始了
: 或者到第i+1行突然没了也是一个意思
: 当然某些特殊钝角三角形会导致你少数出几条边
: 但是正方形是一定能数出4条边的

p*t2013-12-23 08:12

55 楼

只要够大应该不会吧。。

【在 b****h 的大作中提到】

: 第二题三角形是正三角形吗？
: 如果不是，很多情况下三角形和正方形覆盖出的1可能完全一样

H*n2013-12-23 08:12

56 楼

我有一个想法：
不考虑有图形的边平行于矩阵的边的情况：
先找值为1的最上，最下，最左，最右格子的坐标。
如果四个格子坐标各不相同，则为正方形。
如果有相同的，则为三角形。
不知道对不对

【在 i******n 的大作中提到】

: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。

p*t2013-12-23 08:12

57 楼

边长小于某个阈值的话确实存在无法区分的情况
本来嘛你像素值太低的时候三角形和正方形显示出来确实就是一样的
在这种极端情况下任何一个算法都没办法区分出到底是三角形还是正方形
因为本来就都可以。。。
所以我觉得这个题应该能想到图像识别就ok了

【在 b****h 的大作中提到】

: 正方形小的话也可能只数出来一条边
: 正三角形也可能投影一样，比如投影是2个连续的小方块
: 这道题明显是个实际问题，要方块小，三角形或正方形大的时候才能解

i*n2013-12-23 08:12

58 楼

假设矩阵中的1不少至少有10个吧，然后是任意的三角形~~~ 任意位置任意旋转~

p*t2013-12-23 08:12

59 楼

尖角未必是一个独立的格子
也有可能是2个甚至3个格子
这种情况下三角形最上最下最左最右是可以找到4个点的吧。。
比如
0 0 0 0 0
0 0 1 1 0
0 1 1 1 0
0 0 1 1 0
0 0 0 0 0
这种当然这个例子似乎也可以是正方形？

【在 H*******n 的大作中提到】

: 我有一个想法：
: 不考虑有图形的边平行于矩阵的边的情况：
: 先找值为1的最上，最下，最左，最右格子的坐标。
: 如果四个格子坐标各不相同，则为正方形。
: 如果有相同的，则为三角形。
: 不知道对不对

H*n2013-12-23 08:12

60 楼

我修改了一下。
对这种图形有边平行于矩阵边的还没想好。初步想法是这样：
对最上，记录最上的height,同时记录最上所有点的width的range.用你这个例子表示就
是最上是
height=4,width=(3,4)
这样记录四组边界条件再比较？

【在 p**t 的大作中提到】

: 尖角未必是一个独立的格子
: 也有可能是2个甚至3个格子
: 这种情况下三角形最上最下最左最右是可以找到4个点的吧。。
: 比如
: 0 0 0 0 0
: 0 0 1 1 0
: 0 1 1 1 0
: 0 0 1 1 0
: 0 0 0 0 0
: 这种当然这个例子似乎也可以是正方形？

p*a2013-12-23 08:12

61 楼

2. 三角形是普通的？
尖角覆盖不一定都是1，很可1的边界也是正方形？

【在 i******n 的大作中提到】

: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。

l*82013-12-23 08:12

62 楼

mark

M*w2013-12-23 08:12

63 楼

It is easy to calculate the area A and Perimeter P of the 1's.
for square (P/4)^2= P^2/16 = A
for triangle (P/3)^2*sqrt(3)/4= P^2/36*sqrt(3) >=A; when 3 sides are the
same, it leads to =.
using ratio of A/(P^2), it is easy to separate squares and triangles

【在 l*****8 的大作中提到】

: mark

j*32013-12-23 08:12

64 楼

第二题啥意思？完全没明白

s*w2013-12-23 08:12

65 楼

原帖写得是不大清楚。简单说就是给你一个二值图像，你需要判断是黑背景上面盖了个
可能旋转了的白方格还是白三角形。

【在 j**********3 的大作中提到】

: 第二题啥意思？完全没明白

j*32013-12-23 08:12

66 楼

为啥我觉得这个题大家想多了，其实就找到顶点就可以了，如果顶点是4个，就是正方
形，3个就是三角形

【在 s*w 的大作中提到】

: 原帖写得是不大清楚。简单说就是给你一个二值图像，你需要判断是黑背景上面盖了个
: 可能旋转了的白方格还是白三角形。

w*s2013-12-23 08:12

67 楼

第二题, 霍夫变换, 或者harris corner detector
反正问你这个问题的人脑子被驴踢过,这种问题没学过计算机视觉算法的基本都回答不
出.

【在 i******n 的大作中提到】

: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。

j*o2013-12-23 08:12

68 楼

第一题用merge sort对吗？
比如［4，3，2，1］
无序对应该有6对，｛［4，3］，［4，2］，［4，1］，［3，2］，［3，1］，［2，1
］｝
但是用merge sort的话，只能数出四对吧？
搜了一下，stack overflow上面用的是树，这个解法好像才是对的
tree = an empty balanced binary search tree
answer = 0
for each element in the array:
answer += number of the elements in the tree greater then this element
add this element to the tree

s*i2013-12-23 08:12

69 楼

第二题，4个格子的，
00
11
既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？

s*i2013-12-23 08:12

70 楼

就是用merge sort，只数出4对说明你数错了。

1
element

【在 j********o 的大作中提到】

: 第一题用merge sort对吗？
: 比如［4，3，2，1］
: 无序对应该有6对，｛［4，3］，［4，2］，［4，1］，［3，2］，［3，1］，［2，1
: ］｝
: 但是用merge sort的话，只能数出四对吧？
: 搜了一下，stack overflow上面用的是树，这个解法好像才是对的
: tree = an empty balanced binary search tree
: answer = 0
: for each element in the array:
: answer += number of the elements in the tree greater then this element

j*o2013-12-23 08:12

71 楼

想了一下，知道我哪里错了。谢谢。

j*32013-12-23 08:12

72 楼

我觉得它少了什么条件

【在 s********i 的大作中提到】

: 第二题，4个格子的，
: 00
: 11
: 既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？

c*y2013-12-23 08:12

73 楼

看上去很难啊

p*t2013-12-23 08:12

74 楼

当面积不够大的时候三角形和正方形是区分不出来的
所以可以合理假设吧

【在 s********i 的大作中提到】

: 第二题，4个格子的，
: 00
: 11
: 既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？

P*i2013-12-23 08:12

75 楼

3x3的边界一共有十几二十种模板，数一下，正方形的histogram和三角形的histogram
肯定有差别吧
1 0 0 0 0 1
1 1 1 0 1 1
1 1 1 1 1 1

c*r2013-12-23 08:12

76 楼

我怎么也数出来四对呢？
请大牛指教。

1
element

【在 j********o 的大作中提到】

: 第一题用merge sort对吗？
: 比如［4，3，2，1］
: 无序对应该有6对，｛［4，3］，［4，2］，［4，1］，［3，2］，［3，1］，［2，1
: ］｝
: 但是用merge sort的话，只能数出四对吧？
: 搜了一下，stack overflow上面用的是树，这个解法好像才是对的
: tree = an empty balanced binary search tree
: answer = 0
: for each element in the array:
: answer += number of the elements in the tree greater then this element

c*r2013-12-23 08:12

77 楼

又想了一下，知道大概错在哪了，left[i] > right[j]的话，说明从 i至leftLen的数
都大于 right[j]了，这时increment的数该是 leftLen-i;

【在 c***r 的大作中提到】

: 我怎么也数出来四对呢？
: 请大牛指教。
:
: 1
: element

n*n2013-12-23 08:12

78 楼

CLRS的习题。

【在 c***r 的大作中提到】

: 又想了一下，知道大概错在哪了，left[i] > right[j]的话，说明从 i至leftLen的数
: 都大于 right[j]了，这时increment的数该是 leftLen-i;

x*62013-12-23 08:12

79 楼

我也觉得第二题是不是找顶点，1周围四个cell有三个是0或者区域外的就是顶点。

c*r2013-12-23 08:12

80 楼

就是在合并Left[] 和right[] array时候，当left[i] < right[j]的条件下，那个
count变量，要加上 left_length-i；因为从i开始到left array最后一个数，都会比j
大，所以从i开始，比j大的逆序pairs是 left_length-i个。

【在 x****3 的大作中提到】

: 能否贴一下第一题用merge sort的代码。谢谢

j*g2013-12-23 08:12

81 楼

where are the old members? All with big packages? :)
For Q2, clearly we need lots squares, see below example
It could be a square of [[11], [11]] which is shadowed by either a square or
a triangle.
Only when the shadowed area is large, we can use lines of corners to detect
the shape.