Flexible List Cleaner优化：求更高效的魔方操作列表清理方案

核心思路：用栈结构一次遍历处理 #

原方案通过多次字符串替换实现，不仅代码冗长，还可能存在处理不彻底的问题（比如连续替换后新产生的可合并/抵消操作无法二次处理）。改用栈结构逐个处理操作，一次遍历即可完成所有规则的应用，效率更高且逻辑清晰。

实现代码 #

def clean_sol(sol):
    # 预定义所有操作到（方向，数值）的映射
    move_mapping = {}
    base_directions = ['U', 'D', 'R', 'L', 'F', 'B', 'Y', 'X', 'Z', 'M', 'E', 'S']
    for dir in base_directions:
        move_mapping[dir] = (dir, 1)
        move_mapping[f"{dir}'"] = (dir, -1)
        move_mapping[f"{dir}2"] = (dir, 2)
    
    # 将（方向，数值）转换回操作字符串的辅助函数
    def to_move(dir, val):
        if val == 1:
            return dir
        elif val == -1:
            return f"{dir}'"
        elif val == 2:
            return f"{dir}2"
    
    stack = []
    for move in sol:
        curr_dir, curr_val = move_mapping[move]
        if stack:
            top_dir, top_val = stack[-1]
            # 仅处理同方向的操作
            if curr_dir == top_dir:
                total = top_val + curr_val
                mod_total = total % 4
                if mod_total == 0:
                    # 总和为4的倍数，完全抵消，弹出栈顶
                    stack.pop()
                else:
                    # 合并后更新栈顶
                    stack.pop()
                    stack.append((curr_dir, mod_total))
            else:
                # 不同方向直接入栈
                stack.append((curr_dir, curr_val))
        else:
            # 栈为空时直接入栈
            stack.append((curr_dir, curr_val))
    
    # 将栈中元素转换为最终操作列表
    return [to_move(dir, val) for dir, val in stack]

规则对应说明 #

• 连续4个相同操作抵消：每个基础操作对应数值1，4次累加总和为4，模4等于0，直接弹出栈顶（抵消）。
• 操作与逆操作抵消：原操作（+1）与逆操作（-1）总和为0，模4等于0，弹出栈顶（抵消）。
• 连续2个相同操作合并为2倍操作：两个基础操作累加总和为2，转换为dir2格式。

测试示例 #

输入：

sol = ["U", "U'","U","R","R'", "R", "R", "R", "R","U'","U"]

调用clean_sol(sol)，输出：

['U']

与预期结果一致。

对比原方案的优势 #

• 效率更高：一次遍历完成所有处理，时间复杂度为O(n)，原方案多次字符串替换的时间复杂度更高（且可能需要多轮扫描）。
• 逻辑更严谨：自动处理替换后新产生的可合并/抵消操作（比如两个U2会被自动抵消为0），原方案无法覆盖此类场景。
• 代码更简洁：通过映射和栈逻辑减少重复代码，可读性更强。

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