调试程序行号计算面试题求助：代码仅通过70%测试用例

题目背景 #

我在一道面试题上卡壳了，至今没能完全解决。题目内容如下：

你正在调试一个共length行的程序，有两个数组：actions和breakpoints：

• actions数组只有"next"或"continue"两种值；
• breakpoints数组存的是断点行号，范围是1<=breakpoints[i]<=length。

核心规则 #

• 执行"next"：跳转到下一行；
• 执行"continue"：
  • 跳转到大于当前行号的下一个断点；
  • 要是没剩余断点了，直接返回length；
• 初始行号：默认是1，但若breakpoints非空，就设为breakpoints[0]；
• 所有actions执行完后，返回当前行号。

我的尝试代码 #

面试后我梳理思路写了下面这段代码，但只能过大概70%的测试用例：

# Initialize line_number to 1
line_number = 1

# If there are no breakpoints or actions, return 1
if len(actions) == 0 and len(breakpoints) == 0:
    return line_number

# If there are no actions, but there are breakpoints, return the first breakpoint
if len(actions) == 0 and len(breakpoints) > 0:
    return breakpoints[0]

# If there are actions, but not breakpoints, make sure actions are all "next", else, return length
if len(actions) > 0 and len(breakpoints) == 0:
    if "continue" in actions:
        return length
    else:
        for i in actions:
            if i == "next":
                line_number += 1
        return line_number

# If there are actions and breakpoints...
while (len(actions) > 0):
    # If the line_number exceeds the length, return length
    if line_number >= length:
        return length

    # While the action is "continue"...
    while actions[0] == "continue":
        # If the length of breakpoint is greater than 0
        if len(breakpoints) == 0:
            return length
        
        # If the length of breakpoints is greater than 0...
        if len(breakpoints) > 0:
            # If the next breakpoint is greater than the line_number, then set line_number to the next breakpoint
            if breakpoints[0] > line_number:
                line_number = breakpoints[0]
                breakpoints.pop(0)
                actions.pop(0)
            
            # If the next breakpoint is less than the line_number...
            else:
                # Pop until the next breakpoint is greater than the line_number or the length of breakpoints is 0.
                while breakpoints[0] <= line_number:
                    if len(breakpoints) == 0:
                        return length
                    breakpoints.pop(0)
                line_number = breakpoints[0]
                breakpoints.pop(0)
                actions.pop(0)

    # If the action is "next", then set line_number to the next line
    while actions[0] == "next":
        line_number += 1
        actions.pop(0)

return(line_number)

原代码里的几个坑 #

1. 初始行号逻辑错误：原代码先把line_number设为1，但只有在没有actions的时候才返回breakpoints[0]；如果有actions，初始行号还是1，完全违反题目“breakpoints非空时初始化为breakpoints[0]”的要求。
2. 默认断点数组有序：题目没说breakpoints是排好序的！比如breakpoints = [5,2]，原代码直接取第一个元素处理，后续找下一个断点的逻辑全错。
3. continue处理的循环漏洞：在清理小于等于当前行的断点时，pop后如果breakpoints变空，应该直接返回length，但原代码里的循环可能没及时触发返回，导致后续报错。
4. next操作未限制行号：执行next时line_number可能超过length，这时候应该直接返回，不用再处理剩下的actions。
5. 冗余判断与低效操作：比如重复判断breakpoints是否为空，还有用pop(0)操作列表（时间复杂度O(n)），既冗余又低效。

优化后的代码 #

def debug_program(length, actions, breakpoints):
    # 初始化行号
    line_number = breakpoints[0] if breakpoints else 1
    # 对断点去重并排序，方便快速查找下一个有效断点
    sorted_breakpoints = sorted(list(set(breakpoints))) if breakpoints else []
    
    import bisect

    for action in actions:
        # 提前判断行号是否超限，直接返回
        if line_number >= length:
            return length
        
        if action == "next":
            line_number += 1
            # next后直接检查是否超限
            if line_number > length:
                return length
        elif action == "continue":
            if not sorted_breakpoints:
                return length
            # 用bisect找到第一个大于当前行号的断点位置
            idx = bisect.bisect_right(sorted_breakpoints, line_number)
            if idx >= len(sorted_breakpoints):
                return length
            # 更新行号并移除该断点（已到达过，后续不会再跳）
            line_number = sorted_breakpoints[idx]
            sorted_breakpoints.pop(idx)
    
    # 所有actions处理完，返回不超过length的当前行号
    return min(line_number, length)

优化思路说明 #

1. 修正初始行号：直接用三元表达式设置初始行号，逻辑清晰且符合题目要求。
2. 断点预处理：对断点去重+排序，解决原代码依赖断点有序的问题，同时避免重复处理同一个断点。
3. 高效查找断点：用bisect模块的bisect_right快速定位第一个大于当前行号的断点，比手动循环高效得多（时间复杂度O(logn) vs O(n)）。
4. 及时终止逻辑：在每个action处理前、next操作后都检查行号是否超限，符合题目规则，避免无效操作。
5. 简洁遍历actions：用for循环遍历actions，避免原代码中pop(0)的低效操作，逻辑更直观。

内容的提问来源于stack exchange，提问作者Mr.Squid