LeetCode风格Python题：带移动限制的键盘最接近数字求解

题目重述 #

给定整数n（1<n<200），仅允许在标准电话键盘上向下或向右移动，且必须从输入数字的第一个数字开始按压。要求输出符合移动规则的、与原数最接近的数字：

• 示例1：输入"180"，输出"180"（从1可向下到8，8可向下到0，路径合法）
• 示例2：输入"98"，输出"99"（9无法向右或向下移动到8，只能选择保持9，得到最接近的99）

当前代码的核心问题 #

1. 未建立数字与键盘位置的映射：直接判断数字是否在某列表，无法准确判断移动合法性，比如8的下方是0，但右侧没有数字，这种逻辑不能靠硬编码数字列表解决。
2. 循环与变量逻辑混乱：check变量未初始化就使用，嵌套循环层级过多，生成number的逻辑完全不符合逐位处理的需求。
3. 未处理核心需求：没有实现“当某一位无法合法移动时，生成最接近的合法数字”的逻辑，只是零散处理个别数字的情况。

核心解题思路 #

步骤1：建立键盘坐标映射 #

先把每个数字（排除*和#）对应到键盘上的行、列坐标，方便快速判断移动关系：

keypad_map = {
    1: (0,0), 2: (0,1), 3: (0,2),
    4: (1,0), 5: (1,1), 6: (1,2),
    7: (2,0), 8: (2,1), 9: (2,2),
    0: (3,1)
}

步骤2：判断合法移动 #

写一个辅助逻辑，判断从数字curr是否可以合法移动到next_num：

• 合法移动的条件：next_num的行号 ≥ curr的行号，且列号 ≥ curr的列号（因为只能向右或向下）
• 注意：必须对应键盘实际位置，比如9的坐标是(2,2)，下方是#、右侧无数字，所以9只能停在原地，无法移动到其他数字。

步骤3：逐位处理输入数字 #

将输入转为字符串，逐位遍历：

1. 从第一位开始，记录当前的键盘位置。
2. 对每一位目标数字，检查是否可以从当前位置合法移动过去：
   • 如果可以，更新当前位置为该数字的坐标，保留该位数字。
   • 如果不可以，找到所有能从当前位置合法移动到的数字，选择其中与目标数字最接近的那个；如果没有可移动的数字（比如当前在9），则只能保留当前数字。
3. 处理完所有位后，得到一个合法数字。

步骤4：确认最优结果 #

如果某一步有多个接近的候选数字，计算每个候选与原数的差值绝对值，选择最小的那个；若差值相同，选较大的数字（保证更接近原数的同时符合规则）。

代码重构示例（核心逻辑） #

def closest_valid_number(num_str):
    # 数字到键盘坐标的映射
    keypad_map = {
        1: (0,0), 2: (0,1), 3: (0,2),
        4: (1,0), 5: (1,1), 6: (1,2),
        7: (2,0), 8: (2,1), 9: (2,2),
        0: (3,1)
    }
    # 坐标到数字的反向映射，方便查找可移动的数字
    coord_to_num = {(r,c): num for num, (r,c) in keypad_map.items()}
    
    result = []
    # 初始化当前位置为第一个数字的坐标
    current_coord = keypad_map[int(num_str[0])]
    result.append(num_str[0])
    
    for i in range(1, len(num_str)):
        target_num = int(num_str[i])
        target_coord = keypad_map[target_num]
        # 检查是否可以合法移动
        if target_coord[0] >= current_coord[0] and target_coord[1] >= current_coord[1]:
            result.append(num_str[i])
            current_coord = target_coord
        else:
            # 收集所有可移动到的候选数字
            candidates = []
            for r in range(current_coord[0], 4):
                for c in range(current_coord[1], 3):
                    if (r,c) in coord_to_num:
                        candidates.append(coord_to_num[(r,c)])
            # 按与目标数字的差值排序，差值相同选更大的数字
            candidates.sort(key=lambda x: (abs(x - target_num), -x))
            best_num = candidates[0]
            result.append(str(best_num))
            current_coord = keypad_map[best_num]
    
    return ''.join(result)

# 测试示例
print(closest_valid_number("180"))  # 输出180
print(closest_valid_number("98"))   # 输出99

这类问题的思考方法建议 #

• 明确约束条件：把题目中的规则转化为可量化的逻辑（比如“向下/向右”转化为坐标的行≥、列≥），避免靠直觉硬编码。
• 建立辅助数据结构：用映射表（字典）关联数字和位置，大幅简化后续判断逻辑，不要直接遍历键盘列表查找数字。
• 分阶段处理：先解决“合法移动判断”，再解决“无法移动时的候选生成”，最后处理“最优结果选择”，不要试图一步到位写所有逻辑。
• 测试边界案例：比如输入以9开头、以0结尾、长度为2/3的数字，验证逻辑是否正确，边界案例往往能暴露逻辑漏洞。

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