📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 6492| 回复: 8
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : 找出穿过点最多的直线

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
二维平面上有若干点,求出一条直线能穿越最多的点

上一篇:Microsoft : validate a BST
下一篇:Google Intern : two sorted array 中,求和等于指定数的组合
🔗
 楼主| wwwyhx 2011-8-18 15:05:08 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-8-19 12:50 编辑

XOXOXOXOXOXOXOXOXOXO
回复

使用道具 举报

🔗
zach 2011-8-19 05:15:57 | 只看该作者
全局:
给外行说说算法吧,我这各种看不懂C了。。。。你这是各种指针?。。。求科普
回复

使用道具 举报

🔗
FlyInSky 2011-8-19 08:35:42 | 只看该作者
全局:
看不懂唉。。我怎么感觉效率不可能这么高?2楼那个是答案?
回复

使用道具 举报

🔗
FlyInSky 2011-8-19 08:59:31 | 只看该作者
全局:
看不懂唉。。我怎么感觉效率不可能这么高?2楼那个是答案?
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-8-19 12:37:57 | 只看该作者
全局:
给外行说说算法吧,我这各种看不懂C了。。。。你这是各种指针?。。。求科普
zach 发表于 2011-8-19 05:15



    啊,贴错了,这个不是这题的答案
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-8-19 12:49:36 | 只看该作者
全局:
用hashtable这个万金油的方法做的,由更好的吗?
顺便指出careercup一个bug, 不是所有线都可以用double表示斜率的,垂直的线斜率是无穷大

  1. struct PT
  2. {
  3.         float x;
  4.         float y;
  5. };

  6. struct LINE
  7. {
  8.         bool bVertical;
  9.         float k;
  10.         float b;// y axle intersection if none vertical, x axle intersection if vertical line
  11. };

  12. bool Equal(float x, float y)
  13. {
  14.         return (x - y) >= -0.00000001 && (x - y) <= 0.00000001;
  15. }

  16. LINE findLine(PT pts[], int n)
  17. {
  18.         assert(pts && n > 1);

  19.         LINE line;
  20.         int nMax = 0;

  21.         for (int i = 0; i < n-1; i++)
  22.         {
  23.                 hash_map<float, int> map;
  24.                 int nVertical = 0;

  25.                 for (int j = i+1; j < n; j++)
  26.                 {
  27.                         if (Equal(pts[i].x, pts[j].x))
  28.                         {
  29.                                 nVertical++;
  30.                                 if (nVertical > nMax)
  31.                                 {
  32.                                         line.bVertical = true;
  33.                                         line.b = pts[i].x;
  34.                                         nMax = nVertical;
  35.                                 }
  36.                         }
  37.                         else
  38.                         {
  39.                                 float k = (pts[j].y - pts[i].y)/(pts[j].x - pts[i].x);
  40.                                 if (map.find(k) != map.end())
  41.                                         map[k]++;
  42.                                 else
  43.                                         map[k] = 1;

  44.                                 if (map[k] > nMax)
  45.                                 {
  46.                                         line.bVertical = false;
  47.                                         line.k = k;
  48.                                         line.b = pts[i].y - k * pts[i].x;
  49.                                         nMax = map[k];
  50.                                 }
  51.                         }
  52.                 }
  53.         }

  54.         return line;
  55. }
复制代码
回复

使用道具 举报

🔗
coder 2011-8-21 06:10:15 | 只看该作者
全局:
楼上的Java版。

  1. import java.util.HashMap;

  2. public class Line_with_most_nodes {

  3.         private Points points[];
  4.         private HashMap map;
  5.         private double k;
  6.         private double b;
  7.         private int vertical;
  8.         private boolean is_vertical;
  9.         public Line_with_most_nodes(Points points[]) {
  10.                 // TODO Auto-generated constructor stub
  11.                 this.points=points;
  12.                 map=new HashMap();
  13.                 vertical=0;
  14.         }
  15.         public void find_k(){
  16.                 double nMax=0;
  17.                 int temp;
  18.                 for(int i=0;i<points.length;i++){
  19.                         for(int j=i+1;j<points.length;j++){
  20.                                 if(points[i].x==points[j].x){
  21.                                         vertical++;
  22.                                         if(nMax<vertical){
  23.                                                 nMax=vertical;
  24.                                                 is_vertical=true;
  25.                                         }
  26.                                 }
  27.                                 else{
  28.                                         double temp_k=(points[i].y-points[j].y)/(points[i].x-points[j].x);
  29.                                         if(!map.containsKey(k)){
  30.                                                 temp=(Integer) map.get(temp_k);
  31.                                         }
  32.                                         else{
  33.                                                 temp=0;
  34.                                         }
  35.                                         map.put(temp_k, temp++);
  36.                                         if(nMax<temp++){
  37.                                                 nMax=temp_k;
  38.                                                 is_vertical=false;
  39.                                         }
  40.                                 }
  41.                                 if(!is_vertical){
  42.                                         k=nMax;
  43.                                         b=points[i].y-k*points[i].x;
  44.                                 }
  45.                                 else{
  46.                                         b=points[i].x;
  47.                                 }
  48.                         }
  49.                 }
  50.         }

  51.         public static void main(String[] args) {
  52.                 // TODO Auto-generated method stub

  53.         }
  54.        
  55.         public class Points{
  56.                 public double x;
  57.                 public double y;
  58.                 public double getX() {
  59.                         return x;
  60.                 }
  61.                 public void setX(double x) {
  62.                         this.x = x;
  63.                 }
  64.                 public double getY() {
  65.                         return y;
  66.                 }
  67.                 public void setY(double y) {
  68.                         this.y = y;
  69.                 }
  70.         }
  71. }
复制代码
回复

使用道具 举报

🔗
iveney 2011-8-24 09:46:46 | 只看该作者
全局:
枚舉每兩個點得出穿過它們的直綫的斜率 dx / dy, 然後 increment 對應直綫的 counter. 因爲最多有 n^2 條直綫所以 size 是 O(n^2).
time complexity 是 O(n^2).
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表