请问有人用python AC leetcode149题么？求答案

我自己怎么都通不过全部test case，貌似python的精度不够啊

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

复制代码

我的代码非常乱，仅供参考

qlshun 发表于 2017-11-2 23:08
非常感谢你的回复，请问你的code能AC么？我用了longdouble还是不能ac

我的可以
k = np.longdouble((points[i].y - points[j].y))/np.longdouble((points[i].x - points[j].x))
if k in slopPointsMap:
    slopPointsMap[k] += 1
else:
    slopPointsMap[k] = 2

用numpy不算违规，这道题不能AC的原因完全在于Python自己对于浮点数的一些设计，楼上那样解决了自然最好，没解决的话我觉得面试完全可以跟面试官说一下临时用个Java什么的，而且一般面试不都白板么，我记得这题不过的也就是一两个边边角角的测试用例

是的，精度不够，你可以import numpy 用 longdouble

jason123 发表于 2017-11-2 16:29
是的，精度不够，你可以import numpy 用 longdouble

非常感谢你的回复，请问你的code能AC么？我用了longdouble还是不能ac

leetcode还可以import numpy??

greenmoon55 发表于 2017-11-2 23:59
leetcode还可以import numpy??

你想import 什么都可以，只要加在最前面就可以了

jason123 发表于 2017-11-3 15:04
我的可以
k = np.longdouble((points.y - points[j].y))/np.longdouble((points.x - points[j].x))
if  ...

万分感谢你，我用了你的方法真的AC了

qlshun 发表于 2017-11-6 09:11
万分感谢你，我用了你的方法真的AC了

不客气

用numpy略违规了其实，我的思路是求最简分数作key而不是浮点数

ivanyang 发表于 2017-11-8 02:43
用numpy略违规了其实，我的思路是求最简分数作key而不是浮点数

是嘛，能不能说的更详细点或贴一段代码学习下啊