Medium
题目描述
给定两个由相同位数组成的整数 n 和 m。
你可以执行以下操作任意次数：
- 选择 n 中任意一个不是 9 的数字，将其增加 1。
- 选择 n 中任意一个不是 0 的数字，将其减少 1。
整数 n 在任何时候都不能是质数，包括其原始值和每次操作后的值。
变换的成本是 n 在所有执行的操作过程中所取的所有值的总和。
返回将 n 转换为 m 的最小成本。如果不可能，返回 -1。
示例 1：
输入：n = 10, m = 12
输出：85
解释：
我们执行以下操作：
- 增加第一个数字，现在 n = 20。
- 增加第二个数字，现在 n = 21。
- 增加第二个数字，现在 n = 22。
- 减少第一个数字，现在 n = 12。
示例 2：
输入：n = 4, m = 8
输出：-1
解释：
无法使 n 等于 m。
示例 3：
输入：n = 6, m = 2
输出：-1
解释：
由于 2 已经是质数，我们无法使 n 等于 m。
约束条件：
- 1 <= n, m < 10^4
- n 和 m 由相同的位数组成。
解题思路
这是一个经典的最短路径问题。我们需要将其建模为图论问题：
核心思路：
- 将每个非质数看作图中的节点
- 如果两个数可以通过一次操作相互转换，则在它们之间建立边
- 边的权重为目标数字的值
- 使用 Dijkstra 算法求从 n 到 m 的最短路径
具体步骤：
- 首先预处理所有可能的质数（使用埃拉托斯特尼筛法）
- 检查起点 n 和终点 m 是否为质数，如果是则直接返回 -1
- 对于每个非质数，生成其所有可能的邻居（通过增减各位数字）
- 使用优先队列实现 Dijkstra 算法，寻找最短路径
- 路径的成本是经过的所有节点值的总和
关键细节：
- 数字操作时需要保证不超出位数限制
- 每次变换后的数字都不能是质数
- 成本计算包含起始值 n
这种方法的时间复杂度主要取决于图的大小和 Dijkstra 算法的执行。
代码实现
class Solution {
public:
int minOperations(int n, int m) {
if (n == m) return n;
// 预处理质数
vector<bool> isPrime(10001, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= 10000; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= 10000; j += i) {
isPrime[j] = false;
}
}
}
if (isPrime[n] || isPrime[m]) return -1;
// Dijkstra算法
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> dist(10001, INT_MAX);
pq.push({n, n});
dist[n] = n;
while (!pq.empty()) {
auto [cost, curr] = pq.top();
pq.pop();
if (curr == m) return cost;
if (cost > dist[curr]) continue;
string s = to_string(curr);
// 尝试增加每一位
for (int i = 0; i < s.length(); i++) {
if (s[i] < '9') {
s[i]++;
int next = stoi(s);
if (!isPrime[next] && cost + next < dist[next]) {
dist[next] = cost + next;
pq.push({cost + next, next});
}
s[i]--;
}
}
// 尝试减少每一位
for (int i = 0; i < s.length(); i++) {
if (s[i] > '0' && (i > 0 || s[i] > '1')) {
s[i]--;
int next = stoi(s);
if (!isPrime[next] && cost + next < dist[next]) {
dist[next] = cost + next;
pq.push({cost + next, next});
}
s[i]++;
}
}
}
return -1;
}
};
class Solution:
def minOperations(self, n: int, m: int) -> int:
if n == m:
return n
# 预处理质数
is_prime = [True] * 10001
is_prime[0] = is_prime[1] = False
for i in range(2, int(10000**0.5) + 1):
if is_prime[i]:
for j in range(i * i, 10001, i):
is_prime[j] = False
if is_prime[n] or is_prime[m]:
return -1
# Dijkstra算法
import heapq
pq = [(n, n)]
dist = [float('inf')] * 10001
dist[n] = n
while pq:
cost, curr = heapq.heappop(pq)
if curr == m:
return cost
if cost > dist[curr]:
continue
s = list(str(curr))
# 尝试增加每一位
for i in range(len(s)):
if s[i] < '9':
s[i] = str(int(s[i]) + 1)
next_num = int(''.join(s))
if not is_prime[next_num] and cost + next_num < dist[next_num]:
dist[next_num] = cost + next_num
heapq.heappush(pq, (cost + next_num, next_num))
s[i] = str(int(s[i]) - 1)
# 尝试减少每一位
for i in range(len(s)):
if s[i] > '0' and (i > 0 or s[i] > '1'):
s[i] = str(int(s[i]) - 1)
next_num = int(''.join(s))
if not is_prime[next_num] and cost + next_num < dist[next_num]:
dist[next_num] = cost + next_num
heapq.heappush(pq, (cost + next_num, next_num))
s[i] = str(int(s[i]) + 1)
return -1
public class Solution {
public int MinOperations(int n, int m) {
if (n == m) return n;
// 预处理质数
bool[] isPrime = new bool[10001];
Array.Fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= 10000; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= 10000; j += i) {
isPrime[j] = false;
}
}
}
if (isPrime[n] || isPrime[m]) return -1;
// Dijkstra算法
var pq = new PriorityQueue<(int cost, int num), int>();
int[] dist = new int[10001];
Array.Fill(dist, int.MaxValue);
pq.Enqueue((n, n), n);
dist[n] = n;
while (pq.Count > 0) {
var (cost, curr) = pq.Dequeue();
if (curr == m) return cost;
if (cost > dist[curr]) continue;
char[] s = curr.ToString().ToCharArray();
// 尝试增加每一位
for (int i = 0; i < s.Length; i++) {
if (s[i] < '9') {
s[i]++;
int next = int.Parse(new string(s));
if (!isPrime[next] && cost + next < dist[next]) {
dist[next] = cost + next;
pq.Enqueue((cost + next, next), cost + next);
}
s[i]--;
}
}
// 尝试减少每一位
for (int i = 0; i < s.Length; i++) {
if (s[i] > '0' && (i > 0 || s[i] > '1')) {
s[i]--;
int next = int.Parse(new string(s));
if (!isPrime[next] && cost + next < dist[next]) {
dist[next] = cost + next;
pq.Enqueue((cost + next, next), cost + next);
}
s[i]++;
}
}
}
return -1;
}
}
var minOperations = function(n, m) {
function isPrime(num) {
if (num < 2) return false;
if (num === 2) return true;
if (num % 2 === 0) return false;
for (let i = 3; i * i <= num; i += 2) {
if (num % i === 0) return false;
}
return true;
}
if (isPrime(n) || isPrime(m)) return -1;
if (n === m) return n;
const visited = new Set();
const pq = [[n, n]]; // [current_number, cost]
while (pq.length > 0) {
pq.sort((a, b) => a[1] - b[1]);
const [curr, cost] = pq.shift();
if (curr === m) return cost;
if (visited.has(curr)) continue;
visited.add(curr);
const digits = curr.toString().split('').map(Number);
for (let i = 0; i < digits.length; i++) {
// Increase digit
if (digits[i] < 9) {
const newDigits = [...digits];
newDigits[i]++;
const newNum = parseInt(newDigits.join(''));
if (!isPrime(newNum) && !visited.has(newNum)) {
pq.push([newNum, cost + newNum]);
}
}
// Decrease digit
if (digits[i] > 0 && !(i === 0 && digits[i] === 1 && digits.length > 1)) {
const newDigits = [...digits];
newDigits[i]--;
const newNum = parseInt(newDigits.join(''));
if (!isPrime(newNum) && !visited.has(newNum)) {
pq.push([newNum, cost + newNum]);
}
}
}
}
return -1;
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(V log V + E)，其中 V 是所有可能的非质数个数（约 8000 个），E 是边的数量。每个数字最多有 O(d) 个邻居（d 为位数），所以 E ≈ O(V × d)。Dijkstra 算法的复杂度为 O((V + E) log V) |
| 空间复杂度 | O(V)，用于存储距离数组、质数标记数组和优先队列 |