程序员老鬼

税前 41k,税后到手 30k。和女友合租两居,房租分摊 3300,每月吃饭、出行、购物合计 14000。每年能存 14万,周末可以周边游~

刚刷到这个,第一反应是:月薪四万多,听着挺猛,落到北京也就是“日子过得还行”。

税后一到手三万,和女朋友合租,房租自己出三千多,吃饭、打车、买东西一个月再花一万多。平时确实不抠,周末能出去转转,手机坏了直接换,不至于为了几十块钱纠结。

Image

一年还能攒十四万,放普通城市已经很舒服了。可一看北京房价,人又老实了。首付不是少买几杯咖啡就能省出来的,得按年熬。

这就是互联网中层最真实的状态吧,消费挺自由,人生大件一点不自由。工资看着高,离“随便选”还差得远。

今日面试题

判断四个点能不能组成正方形,别急着算角度

四个点丢进来,顺序是乱的。

你要是上来就认定 p1、p2 是一条边,再用斜率判断垂直,代码很快就会绕进去。斜率还得处理竖线,点的排列顺序也有二十多种,这种写法我一般不碰,看着就不稳。

这道题真正有用的信息,不是点的顺序,而是四个点之间的距离。

四个点两两组合,一共能算出 6 个距离。正方形的 6 条距离很固定:

  • 4 条边,长度相等;
  • 2 条对角线,长度相等;
  • 对角线比边长;
  • 边长不能为 0。

这里没必要开平方。距离只拿来比较,直接计算距离平方更省事:

distance = (x1 - x2)² + (y1 - y2)²

拿一个边长为 2 的正方形来说,四条边的距离平方都是 4,两条对角线的距离平方都是 8。

把 6 个距离平方排个序,结果应该长这样:

边  边  边  边  对角线  对角线
4   4   4   4     8       8

所以判断条件可以压到三行:

最短距离不能为 0
前四个距离相等
最后两个距离相等

Java 实现我会这样写:

import java.util.Arrays;

publicclassSquareChecker{

publicbooleanisValidSquare(
int[] a, int[] b, int[] c, int[] d)
{

int[][] points = {a, b, c, d};
long[] gaps = newlong[6];
int cursor = 0;

for (int left = 0; left < points.length; left++) {
for (int right = left + 1; right < points.length; right++) {
                gaps[cursor++] = squaredGap(points[left], points[right]);
            }
        }

        Arrays.sort(gaps);

boolean sideExists = gaps[0] > 0;
boolean fourSidesEqual =
                gaps[0] == gaps[1]
                && gaps[1] == gaps[2]
                && gaps[2] == gaps[3];

boolean twoDiagonalsEqual = gaps[4] == gaps[5];

return sideExists && fourSidesEqual && twoDiagonalsEqual;
    }

privatelongsquaredGap(int[] first, int[] second){
long dx = (long) first[0] - second[0];
long dy = (long) first[1] - second[1];
return dx * dx + dy * dy;
    }
}

这里有个小地方别随手写成 int。

坐标相减后还要平方,一旦坐标范围比较大,dx * dx 可能先在 int 里溢出,再赋值给 long。所以我在做减法之前就转成了 long,不是等乘完再转。

还要注意重合点。

例如四个点里有两个点坐标相同,排序后最短距离就是 0。只判断“四条短边相等、两条长边相等”,这种退化图形有机会混进来,所以 gaps[0] > 0 不能省。

这套写法没有判断谁挨着谁,也没有计算斜率和夹角。输入顺序再乱,最后都只剩 6 个数字。

时间复杂度可以看成 O(1)。虽然代码里有排序,但排序的永远只有 6 个元素,这点开销不用惦记。真正该防的是距离溢出和重复点,算法题里不少错误就藏在这种不起眼的地方。