2025-06-24：使两个整数相等的数位操作。用go语言，给定两个整数 n 和 m，它们的位数相同。
你可以对 n 执行任意次数的操作，每次操作都是以下两种之一：

1. 1. 选择 n 中的任意一位，且该位数字不为 9，将该位数字加 1。
2. 2. 选择 n 中的任意一位，且该位数字不为 0，将该位数字减 1。

在整个操作过程中，数字 n 的值不能是质数。也就是说，初始的 n 以及每次操作完成后的 n 都不能是质数。

操作的总代价定义为 n 变化过程中所有中间值（包括初始和最终值）的和。

请你计算出，将 n 通过上述操作变为 m 所需的最小代价。如果无法完成转换，则返回 -1。

1 <= n, m < 10000。

n 和 m 包含的数位数目相同。

输入：n = 10, m = 12。

输出：85。

解释：

我们执行以下操作：

增加第一个数位，得到 n = 20 。

增加第二个数位，得到 n = 21 。

增加第二个数位，得到 n = 22 。

减少第一个数位，得到 n = 12 。

题目来自力扣3377。

解决思路

1. 1. 预处理质数：使用埃拉托斯特尼筛法（埃氏筛）预处理所有小于 10000 的数，标记是否为合数（或 1）。这样可以在 O(1) 时间内判断一个数是否是质数。
2. 2. Dijkstra 算法：将问题建模为图的最短路径问题。每个数字是一个节点，边表示通过一次操作从一个数字转移到另一个数字的代价。使用优先队列（最小堆）来找到从 n 到 m 的最小代价路径。
3. o 节点：表示当前的数字。
4. o 边：表示通过一次操作（增加或减少某一位）转移到另一个数字的代价。
5. o 优先级：当前的总代价（即路径上所有数字的和）。
6. 3. 初始化：从 n 开始，初始代价为 n。
7. 4. 遍历：每次从堆中取出当前总代价最小的数字，尝试通过改变其每一位的数字生成新的数字。如果新数字是合数（或 1）且新总代价更小，则将其加入堆中。
8. 5. 终止条件：当取出 m 时，返回当前的总代价；如果堆为空且未找到 m，则返回 -1。

详细步骤

1. 1. 预处理质数：
2. o 初始化一个布尔数组 np，大小为 10000，np[i] 为 true 表示 i 是合数或 1。
3. o 标记 1 为 true（非质数）。
4. o 对于每个数 i 从 2 开始，如果 i 是质数（np[i] 为 false），则标记其所有倍数为合数。
5. 2. 检查初始条件：
6. o 如果 n 或 m 是质数，直接返回 -1。
7. 3. 初始化 Dijkstra：
8. o 创建一个距离数组 dis，大小为 10^len(n)（即所有可能的数字范围），初始值为无穷大。
9. o dis[n] 初始化为 n（初始代价）。
10. o 将 (n, n) 加入最小堆，表示从 n 出发，当前总代价为 n。
11. 4. Dijkstra 主循环：
12. o 从堆中取出当前总代价最小的数字 x。
13. o 如果 x == m，返回当前总代价。
14. o 否则，尝试改变 x 的每一位：
15. o 对于每一位的数字 d，如果 d > 0，可以减 1 生成新数字 y。
16. o 如果 d < 9，可以加 1 生成新数字 y。
17. o 计算新总代价 newD = disX + y（disX 是 x 的当前总代价）。
18. o 如果 y 是合数（或 1）且 newD < dis[y]，更新 dis[y] 并将 (newD, y) 加入堆。
19. 5. 终止：
20. o 如果堆为空且未找到 m，返回 -1。

时间复杂度和空间复杂度

• o 时间复杂度：
• o 预处理质数：O(mx log log mx) = O(10000 log log 10000) ≈ O(10000 * 3) = O(30000)。
• o Dijkstra 算法：最坏情况下需要遍历所有可能的数字（最多 10000 个），每次操作需要处理数字的每一位（最多 4 位），堆操作的时间复杂度为 O(log V)。因此总时间复杂度为 O(V * log V * D)，其中 V = 10000，D = 4，即 O(40000 log 10000) ≈ O(40000 * 13) = O(520000)。
• o 综合：O(30000 + 520000) ≈ O(550000)。
• o 空间复杂度：
• o np 数组：O(10000)。
• o dis 数组：O(10000)。
• o 堆：最坏情况下存储所有数字，O(10000)。
• o 综合：O(10000)。

总结

• o 时间复杂度：O(V * log V * D)，其中 V 是数字范围（10000），D 是数字位数（最多 4）。
• o 空间复杂度：O(V)，主要用于存储距离和堆。

Go完整代码如下：

.

package main

import (
    "container/heap"
    "fmt"
    "math"
    "strconv"
)

const mx = 10000

var np = [mx]bool{1: true}

func init() {
    // 埃氏筛，标记每个数是否为合数（或者 1）
    for i := 2; i < mx; i++ {
        if !np[i] {
            for j := i * i; j < mx; j += i {
                np[j] = true// 合数
            }
        }
    }
}

func minOperations(n, m int)int {
    if !np[n] || !np[m] {
        return-1
    }
    lenN := len(strconv.Itoa(n))
    dis := make([]int, int(math.Pow10(lenN)))
    for i := range dis {
        dis[i] = math.MaxInt
    }
    dis[n] = n
    h := hp{{n, n}}
    forlen(h) > 0 {
        top := heap.Pop(&h).(pair)
        x := top.x
        if x == m {
            return top.dis
        }
        disX := top.dis
        if disX > dis[x] {
            continue
        }
        pow10 := 1
        for v := x; v > 0; v /= 10 {
            d := v % 10
            if d > 0 { // 减少
                y := x - pow10
                newD := disX + y
                if np[y] && newD < dis[y] {
                    dis[y] = newD
                    heap.Push(&h, pair{newD, y})
                }
            }
            if d < 9 { // 增加
                y := x + pow10
                newD := disX + y
                if np[y] && newD < dis[y] {
                    dis[y] = newD
                    heap.Push(&h, pair{newD, y})
                }
            }
            pow10 *= 10
        }
    }
    return-1
}

type pair struct{ dis, x int }
type hp []pair

func (h hp) Len() int           { returnlen(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() (v any)      { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }

func main() {
    n := 10
    m := 12
    fmt.Println(minOperations(n, m))
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

import heapq
import math

MAX = 10000

# np[i] == True 表示 i 是合数或 1，不是质数
np = [False] * MAX
np[1] = True
for i in range(2, int(math.sqrt(MAX)) + 1):
    if not np[i]:
        for j in range(i * i, MAX, i):
            np[j] = True

def min_operations(n: int, m: int) -> int:
    if not np[n] or not np[m]:
        return-1
    
    len_n = len(str(n))
    limit = 10 ** len_n
    dis = [math.inf] * limit
    dis[n] = n
    
    heap = [(n, n)]  # (dist, x)
    while heap:
        dist_x, x = heapq.heappop(heap)
        if x == m:
            return dist_x
        if dist_x > dis[x]:
            continue
        
        pow10 = 1
        v = x
        digits = []
        for _ in range(len_n):
            digits.append(v % 10)
            v //= 10
        
        for i, d in enumerate(digits):
            if d > 0:
                y = x - pow10
                if y < limit and np[y]:
                    new_dist = dist_x + y
                    if new_dist < dis[y]:
                        dis[y] = new_dist
                        heapq.heappush(heap, (new_dist, y))
            if d < 9:
                y = x + pow10
                if y < limit and np[y]:
                    new_dist = dist_x + y
                    if new_dist < dis[y]:
                        dis[y] = new_dist
                        heapq.heappush(heap, (new_dist, y))
            pow10 *= 10
    return-1

if __name__ == "__main__":
    n = 10
    m = 12
    print(min_operations(n, m))

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·