如何实现返回找到相邻重复数字对所需最少乘法次数的算法？

核心思路 #

• 该问题要求最少乘法次数，采用广度优先搜索（BFS）实现最优解查找，BFS的每一层遍历对应一次乘法操作，首次命中终止条件时的层数就是最少执行次数
• 每个搜索节点存储三类信息：当前用于乘法计算的数字、累计拼接的数字列表、已完成的乘法次数
• 引入已访问数字集合避免重复计算，防止出现无限循环
• 每次生成新数字后优先校验两类相邻重复场景：原列表末尾数字与新数字首位是否重复、新数字内部是否存在相邻重复数字，任意场景命中即可直接返回结果

代码实现（Python） #

from collections import deque

def ArrayChallenge(num):
    # 拆分初始数字为列表
    initial_digits = [int(c) for c in str(num)]
    # 校验初始列表是否存在相邻重复（如输入11直接返回0）
    for i in range(len(initial_digits) - 1):
        if initial_digits[i] == initial_digits[i+1]:
            return 0
    # 初始化BFS队列：(当前计算用数字, 累计数字列表, 已执行次数)
    queue = deque()
    queue.append((num, initial_digits, 0))
    # 已访问数字集合，去重避免循环
    visited = set()
    visited.add(num)
    
    while queue:
        current_num, current_list, step = queue.popleft()
        # 获取当前数字的所有不重复数位，减少无效计算
        available_digits = set([int(c) for c in str(current_num)])
        
        for d in available_digits:
            new_num = current_num * d
            if new_num in visited:
                continue
            visited.add(new_num)
            # 拆分新数字数位
            new_digits = [int(c) for c in str(new_num)]
            # 校验第一种重复场景：原列表末尾和新数字首位重复
            if current_list[-1] == new_digits[0]:
                return step + 1
            # 校验第二种重复场景：新数字内部存在相邻重复
            for i in range(len(new_digits) - 1):
                if new_digits[i] == new_digits[i+1]:
                    return step + 1
            # 无重复则加入队列进入下一轮搜索
            new_list = current_list + new_digits
            queue.append((new_num, new_list, step + 1))

测试用例验证 #

• 输入ArrayChallenge(134)，返回结果1，匹配示例1
• 输入ArrayChallenge(46)，返回结果2，匹配示例2

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