#722. 删除注释

• LeetCode：原题1
• 难度：中等
• 归类：数组（数组、字符串）
• 主解法：分情况讨论

#先给结论

这道题的核心是把题目的操作规则直接转成确定的状态机，并保证每一步只修改规定状态。面试时先说清楚“状态表示什么、为什么能排除其他候选、何时更新答案”，再写代码；只报出“用 模拟”还不足以证明理解。

#题目描述

题目要求完成“删除注释”。输入包括 source（string[]），需要返回 list<string>。完整限制以原题为准，解题时重点利用这些特征：数组、字符串。

示例：

输入：: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
输出：: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]
解释：: 示例代码可以编排成这样:
/*Test program */
int main()
{
// variable declaration
int a, b, c;
/* This is a test
multiline
comment for
testing */
a = b + c;
}
第 1 行和第 6-9 行的字符串 /* 表示块注释。第 4 行的字符串 // 表示行注释。
编排后:
int main()
{
int a, b, c;
a = b + c;
}

#题型判断

从题目标签和参考实现看，本题采用 模拟。判断依据是：把题目的操作规则直接转成确定的状态机，并保证每一步只修改规定状态。

#核心思路

变量保存当前下标、方向、边界或累计结果，完整描述下一步该做什么。整个过程保持一个关键不变量：每轮开始时，已经处理的部分符合题意，未处理部分仍保持原始语义。因此每一步被排除或已经处理的状态都无需回退，不会漏掉最终答案。

#示例步骤图解

#变量与区间含义

• 主状态：变量保存当前下标、方向、边界或累计结果，完整描述下一步该做什么。
• 候选区间采用代码中的实际边界定义；若代码使用 left <= right，它表示闭区间 [left, right]；若使用 left < right，则必须结合边界赋值判断是闭区间还是左闭右开区间。
• ans 或返回变量只保存已经被证明有效的候选，不把未经验证的中间状态当作答案。

#推进规则

按规则读取当前状态、生成下一状态，并在越界或完成条件出现时停止。移动边界前要能说明被跳过部分为什么不可能更优，这是本题正确性的核心，而不是模板本身。

#边界条件与易错点

• 空输入、只有一个元素，以及答案位于首尾位置时，循环仍应正常结束。
• 最容易错在状态更新顺序、边界少一位，以及修改输入后影响后续读取。
• JavaScript 中下标计算优先使用 Math.floor；涉及大整数时要检查是否超过 Number.MAX_SAFE_INTEGER。

#代码实现

参考实现来源：JoshCrozier/leetcode-javascript，按本文结构重新整理；原项目采用 MIT License。

#JavaScript 实现

/**
 * @param {string[]} source
 * @return {string[]}
 */
var removeComments = function(source) {
  return source.join('\n').replace(/\/\*.*?\*\/|\/\/[^\n]+/gs, '').split(/\n/).filter(Boolean);
};

#代码与思路对照

读代码时应把每个判断还原成“它排除了什么状态或完成了哪次转移”，而不是只记变量名。

#复杂度分析

• 时间复杂度：O(L)。
• 空间复杂度：O(L)，其中 L 是源代码的总长度。

复杂度必须按“状态数量 × 每个状态处理成本”分析；如果存在排序、堆操作、递归深度或结果数组，需要单独计入，不能只看最外层循环。

#面试官递进追问

#1. 为什么本题适合 模拟？

因为把题目的操作规则直接转成确定的状态机，并保证每一步只修改规定状态。 为什么问： 检查你是在识别性质，还是只凭题号背模板。回答要抓住可被利用的单调性、重复子问题或数据结构约束。

#2. 代码维护的核心状态是什么？

变量保存当前下标、方向、边界或累计结果，完整描述下一步该做什么。 为什么问： 状态定义决定代码是否可证明。回答时要让每个变量都能对应到题意。

#3. 这个实现依赖什么不变量？

每轮开始时，已经处理的部分符合题意，未处理部分仍保持原始语义。 为什么问： 不变量比逐行复述代码更能证明理解，回答要说明它在初始化、推进和结束时都成立。

#4. 为什么这样推进不会漏掉答案？

按规则读取当前状态、生成下一状态，并在越界或完成条件出现时停止，被跳过的状态已经由题目性质证明不可能更优或已经处理完成。 为什么问： 检查正确性证明，重点不是“指针这样写”，而是“为什么可以排除”。

#5. 最危险的边界是什么？

最容易错在状态更新顺序、边界少一位，以及修改输入后影响后续读取。 为什么问： 检查代码能否一次通过，回答要给出具体失败场景而不是只说“注意边界”。

#6. 复杂度还能优化吗？

先看瓶颈来自状态数量、每次转移成本还是辅助结构操作；只有其中一项能被减少时，复杂度才可能继续下降。 为什么问： 检查你能否从成本组成出发优化，而不是机械背最优复杂度。

#7. 如果输入规模扩大或数据改成流式，方案怎么变？

要判断当前算法是否需要随机访问全部输入；若只依赖有限历史状态，可以做滚动或在线维护，否则需要分块、外存或调整数据结构。 为什么问： 检查算法理解能否迁移到工程约束。

#8. 有哪些替代解法，如何取舍？

可以从暴力枚举开始，再比较排序、哈希、搜索或动态规划等方案；取舍标准是时间、空间、是否修改输入和实现复杂度。 为什么问： 检查横向比较能力。回答要说明替代方案为什么更慢或在什么条件下更合适。

#常见错误回答

• “这题套 模拟 模板即可”：只有结论，没有说明题目性质和排除依据。
• 逐行朗读代码：没有建立状态、不变量和正确性因果链。
• 只报 O(n) 或 O(n²)：没有解释每个状态被访问多少次，也容易漏掉排序或辅助结构。
• 把示例能跑通当成证明：示例只能帮助检查，不能覆盖重复值、空输入和极端边界。

#可迁移总结

• 核心关键词：模拟、状态定义、不变量、推进规则、边界。
• 一句话本质：把题目的操作规则直接转成确定的状态机，并保证每一步只修改规定状态。
• 思考链路：识别题目性质 → 定义状态 → 证明推进安全 → 确定更新时机 → 检查边界与复杂度。
• 1 分钟回答：说清题型、核心状态、推进规则和复杂度。
• 3 分钟回答：补上正确性依据、示例和两个关键边界。
• 10 分钟回答：写出代码，并比较替代方案、空间优化和工程限制。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 不看代码，你能用一句话说出本题的不变量吗？

2. 如果把示例中的重复值、空输入或边界值换掉，哪一行代码最先受到影响？

3. 不改变正确性的前提下，你能写出一种替代方案并比较复杂度吗？