P**********c
发帖数: 3417 | 1 后来大家有一致结论吗？
9.N个矩形，所有矩形都有一条边在同一条直线上，他们相互可能有overlap，找出最后
得到的这个不规则图形的所有边界点
还有那个score(i)的题
8.给N个元素，第i个元素有一个大于0的score(i)，要求随机选出k个，每个元素可以被
选择任意多次，但保证被选择的概率要和score(i)成比例
有人说算score(i)/sum(score(i)), 但是细节上的实现，
是不是先选一个random在(1,n)的数i，然后生成一个(0,1)内的数，看是否小于score(i
)/sum(score(i))来决定是否取i, 如果取了i呢。i的score要调整吗？如何调整？ | d*******l
发帖数: 338 | 2 矩形那个题，这里只说通过overlap形成一个不规则图形的若干个矩形。假设有n个，那
这n个矩形最多有2n条垂直的边。这2n条垂直的边所在的直线和最后图形的交点处才可
能形成分界点。把这些直线按坐标排序，然后用这些直线把原来的那些矩形分成更小的
矩形，把小矩形排序。然后确定每个小区间上的高度，最后扫描一下这些小区间，前后
出现高度差的就构成一个分界点。应该可以做到O(nlogn)。
(i
【在 P**********c 的大作中提到】
: 后来大家有一致结论吗？
: 9.N个矩形，所有矩形都有一条边在同一条直线上，他们相互可能有overlap，找出最后
: 得到的这个不规则图形的所有边界点
: 还有那个score(i)的题
: 8.给N个元素，第i个元素有一个大于0的score(i)，要求随机选出k个，每个元素可以被
: 选择任意多次，但保证被选择的概率要和score(i)成比例
: 有人说算score(i)/sum(score(i)), 但是细节上的实现，
: 是不是先选一个random在(1,n)的数i，然后生成一个(0,1)内的数，看是否小于score(i
: )/sum(score(i))来决定是否取i, 如果取了i呢。i的score要调整吗？如何调整？
| d*******l
发帖数: 338 | 3 第8题我觉得先计算所有score的和，每个元素分配一个区间，比如第i个元素的区间是(
sum(i-1), sum(i)]。然后每次生成一个(0,sum(n)]上的随机数，落在哪个区间就取那
个元素不就完了。
(i
【在 P**********c 的大作中提到】
: 后来大家有一致结论吗？
: 9.N个矩形，所有矩形都有一条边在同一条直线上，他们相互可能有overlap，找出最后
: 得到的这个不规则图形的所有边界点
: 还有那个score(i)的题
: 8.给N个元素，第i个元素有一个大于0的score(i)，要求随机选出k个，每个元素可以被
: 选择任意多次，但保证被选择的概率要和score(i)成比例
: 有人说算score(i)/sum(score(i)), 但是细节上的实现，
: 是不是先选一个random在(1,n)的数i，然后生成一个(0,1)内的数，看是否小于score(i
: )/sum(score(i))来决定是否取i, 如果取了i呢。i的score要调整吗？如何调整？
| P**********c
发帖数: 3417 | 4 某个元素被取之后影响之后被取的概率吗？
是(
【在 d*******l 的大作中提到】
: 第8题我觉得先计算所有score的和，每个元素分配一个区间，比如第i个元素的区间是(
: sum(i-1), sum(i)]。然后每次生成一个(0,sum(n)]上的随机数，落在哪个区间就取那
: 个元素不就完了。
:
: (i
| d*******l
发帖数: 338 | 5 按我对题目的理解是不影响的，每次选取的时候第i个元素被选择的概率和score(i)成
比例就行
【在 P**********c 的大作中提到】
: 某个元素被取之后影响之后被取的概率吗？
:
: 是(
| s*****y
发帖数: 897 | 6 但是某些矩形的顶点或者边可能被另一个矩形覆盖了,这种情况怎么办啊?
【在 d*******l 的大作中提到】
: 矩形那个题，这里只说通过overlap形成一个不规则图形的若干个矩形。假设有n个，那
: 这n个矩形最多有2n条垂直的边。这2n条垂直的边所在的直线和最后图形的交点处才可
: 能形成分界点。把这些直线按坐标排序，然后用这些直线把原来的那些矩形分成更小的
: 矩形，把小矩形排序。然后确定每个小区间上的高度，最后扫描一下这些小区间，前后
: 出现高度差的就构成一个分界点。应该可以做到O(nlogn)。
:
: (i
| d*******l
发帖数: 338 | 7 所有矩形有一条边都是共线的。2n条垂直的边可以把水平方向划分成若干个单位区间，
把所有矩形分割成在单位区间上的小矩形，每个区间上取最高的那个小矩形就可以。相
互覆盖的情况已经蕴涵在里面了，不用特殊考虑。所有矩形的一条边共线是很重要的条
件，没有这个条件这么弄就不行。
【在 s*****y 的大作中提到】
: 但是某些矩形的顶点或者边可能被另一个矩形覆盖了,这种情况怎么办啊?
| s*****y
发帖数: 897 | 8 还是没有想懂
A的右上方那个顶点咋办？完全被B覆盖了。
B--------------
| |
A -------------- |
| | | |
| | | | | s*****y
发帖数: 897 | 9 你的意思是不是把A右边的边向上延伸，求出跟B上面那条边的交点啊？
要是这样子的话,如果多个互相重合,像这种不就挺烦的.
C ----------
| |
B--------------
| | | |
A -------------- | |
| | | | | |
| | | | | |
---------------------------
【在 s*****y 的大作中提到】
: 还是没有想懂
: A的右上方那个顶点咋办？完全被B覆盖了。
: B--------------
: | |
: A -------------- |
: | | | |
: | | | |
| d*******l
发帖数: 338 | 10 先明确一下，这题要求的是最后的不规则图形的边界点，这个理解上没有异议吧？你的
例子中就是A的左下、左上，AB的那个交点，以及B的左上、右上、右下。这个不画出来
要讲清楚确实有点难，你这个图中，B的一条边把A分成了两个矩形，A的一条边（所在
直线）也把B分成了两个矩形，所以我们有4个单位区间上的矩形，第二个区间上有两个
小矩形，一个来自A，一个来自B，我们取高的那个。然后对于每两个相邻的单位区间，
只要有高度差就有两个边界点，否则就没有。
【在 s*****y 的大作中提到】
: 还是没有想懂
: A的右上方那个顶点咋办？完全被B覆盖了。
: B--------------
: | |
: A -------------- |
: | | | |
: | | | |
| | | s*****y
发帖数: 897 | 11 这个真正要code成这样子还挺复杂的吧？
可以上code 吗？
A:(1,0) (1,2) (5,0) (5,2）
B: (2,0) (2,3) (6,0) (6,3）
C: (4,0) (4,4) (8,0) (8,4）
C ----------
| |
B--------------
| | | |
A -------------- | |
| | | | | |
| | | | | |
---------------------------
【在 d*******l 的大作中提到】
: 先明确一下，这题要求的是最后的不规则图形的边界点，这个理解上没有异议吧？你的
: 例子中就是A的左下、左上，AB的那个交点，以及B的左上、右上、右下。这个不画出来
: 要讲清楚确实有点难，你这个图中，B的一条边把A分成了两个矩形，A的一条边（所在
: 直线）也把B分成了两个矩形，所以我们有4个单位区间上的矩形，第二个区间上有两个
: 小矩形，一个来自A，一个来自B，我们取高的那个。然后对于每两个相邻的单位区间，
: 只要有高度差就有两个边界点，否则就没有。
| d*******l
发帖数: 338 | 12 不是很麻烦吧。
#include
#include
#include
using namespace std;
#define MP make_pair
typedef pair PII;
typedef vector VI;
struct FindVertex
{
struct rect
{
int x1, y1, x2, y2;
rect(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d) {}
};
vector rects;
void add(int a, int b, int c, int d)
{
rect r(a, b, c, d);
rects.push_back(r);
}
void solve()
{
int i, j;
VI v;
for(i = 0; i < rects.size(); i++) {
v.push_back(rects[i].x1);
v.push_back(rects[i].x2);
}
sort(v.begin(), v.end());
int k = 0;
for(i = 0; i < v.size(); i++)
if(i == 0 || v[i] != v[i-1])
v[k++] = v[i];
vector > v1;
vector > v2;
for(i = 0; i < rects.size(); i++) {
int x1 = rects[i].x1, x2 = rects[i].x2;
int h = rects[i].y2;
int lo = lower_bound(v.begin(), v.begin()+k, x1) - v.begin();
int hi = lower_bound(v.begin(), v.begin()+k, x2) - v.begin();
for(j = lo+1; j <= hi; j++)
v1.push_back(MP(MP(v[j-1], v[j]), h));
}
sort(v1.begin(), v1.end());
for(i = v1.size()-1; i >= 0; i--)
if(i == v1.size()-1 || v1[i+1].first != v1[i].first)
v2.push_back(v1[i]);
int l = v2.size()-1;
cout << v2[l].first.first << " " << rects[0].y1 << endl;
cout << v2[l].first.first << " " << v2[l].second << endl;
for(i = l; i > 0; i--)
if(v2[i].second != v2[i-1].second) {
cout << v2[i].first.second << " " << v2[i].second << endl;
cout << v2[i-1].first.first << " " << v2[i-1].second << endl;
}
cout << v2[0].first.second << " " << v2[0].second << endl;
cout << v2[0].first.second << " " << rects[0].y1 << endl;
}
};
【在 s*****y 的大作中提到】
: 这个真正要code成这样子还挺复杂的吧？
: 可以上code 吗？
: A:(1,0) (1,2) (5,0) (5,2）
: B: (2,0) (2,3) (6,0) (6,3）
: C: (4,0) (4,4) (8,0) (8,4）
: C ----------
: | |
: B--------------
: | | | |
: A -------------- | |
| d*******l
发帖数: 338 | 13 上面代码中矩形的表示方式是左下和右上顶点的坐标。所有矩形的左下顶点必须都是共
线的。测试的时候这样就可以：
int main()
{
FindVertex fv;
fv.add(1, 0, 5, 2);
fv.add(2, 0, 6, 3);
fv.add(4, 0, 8, 4);
fv.solve();
return 0;
}
最后顺时针输出所有边界上的顶点。 | s*****y
发帖数: 897 | 14 强，赞数学功力，我以为你要用几何的方法求直线交点的
但是anyway,现场没有debugger，我肯定写不出这样子的代码。我再想想有没有适合自
己的方法。
【在 d*******l 的大作中提到】
: 上面代码中矩形的表示方式是左下和右上顶点的坐标。所有矩形的左下顶点必须都是共
: 线的。测试的时候这样就可以：
: int main()
: {
: FindVertex fv;
: fv.add(1, 0, 5, 2);
: fv.add(2, 0, 6, 3);
: fv.add(4, 0, 8, 4);
: fv.solve();
: return 0;
| d*******l
发帖数: 338 | 15 其实没用到什么数学。数学自从高中毕业就在不断遗忘，现在已经忘的差不多了。。
面试的时候要写完整代码比较困难，但可以把思路说的差不多。关键就是要离散化，这
个其实在一类问题中都能用到。
【在 s*****y 的大作中提到】
: 强，赞数学功力，我以为你要用几何的方法求直线交点的
: 但是anyway,现场没有debugger，我肯定写不出这样子的代码。我再想想有没有适合自
: 己的方法。
| p*****u
发帖数: 310 | 16 谁说所有矩形的左下顶点必须都是共线的？难道不能右上顶点和其他矩形的左下顶点共
线？ | d*******l
发帖数: 338 | 17 这个不能凭空猜测，面试的时候肯定要提问澄清。所有矩形都在一条直线一侧好处理些
，如果在两侧，方法还可以是类似的，但会麻烦些
【在 p*****u 的大作中提到】
: 谁说所有矩形的左下顶点必须都是共线的？难道不能右上顶点和其他矩形的左下顶点共
: 线？
| p*****u
发帖数: 310 | | k*j
发帖数: 153 | 19 谁给解释一下第8题？不理解是什么意思。是问以何种方式选出第i个元素？
8.给N个元素，第i个元素有一个大于0的score(i)，要求随机选出k个，每个元素可以被
选择任意多次，但保证被选择的概率要和score(i)成比例 | m**q
发帖数: 189 | 20 我的思路和你类似，不过我觉得每取完一个元素后要把这个元素排除，
这样才能保证第i个被选择概率和score(i)成比例
最简单的实现是每次把取过的元素swap到数组前面，复杂度应该是O(kn)
一个可能的优化的方法是组织成一个顺序统计树，每个节点不是存它的子树的
子节点数，而是存它的子树的score的和，这样每次生成随机数可以用
O(lgn)找到对应节点，选k个数复杂度为O(klgn)。生成树应该需要O(nlgn)。
总复杂度O(nlgn)，如果k是O(n)的话这个方法更优
求指正
是(
【在 d*******l 的大作中提到】
: 按我对题目的理解是不影响的，每次选取的时候第i个元素被选择的概率和score(i)成
: 比例就行
| | | m**q
发帖数: 189 | 21 这个思路我当场肯定想不到...
不过想了想，所有小矩形最多可能有O(n^2)个，
对它们进行排序需要O(n^2*lgn)
如果用sweepling line algorithm，用一个set记录
过程中的端点，应该可以O(nlgn)
【在 d*******l 的大作中提到】
: 不是很麻烦吧。
: #include
: #include
: #include
: using namespace std;
: #define MP make_pair
: typedef pair PII;
: typedef vector VI;
: struct FindVertex
: {
| H****s
发帖数: 247 | 22 第一题就是画skyline那个问题， 经典题，考古一下就可以了。 | d*******l
发帖数: 338 | 23 是不是理解上不同，我的理解就是每次选取时保证第i个被选上的概率和score(i)成正
比就可以，然后每次选取都是相互独立的。你是考虑k次之后的概率吗？那样就不太好
算了
【在 m**q 的大作中提到】
: 我的思路和你类似，不过我觉得每取完一个元素后要把这个元素排除，
: 这样才能保证第i个被选择概率和score(i)成比例
: 最简单的实现是每次把取过的元素swap到数组前面，复杂度应该是O(kn)
: 一个可能的优化的方法是组织成一个顺序统计树，每个节点不是存它的子树的
: 子节点数，而是存它的子树的score的和，这样每次生成随机数可以用
: O(lgn)找到对应节点，选k个数复杂度为O(klgn)。生成树应该需要O(nlgn)。
: 总复杂度O(nlgn)，如果k是O(n)的话这个方法更优
: 求指正
:
: 是(
| d*******l
发帖数: 338 | 24 这种题面试最多说说思路，不太可能写出code。。
你说的对。感觉上像是有nlogn办法，不过要求的是边界点，细节不太好办，你能具体
说说你的方法吗？
【在 m**q 的大作中提到】
: 这个思路我当场肯定想不到...
: 不过想了想，所有小矩形最多可能有O(n^2)个，
: 对它们进行排序需要O(n^2*lgn)
: 如果用sweepling line algorithm，用一个set记录
: 过程中的端点，应该可以O(nlgn)
| m**q
发帖数: 189 | 25 是，我理解是要考虑总的概率，不然选k个就没意义了。
这个题很像一个经典题，从n个数中选k个，保证每个数被选择的概率相等。
那题的一个解法就是每选出一个就把选出的swap到数组前面，保证不参与
后面的选择。大概的代码是这样的:
//assume rand(i) generates random number within [0, i-1]
for (int i=0; i
int r = i + rand(n-i);
swap(a[r], a[i]);
}
//the selected items are a[0]~a[k-1]
我觉得这个题是类似的，区别是每个数被选择的概率和score[i]成正比。
我说的swap的方法可以保证k次之后总的概率满足题目要求，只是每个
元素最多只会被选择一次。选择多次的话不知道怎么实现
【在 d*******l 的大作中提到】
: 是不是理解上不同，我的理解就是每次选取时保证第i个被选上的概率和score(i)成正
: 比就可以，然后每次选取都是相互独立的。你是考虑k次之后的概率吗？那样就不太好
: 算了
| g*****i
发帖数: 2162 | 26 矩形题讲思路就可以了,思路对面试官会引导你的. | m**q
发帖数: 189 | 27 思路大概是这样的
因为所有矩形的底边都在x轴上，把每个矩形的左上角和右上角的坐标记录到
一个数组中，每个元素是 pair, int start>，每个矩形
在数组中有两个元素，代表左右两条边，start为1表示开始，为0表示结束。
比如，一个矩形的x轴开始坐标为x1，结束坐标为x2，高为y，则在数组中它
对应的两个元素是 <, 1>, <, 0>
可知n个矩阵生成的数组中有2n个元素，然后sort数组，复杂度O(nlgn)
然后用sweepling line algorithm，扫描数组，用一个BST记录当前
overlapping的所有矩形。
遇到矩形的左边时(start==1)，判断边的高度（即当前y值）是否大于BST中
的最大高度，大于则记录两个点，（当前x值，BST中最大高度），
(当前x值，当前y值)。把当前y值放入BST
遇到矩形的右边时(start==0),把当前y值从BST中删除，如果BST有相同值只删除
一个。判断边的高度（即当前y值）是否大于当前BST中的最大高度，大于则
记录两个点，（当前x值，当前y值），（当前x值，BST中最大高度）
这样每一步操作BST最多是O(lgn)，总复杂度O(nlgn)
【在 d*******l 的大作中提到】
: 这种题面试最多说说思路，不太可能写出code。。
: 你说的对。感觉上像是有nlogn办法，不过要求的是边界点，细节不太好办，你能具体
: 说说你的方法吗？
| m**q
发帖数: 189 | 28 平时都写纯C，STL不熟，现查的写的伪代码，可能有些地方不准确
假设sort后的数组为a，长度是2n，则sweeping line算法大概是这样的
multiset s;
vector v;
for (int i=0; i<2n; i++) {
if (a[i].second) { //start is 1, left edge
add_points(v, a[i].first, *(s.rbegin());
s.insert(a[i].first.second);
} else { //start is 0, right edge
s.erase(s.find(a[i].first.second)); //only removes ONE if
multiple values are the same
add_points(v, a[i].first, *(s.rbegin());
}
}
void add_points(vector &v, pair p, int max)
{
if (p.second > max) {
v.push_back(p.first, max); //(x,max)
v.push_back(p.first, p.second); //(x,y)
}
}
开始和结束可能需要特殊处理一下，另外代码也没有处理set为空等边界情况
【在 m**q 的大作中提到】
: 思路大概是这样的
: 因为所有矩形的底边都在x轴上，把每个矩形的左上角和右上角的坐标记录到
: 一个数组中，每个元素是 pair, int start>，每个矩形
: 在数组中有两个元素，代表左右两条边，start为1表示开始，为0表示结束。
: 比如，一个矩形的x轴开始坐标为x1，结束坐标为x2，高为y，则在数组中它
: 对应的两个元素是 <, 1>, <, 0>
: 可知n个矩阵生成的数组中有2n个元素，然后sort数组，复杂度O(nlgn)
: 然后用sweepling line algorithm，扫描数组，用一个BST记录当前
: overlapping的所有矩形。
: 遇到矩形的左边时(start==1)，判断边的高度（即当前y值）是否大于BST中
| d*******l
发帖数: 338 | 29 我觉得是对的。扫描线加某种区间数据结构是挺常用的办法，本来我想水平线扫描，但
不好处理多个分开的区间。这题的条件使垂直线扫描比较可行，因为不会有分开的两个
区间。很不错的方法！
【在 m**q 的大作中提到】
: 思路大概是这样的
: 因为所有矩形的底边都在x轴上，把每个矩形的左上角和右上角的坐标记录到
: 一个数组中，每个元素是 pair, int start>，每个矩形
: 在数组中有两个元素，代表左右两条边，start为1表示开始，为0表示结束。
: 比如，一个矩形的x轴开始坐标为x1，结束坐标为x2，高为y，则在数组中它
: 对应的两个元素是 <, 1>, <, 0>
: 可知n个矩阵生成的数组中有2n个元素，然后sort数组，复杂度O(nlgn)
: 然后用sweepling line algorithm，扫描数组，用一个BST记录当前
: overlapping的所有矩形。
: 遇到矩形的左边时(start==1)，判断边的高度（即当前y值）是否大于BST中
| a**********2
发帖数: 340 | 30 赞
【在 m**q 的大作中提到】
: 平时都写纯C，STL不熟，现查的写的伪代码，可能有些地方不准确
: 假设sort后的数组为a，长度是2n，则sweeping line算法大概是这样的
: multiset s;
: vector v;
: for (int i=0; i<2n; i++) {
: if (a[i].second) { //start is 1, left edge
: add_points(v, a[i].first, *(s.rbegin());
: s.insert(a[i].first.second);
: } else { //start is 0, right edge
: s.erase(s.find(a[i].first.second)); //only removes ONE if
|
|
