一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 465|回复: 11
收起左侧

[算法题] 请问有人用python AC leetcode149题么?求答案

[复制链接] |试试Instant~ |关注本帖
qlshun 发表于 2017-10-31 05:28:18 | 显示全部楼层 |阅读模式

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

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

x
我自己怎么都通不过全部test case,貌似python的精度不够啊
jason123 发表于 2017-11-2 16:29:16 | 显示全部楼层
是的,精度不够,你可以import numpy 用 longdouble
回复 支持 反对

使用道具 举报

 楼主| qlshun 发表于 2017-11-2 23:08:36 | 显示全部楼层
jason123 发表于 2017-11-2 16:29
是的,精度不够,你可以import numpy 用 longdouble

非常感谢你的回复,请问你的code能AC么?我用了longdouble还是不能ac
回复 支持 反对

使用道具 举报

greenmoon55 发表于 2017-11-2 23:59:19 | 显示全部楼层
leetcode还可以import numpy??
回复 支持 反对

使用道具 举报

jason123 发表于 2017-11-3 15:04:37 | 显示全部楼层
qlshun 发表于 2017-11-2 23:08
非常感谢你的回复,请问你的code能AC么?我用了longdouble还是不能ac

我的可以
k = np.longdouble((points.y - points[j].y))/np.longdouble((points.x - points[j].x))
if k in slopPointsMap:
    slopPointsMap[k] += 1
else:
    slopPointsMap[k] = 2
回复 支持 反对

使用道具 举报

 楼主| qlshun 发表于 2017-11-6 09:07:29 | 显示全部楼层
greenmoon55 发表于 2017-11-2 23:59
leetcode还可以import numpy??

你想import 什么都可以,只要加在最前面就可以了
回复 支持 反对

使用道具 举报

 楼主| qlshun 发表于 2017-11-6 09:11:11 | 显示全部楼层
jason123 发表于 2017-11-3 15:04
我的可以
k = np.longdouble((points.y - points[j].y))/np.longdouble((points.x - points[j].x))
if  ...

万分感谢你,我用了你的方法真的AC了
回复 支持 反对

使用道具 举报

jason123 发表于 2017-11-7 16:04:34 | 显示全部楼层
qlshun 发表于 2017-11-6 09:11
万分感谢你,我用了你的方法真的AC了

不客气
回复 支持 反对

使用道具 举报

ivanyang 发表于 2017-11-8 02:43:05 | 显示全部楼层
用numpy略违规了其实,我的思路是求最简分数作key而不是浮点数
回复 支持 反对

使用道具 举报

 楼主| qlshun 发表于 2017-11-8 04:18:03 | 显示全部楼层
ivanyang 发表于 2017-11-8 02:43
用numpy略违规了其实,我的思路是求最简分数作key而不是浮点数

是嘛,能不能说的更详细点或贴一段代码学习下啊
回复 支持 反对

使用道具 举报

ivanyang 发表于 2017-11-8 04:22:32 | 显示全部楼层
qlshun 发表于 2017-11-8 04:18
是嘛,能不能说的更详细点或贴一段代码学习下啊
  1. # Definition for a point.
  2. # class Point(object):
  3. #     def __init__(self, a=0, b=0):
  4. #         self.x = a
  5. #         self.y = b

  6. class Solution(object):
  7.     def maxPoints(self, points):
  8.         """
  9.         :type points: List[Point]
  10.         :rtype: int
  11.         """
  12.         l = len(points)
  13.         ret = 0
  14.         def gcd(a, b):
  15.             if b == 0:
  16.                 return a
  17.             return gcd(b, a % b)
  18.         for i in range(len(points)):
  19.             same = 0
  20.             vertical = 0
  21.             his = 0
  22.             count = 0
  23.             d = dict()
  24.             for j in range(i + 1, l):
  25.                 nowx = (points[j].x - points[i].x)
  26.                 nowy = (points[j].y - points[i].y)
  27.                 if nowx == 0:
  28.                     if nowy == 0:
  29.                         same += 1
  30.                     else:
  31.                         vertical += 1
  32.                 elif nowy == 0:
  33.                     his += 1
  34.                 else:
  35.                     haha = gcd(abs(max(nowx, nowy)), abs(min(nowx, nowy)))
  36.                     nowx /= haha
  37.                     nowy /= haha
  38.                     if nowx < 0 and nowy > 0:
  39.                         nowx = -nowx
  40.                         nowy = -nowy
  41.                     elif nowx < 0 and nowy < 0:
  42.                         nowx = -nowx
  43.                         nowy = -nowy
  44.                     if str((nowx, nowy)) not in d:
  45.                         d[str((nowx, nowy))] = 1
  46.                     else:
  47.                         d[str((nowx, nowy))] += 1
  48.                     count = max(count, d[str((nowx, nowy))])
  49.             same += max(count, vertical, his) + 1
  50.             ret = max(ret, same)
  51.         return ret
复制代码
我的代码非常乱,仅供参考
回复 支持 反对

使用道具 举报

painkillerA1 发表于 2017-11-8 07:36:49 | 显示全部楼层
用numpy不算违规,这道题不能AC的原因完全在于Python自己对于浮点数的一些设计,楼上那样解决了自然最好,没解决的话我觉得面试完全可以跟面试官说一下临时用个Java什么的,而且一般面试不都白板么,我记得这题不过的也就是一两个边边角角的测试用例
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-20 21:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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