带联动机制的密码锁最小旋转步数算法超时问题求助

我在做算法作业时遇到超时问题，已经不及格了，现在想找出问题所在并复盘代码，看看怎么优化避免超时，可能我的初始思路有问题。

题目内容 #

有一个带多个拨号盘的密码锁，每个拨号盘是环形结构，数字0-9依次排列：向下转数字减小，向上转数字增大（比如指向9时，向下转1步到8，向上转1步到0）。

保险箱特殊机制：转动一个拨号盘时，其右侧所有拨号盘会同步转动。

示例：初始状态[1,5,9,3,7]，密码[2,5,9,3,7]。向上转第一个拨号盘1步，所有拨号盘变为[2,6,0,4,8]；再向下转第二个拨号盘1步，仅索引2到4的拨号盘转动，最终变为[2,5,9,3,7]，总共2步完成匹配。

需求：计算将拨号盘旋转至匹配密码所需的最小步数。

参数：整数数组dials为拨号盘初始状态，password为密码序列，完成函数solution返回最小步数。

约束条件：

• 1 ≤ dials长度 = password长度 ≤ 100000
• 0 ≤ dials[i], password[i] ≤9
• dials[i]表示第i+1个拨号盘初始数字；password[i]表示密码第i+1位

我的代码 #

def solution(dials, password):
    moves = 0
    for i in range(len(dials)):
        diff = min(abs(password[i] - dials[i]), 10 - abs(password[i] - dials[i]))
        moves += diff
        if i != len(dials) - 1:
            dials[i+1:] = [(d + (password[i] - dials[i])) % 10 for d in dials[i+1:]]
    return moves

# example
dials1 = [1, 5, 9, 3, 7]
password1 = [2, 5, 9 ,3 ,7]
print(solution(dials1,password1)) # Output:2

问题所在 #

代码超时的核心原因是每次修改右侧拨号盘时都遍历了整个子数组。处理第i个拨号盘时，dials[i+1:] = [(d + ...) %10 for d in dials[i+1:]]这一步的时间复杂度是O(n)，整个循环下来总时间复杂度是O(n²)，当n达到1e5时，这种复杂度完全无法通过时间限制。

优化思路 #

不需要实际修改每个右侧拨号盘的数值，而是用一个变量记录累计的偏移量。因为每次转动第i个拨号盘时，右侧所有拨号盘的偏移量都会被叠加，我们只需要跟踪这个累计偏移，就能算出当前拨号盘的实际需要调整的差值。

具体逻辑：

• 维护变量offset，记录前面所有操作对当前拨号盘造成的累计偏移（初始为0）。
• 对于第i个拨号盘，计算它的实际当前值：current = (dials[i] + offset) % 10。
• 计算需要调整到密码值的最小步数：直接差值delta = password[i] - current，环形最小步数取min(abs(delta), 10 - abs(delta))，加到总步数里。
• 更新offset：转动当前拨号盘的操作会给右侧所有拨号盘带来delta的偏移，所以offset = (offset + delta) % 10。

优化后的代码 #

def solution(dials, password):
    moves = 0
    offset = 0
    n = len(dials)
    for i in range(n):
        current = (dials[i] + offset) % 10
        delta = password[i] - current
        # 计算最小步数
        step = min(abs(delta), 10 - abs(delta))
        moves += step
        # 更新累计偏移量
        offset = (offset + delta) % 10
    return moves

# 测试示例
dials1 = [1, 5, 9, 3, 7]
password1 = [2, 5, 9 ,3 ,7]
print(solution(dials1,password1)) # Output:2

复杂度分析 #

优化后的代码时间复杂度是O(n)，每个元素只遍历一次，没有嵌套循环，完全能处理n=1e5的情况。

内容的提问来源于stack exchange，提问作者jamie101112