转化数字的最小运算数
难度:
标签:
题目描述
代码结果
运行时间: 524 ms, 内存: 16.3 MB
/*
思路:
1. 使用广度优先搜索(BFS)来找到从start到goal的最短路径。
2. 每一步可以通过对x执行加、减、异或操作来生成新的状态。
3. 使用Stream来处理nums数组。
4. 使用一个队列来存储当前的状态和操作次数,并且使用一个布尔数组来记录访问过的状态以避免重复计算。
5. 当某个状态等于goal时,返回操作次数。
6. 如果队列为空且未找到goal,返回-1。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int minimumOperations(int[] nums, int start, int goal) {
Queue<int[]> queue = new LinkedList<>();
boolean[] visited = new boolean[1001];
queue.add(new int[]{start, 0});
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0], steps = current[1];
if (x == goal) return steps;
if (x < 0 || x > 1000 || visited[x]) continue;
visited[x] = true;
IntStream.of(nums).forEach(num -> {
queue.add(new int[]{x + num, steps + 1});
queue.add(new int[]{x - num, steps + 1});
queue.add(new int[]{x ^ num, steps + 1});
});
}
return -1;
}
}
解释
方法:
这个题解使用了广度优先搜索(BFS)来寻找将start转换为goal的最短路径。初始状态为(start, 0),其中0表示操作次数。然后,对于队列中的每个状态,分别尝试加、减和异或三种操作,并将得到的新状态添加到队列中(如果它们在合法范围内且未被访问过)。如果在任何时候,新状态等于goal,则返回当前操作数加1。如果队列变为空,说明无法到达goal,返回-1。
时间复杂度:
O(3^n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么算法中对0到1000之外的数值进行操作后就不能再进行其他操作?
▷🦆
在算法描述中提到,如果新状态等于goal,则返回当前操作数加1,这里的加1是指什么?
▷🦆
使用BFS进行搜索时,如何确保不会重复访问相同的状态?
▷🦆
在处理边界情况时,算法是如何确保在数值操作后仍然保持在0到1000的范围内?
▷