Python技术迷

月入15000,早9晚6,周末双休每天闲的发霉,没人和你说话,一直不开心还要坚持下去吗?

月入1万5,早9晚6,双休,活还不多,按理说这配置已经能把不少打工人馋得咽口水了。结果人坐那儿,像被扔进静音模式,一天到晚没人搭话,闲得发霉,心情还持续往下掉,这就挺真实。

Image

评论区有人说,先干着,钱到位了孤独也得忍。也有人说,这种班看着轻松,其实最磨人,像慢慢掉电。后者我更信。上班不是坐牢,最怕的不是忙,是你每天像空气,连个说句废话的人都没有。人一旦长期没反馈,工资再体面,心也会拧巴。

当然,立马裸辞也没必要,毕竟1万5不是大风刮来的。但真干到每天起床都烦,公司再安静,脑子里都已经开始报警了。这种班,适合过渡,不适合硬熬。钱是工资,闷是工伤。

算法题:到达终点数字

这题第一眼看着像 BFS,真下手写一遍你就会后悔。数字轴从 0 出发,第 1 步走 1,第 2 步走 2,第 n 步走 n,每一步可以往左也可以往右,问最少几步走到 target。

这种题我一般先不碰搜索。因为步数一大,状态马上散开,代码也不好看。先把问题压成数学题。

先把 target 取绝对值,往左往右是对称的,-5 和 5 没区别。然后先假设每一步都往右走,走了 k 步以后,最远能到:

s = 1 + 2 + 3 + ... + k

也就是:

s = k * (k + 1) // 2

如果刚好 s == target,那答案就是 k,这个没什么好说的。

麻烦在于 s > target。但这里有个关键观察:如果我把某一步从“向右”改成“向左”,总距离不是少 1,也不是少这一步,而是少 2 * step。因为原来是 +step,现在变成 -step,一来一回差了两倍。

所以问题就变成了:当 s >= target 时,差值 d = s - target 能不能通过若干个步长的两倍凑出来。再说白一点,只要 d 是偶数,就一定能调出来;如果 d 是奇数,就还得继续往后走,直到差值变成偶数。

代码其实就两段循环,没必要写花。

classSolution:
defreachNumber(self, target: int) -> int:
        target = abs(target)
        step = 0
        s = 0

while s < target:
            step += 1
            s += step

while (s - target) % 2 != 0:
            step += 1
            s += step

return step

拿 target = 5 试一下。

前 1 步和是 1,前 2 步和是 3,前 3 步和是 6。现在已经超过 5 了,差值是 1,奇数,说明没法只靠翻转某几步凑出来。再走一步,和是 10,差值 5,还是奇数。再走一步,和是 15,差值 10,偶数,这时候就能通过翻转若干步抵消掉 10,答案就是 5。

这题好就好在,一旦看出“翻转一步等价于减掉两倍步长”,后面就很顺。很多人卡在“超过 target 怎么办”,其实超过不可怕,奇偶性才是核心。

时间复杂度也不高。因为前缀和增长是二次的,step 大概是 sqrt(target) 级别,循环跑得很快。面试里真要我写这题,我宁可写这种干净的数学解,也不愿意上来就 BFS 把自己写进沟里。