LeetCode

max points on a line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

如何判断一个平面内的几个点在同一条直线上,可以通过直线L的斜率来判断,可以比较是一次函数y=kx+b的斜率来判断,只要经过同一点的直线并且斜率相同,就可以判断是一条直线。

# Definition for a point
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
	length = len(points)
	# 少于3个点,也就不存在多条直线了,直接返回点数
        if length < 3: return length
        res = 1
	#经过其中的一个点,于其他的点连成几条直线
        for i in range(length):
            #要考虑到斜率为0(水平于x轴),或者为无限(水平于y轴)的情况
	    slope = {'inf':0}
            samep = 1 #还要考虑相同点的情况
            a = points[i]
	    # 和前面连过的点就不用考虑了,直线不用考虑方向,从左到右从右到左都是一条直线
            for j in range(i+1,length):
                b = points[j]
                if a.x == b.x and a.y != b.y:
		    # 水平于y轴
		    slope['inf'] += 1
                elif a.x != b.x:
                    k = 1.0*(a.y - b.y) / (a.x - b.x)
                    # 统计不同斜率的点数
		    slope[k] = 1 if k not in slope else slope[k] + 1
                else:
                    samep += 1
            res = max(res, max(slope.values()) + samep)
        return res

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

思路是位运算的异或运算 (a xor b) xor b = a,相同的两个数异或为0,单出来的那个数异或0还是那个数,就找出单下来的那个数了

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        res = 0
        for i in A:
            res = i^res
        return res
Tag:code Published under (CC) BY-NC-SA