我刷到一条帖子:有人月薪3.9万,年终奖发4个月,结果去年一把梭哈按年终奖发,税交得心都在滴血。今年他提前跟公司对齐口径,把其中1.2万拆进工资里发,算下来能少交一万多
网友们也很真实:有人说“年终奖先别急着感谢老板,先感谢税法”;还有人吐槽“我去年不懂,交完税才发现自己在给国家买奶茶”;也有人提醒“别瞎操作,走正规方案,跟财务沟通清楚最稳”。
我觉得这事特别像写代码:同样的功能,写法不同,性能差一截。钱也是,发放路径选对了,少交的那点税就像白捡的隐藏福利。
提前沟通这一步,真比年底临时抱佛脚靠谱多了。
算法 题: 直线镜像
昨天我在公司电梯里照镜子你们懂吧…那种不锈钢门,脸被拉长一倍,我同事还说“东哥你最近是不是瘦了”,我说瘦个屁,是镜像轴歪了…然后我就想到算法题里那个“直线镜像”,就很像:给一堆点,问你有没有一条竖直的线 x = c,把所有点一折过去还能一一对应上。听起来玄学,其实就是找“中线”。
我一般先不急着写代码,先拿几个点在纸上画两下:如果存在镜像线,而且题目叫“直线镜像”又不说斜率啥的,十有八九就是 竖直镜像 (x 方向对称,y 不变)。那中线 c 的位置怎么找?你看最左边的点 xMin,最右边的点 xMax,中线肯定在它俩中间,所以有个固定值: xMin + xMax = 2c 我不直接算 c,怕小数,干脆记 sum = xMin + xMax ,后面镜像点就是 (sum - x, y) ,全程整数,舒服。
然后麻烦点来了:点可能重复。你用 HashSet 只存存在性,重复点就容易“看起来都在”但数量对不上,跟你衣柜两只袜子颜色一样其实一只是左一只是右…所以我用计数 Map,见一个点 +1,匹配到镜像点就 -1,最后全归零才算真对称。
口嗨完了上代码,Java 写起来就那几行,关键是把 (x,y) 编码成 long,当 key 用,别整 Pair 类还要重写 hashCode,我懒。
import java.util.*;
publicclassMain{
// 把(x,y)塞进一个long:高32位放x,低32位放y(y转无符号)
staticlongkey(int x, int y){
return (((long) x) << 32) ^ (y & 0xffffffffL);
}
publicstaticbooleanisReflected(int[][] points){
if (points == || points.length == 0) returntrue;
int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
HashMap cnt = new HashMap<>;
for (int[] p : points) {
int x = p[0], y = p[1];
minX = Math.min(minX, x);
maxX = Math.max(maxX, x);
long k = key(x, y);
cnt.put(k, cnt.getOrDefault(k, 0) + 1);
}
long sum = (long) minX + (long) maxX; // = 2c
for (int[] p : points) {
int x = p[0], y = p[1];
int mx = (int) (sum - x); // 镜像x
long mk = key(mx, y);
Integer c = cnt.get(mk);
if (c == || c == 0) returnfalse;
if (c == 1) cnt.remove(mk);
else cnt.put(mk, c - 1);
}
returntrue;
}publicstaticvoidmain(String[] args){
int pts = { {1,1}, {2,1}, {2,2}, {1,2} };
System.out.println(isReflected(pts));
}
}
你看这个思路就很“电梯镜子”:先找左右边界,确定那条“中线的两倍”,然后每个点去找它在镜子里的那一张脸…找不到就说明镜子是歪的,或者你同事真瘦了(反正不可能是我)。
哦对了,复杂度就是 O(n),Map 操作均摊 O(1)。我之前还见人排序按 y 分组再双指针,能做但太累,写到一半还得去接水,回来就忘了指针在哪…算了不折腾。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.