Python技术迷

税前 41k,税后到手 30k。和女友合租两居,房租分摊 3300,每月吃饭、出行、购物合计 14000

刚刷到这个,第一反应是:一个月到手三万,在北京居然也只能算“过得还行”。

他和女友合租两居,自己出三千多。平时吃饭、打车、买东西,一个月差不多花一万四。手机想换就换,周末出去转一圈也不用先看半天余额,一年还能攒个十几万。放普通打工人里,已经挺宽松了。

Image

但一说到买房,立马老实。北京首付那数字摆在那儿,攒一年看着不少,真往房子里一放,跟没动一样。

这就是很多互联网中层的状态吧。日常消费基本不用抠,偶尔还能潇洒一下,但离真正想干嘛就干嘛,差得还挺远。工资看着高,房价专治各种膨胀。

今日算法题

四个点能不能组成正方形,别急着算斜率

四个坐标点摆在面前,判断它们能不能组成一个正方形。

这题看着像几何题,第一反应通常是算斜率:四条边长度相等,相邻边斜率相乘等于 -1。代码真这么写,很快就会碰到竖直线,分母为零,接着还得补浮点误差判断。

这种写法我一般直接放弃。能用整数距离解决的问题,没必要把斜率和浮点数拉进来添乱。

假设输入四个点:

p1 = (0, 0)
p2 = (1, 1)
p3 = (1, 0)
p4 = (0, 1)

四个点之间两两连线,一共会产生 6 个距离。

正方形的这 6 个距离很有特点:

  • 4 条边长度相等;
  • 2 条对角线长度相等;
  • 对角线的平方,等于边长平方的 2 倍。

这里不要真的开平方。两个点之间的距离平方直接算:

(x1 - x2) ** 2 + (y1 - y2) ** 2

这样全程都是整数运算,比较起来干净,也不会出现 1.414213 到底该保留几位的问题。

代码可以直接这么写:

classSolution:
defvalidSquare(
        self,
        p1: list[int],
        p2: list[int],
        p3: list[int],
        p4: list[int]
    )
 -> bool:

        points = [p1, p2, p3, p4]
        distances = []

for left in range(4):
for right in range(left + 1, 4):
                x_gap = points[left][0] - points[right][0]
                y_gap = points[left][1] - points[right][1]
                distances.append(x_gap * x_gap + y_gap * y_gap)

        distances.sort()

        side = distances[0]
if side == 0:
returnFalse

        four_sides_equal = (
            distances[0]
            == distances[1]
            == distances[2]
            == distances[3]
        )

        two_diagonals_equal = distances[4] == distances[5]
        diagonal_length_ok = distances[4] == side * 2

return (
            four_sides_equal
and two_diagonals_equal
and diagonal_length_ok
        )

这段代码里有个判断不能省:

if side == 0:
returnFalse

因为题目给出的四个点可能重复。两个点重合后,最短距离就是 0。要是不拦一下,后面的“边相等”和“对角线相等”有可能把一组退化坐标误判进去。

为什么排序以后,前四个一定是边,后两个一定是对角线?

正方形的对角线比边长,所以 6 个距离排完序,较小的 4 个对应四条边,较大的 2 个对应两条对角线。代码不用关心输入点的顺序,也不用先找左上角、右下角,更不用枚举哪两个点相邻。

这题的数据量固定就是 4 个点,两两计算只做 6 次,排序的也只是 6 个数字。时间复杂度和空间复杂度都可以看成 O(1)。

判断几何图形时,我更愿意先找“距离之间的固定关系”。斜率能做,但边界条件太多。六个整数排个序,问题反而更稳。