i******n
发帖数: 12 | 1 上来就做题，挂在第二题上了
1. 无序数组求逆序对的数量
逆序对就是A > A[j] 且 i
-- merge sort归并的时候统计，nlogn 这个还好。。
2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
任意角度去覆盖。
那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
--算法没想出来没想出来没想出来。。。
后来想想，是不是看与1相邻的0的数目是奇数还是偶数啊？但是三角形奇数不会证。。
。求解答 |
l*********8
发帖数: 4642 | 2 第二题。 是个简化的图像识别。先求出物体边缘(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******n
发帖数: 12 | 3
噗。。这一点通还真不难。。思维定势+弱爆了 要加把劲才行。。
【在 l*********8 的大作中提到】
: 第二题。 是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
: cells分到三或者四条直线里。 如果求得三条直线，则是三角形。四条直线是正方形。
|
i******n
发帖数: 12 | 4
有个问题。。。边缘具体是指什么呀？
比如，你对4个连续的水平方格，沿对角线作出正方形的一条边，然后其余三条边依次
得出，他们都是连续4个水平或者竖直的方格的对角线，那这样的话，边缘的0应该不是
4条线。
如果是边缘的1的话，好像也不行，比如上面的情况，正方形的边变成5个连续方格的对
角线的话，也不是4条线。
不过。。要是把边缘的1全部去掉的话，剩下的1方格阵的边缘貌似是4条线。。不知道
对不对。。
【在 l*********8 的大作中提到】
: 第二题。 是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
: cells分到三或者四条直线里。 如果求得三条直线，则是三角形。四条直线是正方形。
|
s******n
发帖数: 226 | 5 边界不规则 不好找那条直线
三角形和正方形在x/y轴投影不一样， 用各自的最大最小值判断。 |
f***b
发帖数: 21 | |
p**t
发帖数: 157 | 7 不是正三角形
投影可以是一样的吧？
边界其实不需要确定直线数值
知道是一条线就足够了 比如前i行的1起始位置是递减的
到第i+1行突然变成递增了 这显然就是第二条边开始了
或者到第i+1行突然没了 也是一个意思
当然某些特殊钝角三角形会导致你少数出几条边
但是正方形是一定能数出4条边的
【在 s******n 的大作中提到】
: 边界不规则 不好找那条直线
: 三角形和正方形在x/y轴投影不一样， 用各自的最大最小值判断。
|
b****h
发帖数: 163 | 8 第二题三角形是正三角形吗？
如果不是，很多情况下 三角形和正方形 覆盖出的1可能完全一样 |
b****h
发帖数: 163 | 9 正方形 小的话 也可能只数出来一条边
正三角形也可能投影一样，比如投影是2个连续的小方块
这道题明显是个实际问题，要方块小，三角形或正方形大的时候才能解
【在 p**t 的大作中提到】
: 不是正三角形
: 投影可以是一样的吧？
: 边界其实不需要确定直线数值
: 知道是一条线就足够了 比如前i行的1起始位置是递减的
: 到第i+1行突然变成递增了 这显然就是第二条边开始了
: 或者到第i+1行突然没了 也是一个意思
: 当然某些特殊钝角三角形会导致你少数出几条边
: 但是正方形是一定能数出4条边的
|
p**t
发帖数: 157 | 10 只要够大 应该不会吧。。
【在 b****h 的大作中提到】
: 第二题三角形是正三角形吗？
: 如果不是，很多情况下 三角形和正方形 覆盖出的1可能完全一样
|
|
|
H*******n
发帖数: 4 | 11 我有一个想法：
不考虑有图形的边平行于矩阵的边的情况：
先找值为1的最上，最下，最左，最右格子的坐标。
如果四个格子坐标各不相同，则为正方形。
如果有相同的，则为三角形。
不知道对不对
【在 i******n 的大作中提到】
: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。
|
p**t
发帖数: 157 | 12 边长小于某个阈值的话确实存在无法区分的情况
本来嘛 你像素值太低的时候三角形和正方形显示出来确实就是一样的
在这种极端情况下任何一个算法都没办法区分出到底是三角形还是正方形
因为本来就都可以。。。
所以我觉得这个题应该能想到图像识别就ok了
【在 b****h 的大作中提到】
: 正方形 小的话 也可能只数出来一条边
: 正三角形也可能投影一样，比如投影是2个连续的小方块
: 这道题明显是个实际问题，要方块小，三角形或正方形大的时候才能解
|
i******n
发帖数: 12 | 13 假设矩阵中的1不少 至少有10个吧，然后是任意的三角形~~~ 任意位置 任意旋转~ |
p**t
发帖数: 157 | 14 尖角未必是一个独立的格子
也有可能是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*******n
发帖数: 4 | 15 我修改了一下。
对这种图形有边平行于矩阵边的还没想好。初步想法是这样：
对最上，记录最上的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****a
发帖数: 447 | 16 2. 三角形是普通的？
尖角覆盖不一定都是1，很可1的边界也是正方形？
【在 i******n 的大作中提到】
: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。
|
l*****8
发帖数: 1083 | |
M****w
发帖数: 11 | 18 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**********3
发帖数: 3211 | |
s*w
发帖数: 729 | 20 原帖写得是不大清楚。简单说就是给你一个二值图像，你需要判断是黑背景上面盖了个
可能旋转了的白方格还是白三角形。
【在 j**********3 的大作中提到】
: 第二题啥意思？完全没明白
|
|
|
j**********3
发帖数: 3211 | 21 为啥我觉得这个题大家想多了，其实就找到顶点就可以了，如果顶点是4个，就是正方
形，3个就是三角形
【在 s*w 的大作中提到】
: 原帖写得是不大清楚。简单说就是给你一个二值图像，你需要判断是黑背景上面盖了个
: 可能旋转了的白方格还是白三角形。
|
w********s
发帖数: 1570 | 22 第二题, 霍夫变换, 或者harris corner detector
反正问你这个问题的人脑子被驴踢过,这种问题没学过计算机视觉算法的基本都回答不
出.
【在 i******n 的大作中提到】
: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。
|
j********o
发帖数: 435 | 23 第一题用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********i
发帖数: 74 | 24 第二题，4个格子的，
00
11
既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？ |
s********i
发帖数: 74 | 25 就是用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********o
发帖数: 435 | |
j**********3
发帖数: 3211 | 27 我觉得它少了什么条件
【在 s********i 的大作中提到】
: 第二题，4个格子的，
: 00
: 11
: 既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？
|
c******y
发帖数: 6 | |
p**t
发帖数: 157 | 29 当面积不够大的时候三角形和正方形是区分不出来的
所以可以合理假设吧
【在 s********i 的大作中提到】
: 第二题，4个格子的，
: 00
: 11
: 既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？
|
P****i
发帖数: 1362 | 30 3x3的边界一共有十几二十种模板，数一下，正方形的histogram和三角形的histogram
肯定有差别吧
1 0 0 0 0 1
1 1 1 0 1 1
1 1 1 1 1 1 |
|
|
c***r
发帖数: 280 | 31 我怎么也数出来四对呢？
请大牛指教 。
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***r
发帖数: 280 | 32 又想了一下，知道大概错在哪了，left[i] > right[j]的话，说明从 i至leftLen的数
都大于 right[j]了，这时increment的数该是 leftLen-i;
【在 c***r 的大作中提到】
: 我怎么也数出来四对呢？
: 请大牛指教 。
:
: 1
: element
|
n******n
发帖数: 12088 | 33 CLRS的习题。
【在 c***r 的大作中提到】
: 又想了一下，知道大概错在哪了，left[i] > right[j]的话，说明从 i至leftLen的数
: 都大于 right[j]了，这时increment的数该是 leftLen-i;
|
x*******6
发帖数: 262 | 34 我也觉得第二题是不是找顶点，1周围四个cell有三个是0或者区域外的就是顶点。 |
x****3
发帖数: 62 | 35 能否贴一下第一题用merge sort的代码。 谢谢 |
c***r
发帖数: 280 | 36 就是在合并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******n
发帖数: 12 | 37 上来就做题，挂在第二题上了
1. 无序数组求逆序对的数量
逆序对就是A > A[j] 且 i
-- merge sort归并的时候统计，nlogn 这个还好。。
2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
任意角度去覆盖。
那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
--算法没想出来没想出来没想出来。。。
后来想想，是不是看与1相邻的0的数目是奇数还是偶数啊？但是三角形奇数不会证。。
。求解答 |
l*********8
发帖数: 4642 | 38 第二题。 是个简化的图像识别。先求出物体边缘(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******n
发帖数: 12 | 39
噗。。这一点通还真不难。。思维定势+弱爆了 要加把劲才行。。
【在 l*********8 的大作中提到】
: 第二题。 是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
: cells分到三或者四条直线里。 如果求得三条直线，则是三角形。四条直线是正方形。
|
i******n
发帖数: 12 | 40
有个问题。。。边缘具体是指什么呀？
比如，你对4个连续的水平方格，沿对角线作出正方形的一条边，然后其余三条边依次
得出，他们都是连续4个水平或者竖直的方格的对角线，那这样的话，边缘的0应该不是
4条线。
如果是边缘的1的话，好像也不行，比如上面的情况，正方形的边变成5个连续方格的对
角线的话，也不是4条线。
不过。。要是把边缘的1全部去掉的话，剩下的1方格阵的边缘貌似是4条线。。不知道
对不对。。
【在 l*********8 的大作中提到】
: 第二题。 是个简化的图像识别。先求出物体边缘(0,1变化的cells），然后把这些
: cells分到三或者四条直线里。 如果求得三条直线，则是三角形。四条直线是正方形。
|
|
|
s******n
发帖数: 226 | 41 边界不规则 不好找那条直线
三角形和正方形在x/y轴投影不一样， 用各自的最大最小值判断。 |
f***b
发帖数: 21 | |
p**t
发帖数: 157 | 43 不是正三角形
投影可以是一样的吧？
边界其实不需要确定直线数值
知道是一条线就足够了 比如前i行的1起始位置是递减的
到第i+1行突然变成递增了 这显然就是第二条边开始了
或者到第i+1行突然没了 也是一个意思
当然某些特殊钝角三角形会导致你少数出几条边
但是正方形是一定能数出4条边的
【在 s******n 的大作中提到】
: 边界不规则 不好找那条直线
: 三角形和正方形在x/y轴投影不一样， 用各自的最大最小值判断。
|
b****h
发帖数: 163 | 44 第二题三角形是正三角形吗？
如果不是，很多情况下 三角形和正方形 覆盖出的1可能完全一样 |
b****h
发帖数: 163 | 45 正方形 小的话 也可能只数出来一条边
正三角形也可能投影一样，比如投影是2个连续的小方块
这道题明显是个实际问题，要方块小，三角形或正方形大的时候才能解
【在 p**t 的大作中提到】
: 不是正三角形
: 投影可以是一样的吧？
: 边界其实不需要确定直线数值
: 知道是一条线就足够了 比如前i行的1起始位置是递减的
: 到第i+1行突然变成递增了 这显然就是第二条边开始了
: 或者到第i+1行突然没了 也是一个意思
: 当然某些特殊钝角三角形会导致你少数出几条边
: 但是正方形是一定能数出4条边的
|
p**t
发帖数: 157 | 46 只要够大 应该不会吧。。
【在 b****h 的大作中提到】
: 第二题三角形是正三角形吗？
: 如果不是，很多情况下 三角形和正方形 覆盖出的1可能完全一样
|
H*******n
发帖数: 4 | 47 我有一个想法：
不考虑有图形的边平行于矩阵的边的情况：
先找值为1的最上，最下，最左，最右格子的坐标。
如果四个格子坐标各不相同，则为正方形。
如果有相同的，则为三角形。
不知道对不对
【在 i******n 的大作中提到】
: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。
|
p**t
发帖数: 157 | 48 边长小于某个阈值的话确实存在无法区分的情况
本来嘛 你像素值太低的时候三角形和正方形显示出来确实就是一样的
在这种极端情况下任何一个算法都没办法区分出到底是三角形还是正方形
因为本来就都可以。。。
所以我觉得这个题应该能想到图像识别就ok了
【在 b****h 的大作中提到】
: 正方形 小的话 也可能只数出来一条边
: 正三角形也可能投影一样，比如投影是2个连续的小方块
: 这道题明显是个实际问题，要方块小，三角形或正方形大的时候才能解
|
i******n
发帖数: 12 | 49 假设矩阵中的1不少 至少有10个吧，然后是任意的三角形~~~ 任意位置 任意旋转~ |
p**t
发帖数: 157 | 50 尖角未必是一个独立的格子
也有可能是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*******n
发帖数: 4 | 51 我修改了一下。
对这种图形有边平行于矩阵边的还没想好。初步想法是这样：
对最上，记录最上的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****a
发帖数: 447 | 52 2. 三角形是普通的？
尖角覆盖不一定都是1，很可1的边界也是正方形？
【在 i******n 的大作中提到】
: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。
|
l*****8
发帖数: 1083 | |
M****w
发帖数: 11 | 54 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**********3
发帖数: 3211 | |
s*w
发帖数: 729 | 56 原帖写得是不大清楚。简单说就是给你一个二值图像，你需要判断是黑背景上面盖了个
可能旋转了的白方格还是白三角形。
【在 j**********3 的大作中提到】
: 第二题啥意思？完全没明白
|
j**********3
发帖数: 3211 | 57 为啥我觉得这个题大家想多了，其实就找到顶点就可以了，如果顶点是4个，就是正方
形，3个就是三角形
【在 s*w 的大作中提到】
: 原帖写得是不大清楚。简单说就是给你一个二值图像，你需要判断是黑背景上面盖了个
: 可能旋转了的白方格还是白三角形。
|
w********s
发帖数: 1570 | 58 第二题, 霍夫变换, 或者harris corner detector
反正问你这个问题的人脑子被驴踢过,这种问题没学过计算机视觉算法的基本都回答不
出.
【在 i******n 的大作中提到】
: 上来就做题，挂在第二题上了
: 1. 无序数组求逆序对的数量
: 逆序对就是A > A[j] 且 i: -- merge sort归并的时候统计，nlogn 这个还好。。
: 2. 给一个0和1的矩阵，先全部为0，然后，用一个正方形或者三角形去覆盖这个矩阵，
: 若覆盖到的方格面积大于等于1/2，则标1。正方形和三角形的各个顶点都不会超过矩阵
: 边界。可以假设不存在只有一个格子为1的情况。正方形或者三角形可以在任意位置以
: 任意角度去覆盖。
: 那么，给你一个0,1矩阵，判断覆盖该矩阵的是正方形还是三角形。
: --算法没想出来没想出来没想出来。。。
|
j********o
发帖数: 435 | 59 第一题用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********i
发帖数: 74 | 60 第二题，4个格子的，
00
11
既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？ |
|
|
s********i
发帖数: 74 | 61 就是用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********o
发帖数: 435 | |
j**********3
发帖数: 3211 | 63 我觉得它少了什么条件
【在 s********i 的大作中提到】
: 第二题，4个格子的，
: 00
: 11
: 既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？
|
c******y
发帖数: 6 | |
p**t
发帖数: 157 | 65 当面积不够大的时候三角形和正方形是区分不出来的
所以可以合理假设吧
【在 s********i 的大作中提到】
: 第二题，4个格子的，
: 00
: 11
: 既可以是三角形覆盖，又可以是正方形覆盖，没法解啊，题目错了还是不全？
|
P****i
发帖数: 1362 | 66 3x3的边界一共有十几二十种模板，数一下，正方形的histogram和三角形的histogram
肯定有差别吧
1 0 0 0 0 1
1 1 1 0 1 1
1 1 1 1 1 1 |
c***r
发帖数: 280 | 67 我怎么也数出来四对呢？
请大牛指教 。
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***r
发帖数: 280 | 68 又想了一下，知道大概错在哪了，left[i] > right[j]的话，说明从 i至leftLen的数
都大于 right[j]了，这时increment的数该是 leftLen-i;
【在 c***r 的大作中提到】
: 我怎么也数出来四对呢？
: 请大牛指教 。
:
: 1
: element
|
n******n
发帖数: 12088 | 69 CLRS的习题。
【在 c***r 的大作中提到】
: 又想了一下，知道大概错在哪了，left[i] > right[j]的话，说明从 i至leftLen的数
: 都大于 right[j]了，这时increment的数该是 leftLen-i;
|
x*******6
发帖数: 262 | 70 我也觉得第二题是不是找顶点，1周围四个cell有三个是0或者区域外的就是顶点。 |
|
|
c***r
发帖数: 280 | 71 就是在合并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*****g
发帖数: 254 | 72 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. |
