传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2608|回复: 3
收起左侧

[其他] 15行搞定leetcode难题max points on a line

[复制链接] |试试Instant~ |关注本帖
Linzertorte 发表于 2014-5-15 05:06:29 | 显示全部楼层 |阅读模式

2014(1-3月)-[12]CS硕士+fresh grad 无实习/全职 - Other| 码农类其他@

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
. visit 1point3acres.com for more.

评分

2

查看全部评分

writecoffee1 发表于 2014-6-14 12:58:42 | 显示全部楼层
Java 20 ~ 23 行也可以搞定了, hahahahahahahahahaha
  1. public int maxPoints(Point[] points) {
  2.     int n = points.length;
  3.     int gMax = 0;
  4. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5.     for (int i = 0; i < n; i++) {
  6.         HashMap<Double, Integer> h = new HashMap<Double, Integer>();
  7.         int lMax = 1, dup = 0;
  8. . 鍥磋鎴戜滑@1point 3 acres
  9.         for (int j = i + 1; j < n; j++) {
  10.             if (points[j].x == points[i].x && points[j].y == points[i].y) {
  11.                 dup++;
  12.             } else {
  13.                 double dx = points[j].x - points[i].x, dy = points[j].y - points[i].y;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.                 double slope = dx == 0.0 ? Integer.MAX_VALUE : 0.0 + dy / dx;

  15.                 if (!h.containsKey(slope)) {
  16.                     h.put(slope, 1);
  17.                 }

  18.                 lMax = Math.max(lMax, h.put(slope, h.get(slope) + 1) + 1);
  19.             }
  20.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦

  21.         gMax = Math.max(lMax + dup, gMax);
  22.     }

  23.     return gMax;
  24. }
复制代码
回复 支持 1 反对 1

使用道具 举报

 楼主| Linzertorte 发表于 2014-5-15 05:07:01 | 显示全部楼层
  1. # Definition for a point. more info on 1point3acres.com
  2. # class Point:
  3. #     def __init__(self, a=0, b=0):
  4. #         self.x = a
  5. #         self.y = b
  6. . from: 1point3acres.com/bbs
  7. class Solution:
  8.     # @param points, a list of Points. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.     # @return an integer
  10.     def maxPoints(self, points):
  11.         best = 0
  12.         for p in points:
  13.             angle_cnt=dict()
  14.             same = 0
  15.             lm = 0. 鍥磋鎴戜滑@1point 3 acres
  16.             for q in points:
  17.                 angle=math.atan2(p.y-q.y,p.x-q.x)
  18.                 if p.x==q.x and p.y==q.y:
  19.                     same += 1.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.                 else:
  21.                     angle_cnt[angle] = angle_cnt[angle]+1 if angle in angle_cnt else 1
  22.                     lm=max(lm,angle_cnt[angle])-google 1point3acres
  23.             best=max(best,same+lm)
  24.         return best
复制代码
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!-google 1point3acres

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 1 反对 0

使用道具 举报

simonwoo 发表于 2017-1-8 07:03:00 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-26 10:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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