面灵AI→

千里科技笔试:两道编程题都没写出来,最小区间与复制粘贴

轮次
笔试
时间
2026-10
来源
牛客网

《面试题目》

  1. 选择题部分考了哪些内容?
  2. 编程题一:最小区间——题意与解法是什么?
  3. 编程题二:复制粘贴——题意与解法是什么?
  4. 两道题都没写出来时,问题出在哪里(时间分配、题型熟悉度,还是实现卡住)?

《参考解析》

「最小区间」这类题的常见两种形态。 一种是 LeetCode 632 那类:给定 k 个升序列表,找一个最小区间 [a,b],使得每个列表里至少有一个数落在区间内——解法是多路归并 + 滑动窗口:用一个小顶堆维护 k 个列表当前指针的最小值、同时记录这 k 个元素的最大值,当前窗口宽度就是 max − min,每次弹出最小元素、把该列表的下一个数推进堆,重复到某个列表耗尽,全程取最小宽度。另一种是「最小覆盖子串」类:在字符串 s 里找覆盖 t 所有字符的最短窗口——解法是双指针滑动窗口 + 计数数组,右指针扩张到满足条件、左指针收缩到不满足,过程中记录最小长度。遇到题名模糊时,先读输入输出样例判断是哪一类,再看数据范围决定复杂度(n ≤ 1e5 基本要求 O(n log n) 或 O(n))。

「复制粘贴」基本就是 2 Keys Keyboard 那一类。 初始屏幕上只有一个字符 A,每次操作只能「复制全部」或「粘贴」,问得到 n 个 A 最少需要几步。结论是质因数分解:把 n 拆成质因数之积,答案就是所有质因数之和。直觉解释:一次「复制 + 若干次粘贴」相当于把当前长度乘以一个因子 k,代价是 1 + (k−1) = k 步,所以总代价是各因子之和;而因子取得越小(质数)越省,因此最优分解就是质因数分解。代码只有几行:

def min_steps(n: int) -> int:
    ans, d = 0, 2
    while d * d <= n:
        while n % d == 0:
            ans += d
            n //= d
        d += 1
    if n > 1:
        ans += n
    return ans if n > 1 else ans

更严谨的写法是外层 while n > 1,找到因子就累加并除尽,最后剩下的质数也累加。要注意 n=1 时答案是 0(不用任何操作),这是最常见的边界错误。如果题目是「可以复制任意长度的子串」的变体,就变成区间 DP 或另一种贪心,读题时必须确认「复制」是复制全部还是可选中部分。

两道都没写出来,问题通常不在算法。 从描述看是「时间不够 + 状态崩了」。可操作的改进:① 开考先花 2 分钟扫一遍所有题,按「有把握 / 有思路 / 完全不会」排序,先拿稳的分;② 每题先写暴力版本拿部分分(很多笔试按测试点给分),再优化;③ 卡住超过 15 分钟就切题,回头再看往往能想通;④ 平时练习时用计时器模拟,把「读题 → 建模 → 写 → 测样例 → 造边界」固定成流程,减少临场决策成本。笔试考的不只是会不会,还有「在有限时间里拿到最多分」的策略。