由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 再贴这道算法题,寻答案,有包子送
相关主题
CCup题目2.1是不是有更简单的O(n)的解给定整数数组和两个整数的和,求所有pair。
尘埃落定里面的矩形题g公司面试问Longest increasing subsequence,意义在哪里?
一道g家的几何题对于肯定会面挂的公司大家怎么回
一道有趣的算法题问题:判断一组线段是否相交
前几天那个关于正负数stable排序的问题的帖子找数组的最大质数
merge a1,a2,..b1,b2 to a1b1a2b2..F家题请教
问一道google面试题(from careercup)贴个简单的面经
发个A公司的面经google面试问题
相关话题的讨论汇总
话题: point话题: 算法话题: count话题: 蓝点话题: 红点
进入JobHunting版参与讨论
1 (共1页)
x*****p
发帖数: 1707
1
平面上有随机2000个点,其中1000蓝点,1000红点。但任何三点都不同线。
要求寻找一种最优化的算法,生成1000条互不相交的连接蓝点和红点的线段。换句话说
,让任何蓝点去连接任何红点,但各不相交。
g*********s
发帖数: 1782
2
一定存在解吗?

【在 x*****p 的大作中提到】
: 平面上有随机2000个点,其中1000蓝点,1000红点。但任何三点都不同线。
: 要求寻找一种最优化的算法,生成1000条互不相交的连接蓝点和红点的线段。换句话说
: ,让任何蓝点去连接任何红点,但各不相交。

x*****p
发帖数: 1707
3
是的,以前有一个回帖,提出一种算法,是肯定能找到解的,只是复杂度太高了。
f*******4
发帖数: 1401
4
那个vehicle pickup/deliver解法是什么样的?
二分图最大匹配好像跟这个没关系啊

【在 x*****p 的大作中提到】
: 是的,以前有一个回帖,提出一种算法,是肯定能找到解的,只是复杂度太高了。
g*********s
发帖数: 1782
5
我觉得这个不是简单的图论问题,而是计算几何的问题。这个两两不交的限制很强。

【在 f*******4 的大作中提到】
: 那个vehicle pickup/deliver解法是什么样的?
: 二分图最大匹配好像跟这个没关系啊

x*****p
发帖数: 1707
6
需要用到三点不共线这个非常强的条件。
g*********s
发帖数: 1782
7
三角化?

【在 x*****p 的大作中提到】
: 需要用到三点不共线这个非常强的条件。
x*****p
发帖数: 1707
8
缘起: 我有一个当教授的朋友,他偶然向我提到这个题目,说是和另一个美国教授聊天
的时候那个教授提出的,他也没解法。但数学上证明解的存在性是很容易的。因为我是
研究算法的,所以我这个朋友就来问我。我想了十几分钟也没思路就放弃了。一周后,
我的朋友打电话问我想的怎么样了,我本来是很羞愧的说不知道的,谁知当时灵光一闪
,想到一个复杂度为O(n^2)的算法可以解决这个问题。后来把算法整理写给我的朋友。
现在回想,恐怕有更好的O(nlnn)的算法,但不确定。这个版大牛多,上来问问,5个包
子答谢。
g***s
发帖数: 3811
9
抛砖引玉一下:
解法一:
这题可以看作是二分图的最大匹配的最小值路径匹配问题。用KM算法可以知道O(N*M)=O
(N^3).
解法二:
分治法。找到两点,把所有点分成两部分,每个部分都用相同多的红点和蓝点。然后对
两部分分治。
如何找到这样的两点(先给一个nlgn的算法)
1. 找x值最小的一个点A(如果有多个x值相同,取y值最小),把它作为其中一点。
2. 把A作为原点。其它所有点对于A(都减去Ax,Ay),都相当会落入第一和第四象限。
3. 把所有点求tan,排序。
4. 从小到大进行count,一直到找到这么一条边(A->B)。(易知一定存在这么一条边)
f(n) = max{ f(k) + f(n-k) + nlgn } k=1..n-1
f(n) = O(nlgn * n) = O(n^2 * lgn)
改进找B点的算法
3. 建立一最大堆,和一最小堆
4. 轮流从最大堆最小堆来进行查找,直到找到B
f(n) = max { f(k) + f(n-k) + (n + k*lgn)} k = 1..n/2
f(n) = O(n^2)
O(nlgn)感觉很难。
x*****p
发帖数: 1707
10
这个解法二是当时我的思路,只是上面第三步的排序,其实只需要一次排序即可,因为
以后递归的话,这个序是不会变的。
相关主题
merge a1,a2,..b1,b2 to a1b1a2b2..给定整数数组和两个整数的和,求所有pair。
问一道google面试题(from careercup)g公司面试问Longest increasing subsequence,意义在哪里?
发个A公司的面经对于肯定会面挂的公司大家怎么回
进入JobHunting版参与讨论
O*N
发帖数: 207
11
能解释一下为什么第四步一定能找到满足条件的B点?
如何保证分成的两部分中,红点和兰点的数量一定相等?

=O

【在 g***s 的大作中提到】
: 抛砖引玉一下:
: 解法一:
: 这题可以看作是二分图的最大匹配的最小值路径匹配问题。用KM算法可以知道O(N*M)=O
: (N^3).
: 解法二:
: 分治法。找到两点,把所有点分成两部分,每个部分都用相同多的红点和蓝点。然后对
: 两部分分治。
: 如何找到这样的两点(先给一个nlgn的算法)
: 1. 找x值最小的一个点A(如果有多个x值相同,取y值最小),把它作为其中一点。
: 2. 把A作为原点。其它所有点对于A(都减去Ax,Ay),都相当会落入第一和第四象限。

g***s
发帖数: 3811
12
assume the A is blue, it scan from bottom to up for all the rest N-1
point.
count=1
+1 for blue point
-1 for red point.
So, there are 499 times +1 and 500 times -1. count will reach 0 at some
point.
The point that makes count = 0 is the B. the worse case is the B is the
last one. then all N-2 points are in the one side and 0 point in the other
side.


【在 O*N 的大作中提到】
: 能解释一下为什么第四步一定能找到满足条件的B点?
: 如何保证分成的两部分中,红点和兰点的数量一定相等?
:
: =O

g***s
发帖数: 3811
13
因为他们是相对与A的tan值。当递归(分治)的时候,是一个新的A。他们的tan的序还
是回变的。

【在 x*****p 的大作中提到】
: 这个解法二是当时我的思路,只是上面第三步的排序,其实只需要一次排序即可,因为
: 以后递归的话,这个序是不会变的。

x*****p
发帖数: 1707
14
是的。但要注意的是,我们永远选择最左边的点作为新的原点。这样,所有点相当于一
个平移操作,虽然角度发生了变化,但序是不变的。这个可以做出数学证明。

【在 g***s 的大作中提到】
: 因为他们是相对与A的tan值。当递归(分治)的时候,是一个新的A。他们的tan的序还
: 是回变的。

g***s
发帖数: 3811
15
给个反例。

【在 x*****p 的大作中提到】
: 是的。但要注意的是,我们永远选择最左边的点作为新的原点。这样,所有点相当于一
: 个平移操作,虽然角度发生了变化,但序是不变的。这个可以做出数学证明。

x*****p
发帖数: 1707
16
Good example.
Then the algorithm can not be improved to O(nlnn)
1 (共1页)
进入JobHunting版参与讨论
相关主题
google面试问题前几天那个关于正负数stable排序的问题的帖子
直方图盛水最大容量问题merge a1,a2,..b1,b2 to a1b1a2b2..
算法题问一道google面试题(from careercup)
g家电面,被拒了发个A公司的面经
CCup题目2.1是不是有更简单的O(n)的解给定整数数组和两个整数的和,求所有pair。
尘埃落定里面的矩形题g公司面试问Longest increasing subsequence,意义在哪里?
一道g家的几何题对于肯定会面挂的公司大家怎么回
一道有趣的算法题问题:判断一组线段是否相交
相关话题的讨论汇总
话题: point话题: 算法话题: count话题: 蓝点话题: 红点