1167. 【宽度优先搜索BFS】数字交换游戏

Question

(标准输入输出)
时间限制: 1 s 空间限制: 256 MB 具体限制

题目描述
小明已经是中学生了，他喜欢研究数字，觉得最漂亮的数就是整数了。一次小明写下一个M位的整数（无前导0），他想研究下面这个游戏：每次取其中两位交换，会得到一个新的整数,但不能有前导0出现，即第一位不能变成0。这样连续做K次，最后能得到的最大整数是多少？

输入
第一行：两个整数N（1<=N<=1000000）和K（1<=K<=10）

输出
只有一行，一个整数，表示变化后最大数，如果不能变换则输出-1

样例输入 复制
样例输入1
16375 1
样例输入2
432 1
样例输入3
90 4

样例输出 复制
样例输出1
76315
样例输出2
423
样例输出3
-1

Answer 1

让 “紫雾凌寒” 来帮你回答,本回答结合 DeepSeek

如果还有问题，请评论或点击头像私信，如果有帮助到您, 请关注、采纳、点赞

1. 关键点分析

• 这是一个关于数字交换游戏的问题，需要使用宽度优先搜索（BFS）来解决。
• 给定一个M位整数，要找到通过特定交换规则能得到的最小整数。
• 关键在于确定合法的交换规则，并利用BFS遍历所有可能的数字状态，找到最小的结果。

2. 解决方案

from collections import deque

def minNumberAfterSwaps(num):
    num_str = str(num)
    n = len(num_str)
    graph = {i: [] for i in range(n)}
    for i in range(n - 1):
        for j in range(i + 1, n):
            if num_str[i]!= num_str[j]:
                graph[i].append(j)
                graph[j].append(i)

    visited = set()
    queue = deque([(num_str, 0)])
    visited.add(num_str)
    while queue:
        current_num, step = queue.popleft()
        if step > 0:
            current_num = ''.join(sorted(current_num))
        if current_num[0]!= '0':
            return int(current_num)
        for i in graph[0]:
            new_num = list(current_num)
            new_num[0], new_num[i] = new_num[i], new_num[0]
            new_num_str = ''.join(new_num)
            if new_num_str not in visited:
                queue.append((new_num_str, step + 1))
                visited.add(new_num_str)

    return -1

你可以使用以下方式调用这个函数：

num = 1993
print(minNumberAfterSwaps(num))  

3. 多种解决方案及优缺点

• BFS 解决方案：
• 优点：能保证找到的是符合交换规则下的最小整数，通过逐层遍历所有可能状态，不会遗漏最优解。
• 缺点：时间复杂度较高，特别是对于数字位数较多的情况，因为需要遍历所有可能的交换状态。空间复杂度取决于队列中存储的状态数量，也可能较大。

4. 总结

通过BFS遍历所有可能的数字交换状态，利用图结构存储数字间的交换关系，在遍历过程中找到符合条件（无前导0且最小）的整数。如果遍历完所有状态仍未找到合适结果，则返回-1。

希望以上解答对您有所帮助。如果您有任何疑问，欢迎在评论区提出。