携程9.20笔试：两道编程题加AI coding复盘

《面试题目》

1. AI coding 题（作者记录到 8735，提到是从 8710 一步步调试过来的，原文未展开题意）。
2. 编程题一：求数组中任意三个连续数字中的「最大值 − 最小值」是否小于给定值，选出的区间不可有重叠位置。作者用 DP 通过 83%，复盘认为贪心才是最优解，DP 时没有把所有前置状态都考虑进去。
3. 编程题二：求从第一列跳到第 m 列的最小移动次数，每次可以跳 a 列以下，或者跳 b 列以上（a < b）。作者分类讨论了 5 种情况，100% 通过。

《参考解析》

三连窗口极差 + 不重叠选择：分两步。第一步用滑动窗口或单调队列预处理每个位置 i 的三元窗口 (i, i+1, i+2) 的极差，标记该窗口是否可选，O(n)。第二步是在数轴上「选最多互不重叠的区间」，这是经典区间调度问题，最优解是贪心：把所有可选窗口按右端点排序，能放就放（每次选结束最早的，给后面留最多空间）。作者用 DP 只过 83%，原因通常是把状态定义成「以 i 结尾的窗口选不选」，转移里只回看了 i−1 而漏掉了更早的状态——正确的转移必须包含「不选当前位置」这一支，f[i] = max(f[i-1], f[i-3] + 1)（按窗口右端点下标定义 f），或者干脆按区间而不是下标定义状态。另一个易错点是题目到底问「最多能选几个」还是「是否存在可行选法」，边界处理不同。

跳列最小步数（每步 ≤ a 或 ≥ b）：设目标距离为 d = m − 1，每步移动 x 需满足 x ≤ a 或 x ≥ b，中间那段 (a, b) 是不可用区间。分情况讨论：① d ≤ a 或 d ≥ b 时一步到位；② 只能用大步（a 太小、小步走不完）时 ceil(d / b)，再看最后剩余的余数是否能由一次小步或一次大步补齐——若余数落在 (a, b) 内，说明最后一步不合法，需要把某一步大步拆成「大步 + 小步」或整体多走一步；③ 只能用小幅步进时 ceil(d / a)，但要检查过程中不会被迫落在需要大跳的位置；④ 混合时贪心策略是「尽量用大步，最后用小步收尾」，先枚举使用大步的次数 k（k 要从 ceil((d − a) / b) 附近开始试，因为小步总量最多 a），判断剩余距离 d − k·b 是否 ≤ a 或恰好能用 k 次以内的移动走完，取最小的移动次数；⑤ 无解情况（比如 a = 0 且 d < b）。这类题的通用结论是「能用数学公式直接算就别 BFS」，因为 m 可能非常大，O(m) 的搜索会超时。

AI coding 环节怎么拿分：携程这部分的形态是在给定代码或需求上做多轮交互式修改，考察的是「需求描述是否清晰 + 能不能读懂 AI 的输出并逐步调试」。实战建议：先用一句话让模型复述需求确认理解一致；要求它逐步修改而不是整体重写，避免把已经跑通的部分改坏；每改一步立刻跑一遍样例；报错信息原样贴回去，别自己转述；最后自己通读一遍边界（空输入、单元素、极值、多组输入）。由于这类题按通过的测试点累计给分，先保证简单用例全过，再去啃难点。

笔试节奏：携程这套是「2 道编程 + 1 道 AI coding」，时间分配上建议先扫一遍全卷，把最有把握的题先拿满，再回头处理边界复杂的题。作者第一题用 DP 拿到 83% 就是因为方法选错——复盘时应该刻意训练「看到『不重叠区间选择』立刻想到按右端点贪心」的条件反射。