c*****e
发帖数: 3226 | | a*******g
发帖数: 1221 | 2 好几年前被考过这道题，当时电面，我先求的斜率，写得乱七八糟的，但也给onsite了
。后来想了想，这个得用向量做。假设输入是两个点(x1, y1), (x2, y2)，然后核心算
法是一个大循环
for (x = 最小的X; x <= 最大的X； ++x) {
利用 (y-y1)/(x-x1) = (y2-y)/(x2-x)
求出 y=(x*y1-x*y2+x1*y2-x2*y1)/(x1-x2)
这时(x,y)是浮点数，如果(x,y)在屏幕内，
打印出离(x,y)最近的整数像素点
}
有些corner case处理一下，譬如AB两点在同一条竖线上。能想到的优化就是有些常数
提前计算好了；再就是可以先算下斜率，如果是线接近水平的话循环X，如果线接近竖
直的话循环Y；再一个优化就是可以先在循环前先求一下X的范围，不必要把X的所有可
能都试一遍。
当然画两点间的线段和两点间的直线不同，线段简单些。 | c******l
发帖数: 495 | 3 不就是标准bresenham algorithm吗？这还不算放水吗？
【在 c*****e 的大作中提到】
: 各位高手试一试？
| l**g
发帖数: 133 | | c*****e
发帖数: 3226 | 5 你说的情况我都考虑到了。
黑我的是这样一个 case. 我是不明白，比如：
(0, 0), (1,100000), 说不能只是2点，但是又要在2点间。
【在 a*******g 的大作中提到】
: 好几年前被考过这道题，当时电面，我先求的斜率，写得乱七八糟的，但也给onsite了
: 。后来想了想，这个得用向量做。假设输入是两个点(x1, y1), (x2, y2)，然后核心算
: 法是一个大循环
: for (x = 最小的X; x <= 最大的X； ++x) {
: 利用 (y-y1)/(x-x1) = (y2-y)/(x2-x)
: 求出 y=(x*y1-x*y2+x1*y2-x2*y1)/(x1-x2)
: 这时(x,y)是浮点数，如果(x,y)在屏幕内，
: 打印出离(x,y)最近的整数像素点
: }
: 有些corner case处理一下，譬如AB两点在同一条竖线上。能想到的优化就是有些常数
| c*****e
发帖数: 3226 | 6 别装 NB, 自己写一个。你要能写出来，要么你背过，要么这个算法应该是以你命
名的
算法。
考事实上的经典算法还不算黑？你以为背八股文啊。靠，下次我让你写个完整的
suffix tree
算法 interview 应该是考察你用基本的算法理论或者数据结构知识在30分钟内去解决
一个相对并不复杂问题的能力。
不就是标准bresenham algorithm吗？这还不算放水吗？
【在 c******l 的大作中提到】
: 不就是标准bresenham algorithm吗？这还不算放水吗？
| a*******g
发帖数: 1221 | 7 噢，对，我想起来了，我当时也是这样的。我之前提到，你可以算一下斜率，如果接近
竖直，就循环Y值。当然这种方法也不太好。我想到能不能这样。
我先计算一个单位长的方向向量t=(dx,dy)=(x1-x2,y1-y2)/sqrt((x1-x2)^2+(y1-y2)^2)
然后从某一点开始，利用这个单位长的方向向量一直延伸，把剩下的点都画出来
譬如(x1+dx,y1+dy), (x1+2dx,y1+2dy), ..., (x1+ndx,y1+ndy)。画直线的话就要从(
x1,y1)向(dx,dy)延伸，也同时向(-dx,-dy)延伸。
你说的情况我都考虑到了。
【在 c*****e 的大作中提到】
: 你说的情况我都考虑到了。
: 黑我的是这样一个 case. 我是不明白，比如：
: (0, 0), (1,100000), 说不能只是2点，但是又要在2点间。
| c******l
发帖数: 495 | 8 看起来你连postfix tree这种都没有背得滚瓜烂熟。先端正一下态度吧。
再说下去板上的人要对你扔板砖了。
别装 NB, 自己写一个。你要能写出来，要么你背过，要么这个算法应该是以你命
名的
【在 c*****e 的大作中提到】
: 别装 NB, 自己写一个。你要能写出来，要么你背过，要么这个算法应该是以你命
: 名的
: 算法。
: 考事实上的经典算法还不算黑？你以为背八股文啊。靠，下次我让你写个完整的
: suffix tree
: 算法 interview 应该是考察你用基本的算法理论或者数据结构知识在30分钟内去解决
: 一个相对并不复杂问题的能力。
:
: 不就是标准bresenham algorithm吗？这还不算放水吗？
| c*****e
发帖数: 3226 | 9 你只要了解 suffix tree 的基本原理以及怎么运用，谁还自己写一个Ukkonen suffix
tree ?你估计都不明白，装NB, stack over flow 上对这个的描述是好几大段
【在 c******l 的大作中提到】
: 看起来你连postfix tree这种都没有背得滚瓜烂熟。先端正一下态度吧。
: 再说下去板上的人要对你扔板砖了。
:
: 别装 NB, 自己写一个。你要能写出来，要么你背过，要么这个算法应该是以你命
: 名的
| J***A
发帖数: 26 | 10 Move on吧。
很多烙印喜欢拿自己熟悉的内容炫耀一下，遇到了这种就move on。CS内容博大精深，
很多内容如果实际工作中没有解决过，面试的时候是很难很全面的答出来的。其实如果
你问这个面试官一个你熟悉的问题，可能他也答不上来。 |
|
