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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 各位高手试一试?
| l**g 发帖数: 133 | | c*****e 发帖数: 3226 | 5 你说的情况我都考虑到了。
黑我的是这样一个 case. 我是不明白,比如:
(0, 0), (1,100000), 说不能只是2点,但是又要在2点间。
【在 a*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好几年前被考过这道题,当时电面,我先求的斜率,写得乱七八糟的,但也给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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不就是标准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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你说的情况我都考虑到了。 : 黑我的是这样一个 case. 我是不明白,比如: : (0, 0), (1,100000), 说不能只是2点,但是又要在2点间。
| c******l 发帖数: 495 | 8 看起来你连postfix tree这种都没有背得滚瓜烂熟。先端正一下态度吧。
再说下去板上的人要对你扔板砖了。
别装 NB, 自己写一个。你要能写出来,要么你背过,要么这个算法应该是以你命
名的
【在 c*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 别装 NB, 自己写一个。你要能写出来,要么你背过,要么这个算法应该是以你命 : 名的 : 算法。 : 考事实上的经典算法还不算黑?你以为背八股文啊。靠,下次我让你写个完整的 : suffix tree : 算法 interview 应该是考察你用基本的算法理论或者数据结构知识在30分钟内去解决 : 一个相对并不复杂问题的能力。 : : 不就是标准bresenham algorithm吗?这还不算放水吗?
| c*****e 发帖数: 3226 | 9 你只要了解 suffix tree 的基本原理以及怎么运用,谁还自己写一个Ukkonen suffix
tree ?你估计都不明白,装NB, stack over flow 上对这个的描述是好几大段
【在 c******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看起来你连postfix tree这种都没有背得滚瓜烂熟。先端正一下态度吧。 : 再说下去板上的人要对你扔板砖了。 : : 别装 NB, 自己写一个。你要能写出来,要么你背过,要么这个算法应该是以你命 : 名的
| J***A 发帖数: 26 | 10 Move on吧。
很多烙印喜欢拿自己熟悉的内容炫耀一下,遇到了这种就move on。CS内容博大精深,
很多内容如果实际工作中没有解决过,面试的时候是很难很全面的答出来的。其实如果
你问这个面试官一个你熟悉的问题,可能他也答不上来。 |
|