程序员老鬼

老公不想工作了咋办?做Java开发7年了,一直做这个,共同买了一套新房,房贷还有15年不到,月供5000多。有个上幼儿园的女儿。

刚看到个贴子,说有姑娘吐槽:老公在杭州做了7年Java,娃上幼儿园,房贷还有十来年,结果突然说“不想工作了”。

Image

我觉得这事吧,先别急着给老公贴“废物”“不负责”的标签。程序员干几年,熬夜、裁员、焦虑,一起上头,很正常。但现实也摆那儿:房贷、娃的学费,每个月都在倒计时,不是说不干就能不干。

我比较认同的是:先把话说明白,搞清楚他是不想上这份班,还是压根不想再挣钱了。如果是职业倦怠,可以商量换城市、降薪转岗、短暂休整,但要有时间表和具体计划,而不是摊手摆烂。

婚姻更像合伙开公司:有人想改赛道可以理解,但现金流不能断。一起面对问题,比互相埋怨更有用。

面试题:缺失的区间

前两天和测试在对账,一个服务每天要生成 0~99 这 100 条编号的任务,本来应该是 0,1,2,3...99 全都有。结果人家给我扔了一串已经落库的 id:0,1,2,5,6,10... 然后问我一句:哥,你帮我把中间缺的那几段打印出来,我好查日志。

我脑子里第一个反应就是:这不就是算法题里那个“缺失的区间”嘛。

给你一个升序的整型数组 nums,再给你一个下界 lower 和上界 upper,都包含在内。lower 到 upper 这个闭区间里,理论上应该每个整数都在;但实际只有 nums 里这几个。那哪些数(或连续的一段数)是缺的,就要你算出来。输出的时候,单个数写成 "7",一段区间写成 "4->8" 这种。

比如:lower = 0, upper = 9, nums = [0,1,2,5,6,10]那缺的就是:"3->4"、"7->9",10 已经越上界了就不管它。

我会做一件事:永远比较“上一个已经出现过的数”和“当前这个数”之间差了多少。

大致是这么个节奏:

  • 我先假装有一个“上一个数” prev,它放在 lower 的前面一格,也就是 lower - 1。

  • 然后从左往右扫数组 nums,每来一个当前数 cur,就看看 prev 和 cur 中间有没有空档:

    • 如果 cur == prev + 1,说明啥都不缺,贴着的。
    • 如果 cur == prev + 2,说明刚好缺一个数,就是 prev + 1。
    • 如果 cur > prev + 2,说明中间缺了一段,从 prev + 1 一直到 cur - 1。
  • 每次处理完,把 prev 更新成当前数 cur,继续往后看。

  • 数组扫完以后,别忘了尾巴那段。最后再假装有个 upper + 1 当作“终点”,再拿它跟 prev 比一次,就能把尾部的缺失区间也挖出来。

稍微绕一点的地方就是边界:

  • 数组可能是空的,那从 lower 到 upper 全缺。
  • lower / upper 有可能接近 Integer.MIN_VALUE / Integer.MAX_VALUE,lower - 1 或 upper + 1 会溢出。这个时候用 long 来存 prev 和 cur 会安全很多。

直接上 Java 代码,你可以贴到 LeetCode 那题里跑(Missing Ranges 那个):

import java.util.ArrayList;
import java.util.List;

publicclassMissingRanges{

public List<String> findMissingRanges(int[] nums, int lower, int upper){
        List<String> res = new ArrayList<>();

// 用 long 防止 lower - 1 / upper + 1 溢出
long prev = (long) lower - 1;
long cur;

// 把真实数据 + 一个“尾巴上界”拼成统一流程
for (int i = 0; i <= nums.length; i++) {
if (i == nums.length) {
// 最后一次,用 upper + 1 当作“终点”
                cur = (long) upper + 1;
            } else {
// 当前这个数如果在区间外,就直接跳过
if (nums[i] < lower) {
continue;
                }
if (nums[i] > upper) {
// 后面只会更大了,可以直接结束循环
break;
                }
                cur = nums[i];
            }

// 现在 prev 是“上一个有效数”,cur 是“下一个有效数或终点”
if (cur - prev >= 2) {
// 至少缺一个
long start = prev + 1;
long end = cur - 1;
                res.add(formatRange(start, end));
            }

            prev = cur;
        }

return res;
    }

private String formatRange(long start, long end){
if (start == end) {
// 只有一个数
return String.valueOf(start);
        } else {
// 一段区间
return start + "->" + end;
        }
    }

// 简单测一下
publicstaticvoidmain(String[] args){
        MissingRanges mr = new MissingRanges();
int[] nums = {0, 1, 2, 5, 6, 10};
int lower = 0;
int upper = 9;
        List<String> ans = mr.findMissingRanges(nums, lower, upper);
        System.out.println(ans); // [3->4, 7->9]
    }
}

你大概盯着 for (int i = 0; i <= nums.length; i++) 这一行会有点别扭,对吧,按平时习惯应该是 < nums.length。这里特意写成 <=,就是为了最后那一次把“upper + 1 当作一个假的元素”塞进来,这样头尾的处理逻辑就统一了,不用单写一个“处理尾区间”的分支。

时间复杂度也好说,一趟扫描,O(n);额外空间就结果列表,多算不上啥。

这种题在业务里其实还挺常见的:

  • 比如你要查日志里遗漏的订单号段;
  • 又或者做定时任务调度,发现某些分钟的任务从来没触发过; 本质都可以抽成“给我现有的一些点,以及理论上完整的范围,把没出现的那几段告诉我”。

你可以先照着这个写一遍,自己再加两三个极端用例测测:比如 nums 为空、nums 覆盖整个区间、或者只有一个元素那种。写完跑顺了,差不多这道题就稳了,嗯,我去泡个茶,你要是想扩展成返回 int[] 区间也很容易改。

-END-

我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html

最后给大家分享一份不错的副业资料,点击下方公众号,回复关键字: 副业 领,也可以链接我微信:hls404