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

福大大架构师每日一题

发布于 2025-06-24 10:02:59

1730

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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

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

详细步骤

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

时间复杂度和空间复杂度

• 时间复杂度：
- • 预处理质数：O(mx log log mx) = O(10000 log log 10000) ≈ O(10000 * 3) = O(30000)。
- • 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(30000 + 520000) ≈ O(550000)。
• 空间复杂度：
- • np 数组：O(10000)。
- • dis 数组：O(10000)。
- • 堆：最坏情况下存储所有数字，O(10000)。
- • 综合：O(10000)。

总结

• 时间复杂度：O(V * log V * D)，其中 V 是数字范围（10000），D 是数字位数（最多 4）。
• 空间复杂度：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))