程序员老鬼

面试一个27岁的前端开发,已敲定要发 offer。结果谈到作息,他说只接受朝九晚六不加班,周末必须双休,连临时支援都不接受

27岁前端,技术面都过了,offer都快发了,结果卡在一句话:朝九晚六,不加班,周末双休,临时支援也别找我。

Image

这话一出来,估计招聘那边表情都僵了。不是他说得离谱,是他说得太实在了。现在很多公司嘴上写“双休”,后面都藏着一句“看业务情况”。你真按字面理解,反而像你不懂规矩。

求职的想找个正常班,公司想找个随叫随到的“有责任心”。话都没错,放一起就直接撞车。说白了,这不是前端不前端的问题,是谁还愿意拿生活给KPI垫背。成年人找工作,能把丑话提前说透,反而省得后面互相演。

面试题:到达终点数字

1、2、3、4 这么往前跳,看着像小学题,真写起来,不少人第一反应还是 DFS、BFS,甚至真去枚举正负号。这个路子我第一眼就不太信。数据一大,树一展开,分支直接炸了。

这题叫“到达终点数字”。规则很简单:第 i 次必须走 i 步,可以向左也可以向右,问最少多少步能走到 target。

这种题别急着在方向上打转,先盯住“步长和”本身。 走了 k 步,不管中间怎么拐,能拿到的总步长就是:

1 + 2 + 3 + ... + k = k * (k + 1) / 2

真正决定你能不能落到目标点的,不是“路径长什么样”,而是这个总和能不能通过若干次“翻转方向”修出来。

我一般先把题目里的 target 取绝对值。左边右边是对称的,没必要把负数单独当回事。

假设走了 k 步,总和是 sum。如果一路都往右,就是落在 sum。 现在想落到 target,差值是 sum - target。

这里有个关键点: 把某一步从“向右”改成“向左”,位置会少 2 * step。 所以你最后能不能修到目标,只看 sum - target 是不是偶数。

这个判断很值钱,很多人代码绕半天,其实就差在这一下。

举个例子,target = 2。

  • 走 1 步,sum = 1,不够
  • 走 2 步,sum = 3,超过了 但 sum - target = 1,是奇数,修不了
  • 走 3 步,sum = 6sum - target = 4,偶数,可以修

怎么修?把第 2 步翻过去就行。+1 -2 +3 = 2

所以这题压根不用搜索。一路把 sum 往上加,直到同时满足两个条件:

  • sum >= target
  • (sum - target) 是偶数

满足时,当前步数就是答案。

代码我按平时写法给,不搞那些花里胡哨的模板:

publicclassReachNumber{

publicintreachNumber(int target){
        target = Math.abs(target);

int step = 0;
int sum = 0;

while (sum < target || ((sum - target) & 1) != 0) {
            step++;
            sum += step;
        }

return step;
    }

publicstaticvoidmain(String[] args){
        ReachNumber solution = new ReachNumber();
        System.out.println(solution.reachNumber(2));   // 3
        System.out.println(solution.reachNumber(3));   // 2
        System.out.println(solution.reachNumber(4));   // 3
        System.out.println(solution.reachNumber(-5));  // 5
    }
}

这段代码短,但思路是完整的。

再补一句,为什么这样一定能停? 因为 sum 会一直增长,而奇偶性也会在后续步数里被修正。最多再多走两步,奇偶问题基本就能抹平,不会卡死。

时间复杂度也很老实,不是 O(target),而是接近 O(sqrt(target))。因为前 k 项和是二次增长,sum 很快就超过目标了。空间复杂度 O(1)。

这题挺适合拿来练一个习惯: 别一看到“最少步数”“左右选择”就条件反射上搜索。先看数学约束在不在。很多题表面像路径问题,骨子里其实是和、差、奇偶性。这个口子一旦看见,代码就会一下子变短,味道也对了。