给你一个下标从 0 开始的整数数组 nums ，该数组由 互不相同 的数字组成。另给你两个整数 start 和 goal 。
整数 x 的值最开始设为 start ，你打算执行一些运算使 x 转化为 goal 。你可以对数字 x 重复执行下述运算：
如果 0 <= x <= 1000 ，那么，对于数组中的任一下标 i（0 <= i < nums.length），可以将 x 设为下述任一值：
x + nums[i]x - nums[i]x ^ nums[i]（按位异或 XOR）
注意，你可以按任意顺序使用每个 nums[i] 任意次。使 x 越过 0 <= x <= 1000 范围的运算同样可以生效，但该该运算执行后将不能执行其他运算。
返回将 x = start 转化为 goal 的最小操作数；如果无法完成转化，则返回 -1 。
示例 1：
输入：nums = [1,3], start = 6, goal = 4 输出：2 解释： 可以按 6 → 7 → 4 的转化路径进行，只需执行下述 2 次运算： - 6 ^ 1 = 7 - 7 ^ 3 = 4
示例 2：
输入：nums = [2,4,12], start = 2, goal = 12 输出：2 解释： 可以按 2 → 14 → 12 的转化路径进行，只需执行下述 2 次运算： - 2 + 12 = 14 - 14 - 2 = 12
示例 3：
输入：nums = [3,5,7], start = 0, goal = -4 输出：2 解释： 可以按 0 → 3 → -4 的转化路径进行，只需执行下述 2 次运算： - 0 + 3 = 3 - 3 - 7 = -4 注意，最后一步运算使 x 超过范围 0 <= x <= 1000 ，但该运算仍然可以生效。
示例 4：
输入：nums = [2,8,16], start = 0, goal = 1 输出：-1 解释： 无法将 0 转化为 1
示例 5：
输入：nums = [1], start = 0, goal = 3 输出：3 解释： 可以按 0 → 1 → 2 → 3 的转化路径进行，只需执行下述 3 次运算： - 0 + 1 = 1 - 1 + 1 = 2 - 2 + 1 = 3
提示：
1 <= nums.length <= 1000-109 <= nums[i], goal <= 1090 <= start <= 1000start != goalnums中的所有整数互不相同
BFS
class Solution:
def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
op1 = lambda x, y: x + y
op2 = lambda x, y: x - y
op3 = lambda x, y: x ^ y
ops = [op1, op2, op3]
vis = [False] * 1001
q = deque([(start, 0)])
while q:
x, step = q.popleft()
for num in nums:
for op in ops:
nx = op(x, num)
if nx == goal:
return step + 1
if nx >= 0 and nx <= 1000 and not vis[nx]:
q.append((nx, step + 1))
vis[nx] = True
return -1class Solution {
public int minimumOperations(int[] nums, int start, int goal) {
IntBinaryOperator op1 = (x, y) -> x + y;
IntBinaryOperator op2 = (x, y) -> x - y;
IntBinaryOperator op3 = (x, y) -> x ^ y;
IntBinaryOperator[] ops = { op1, op2, op3 };
boolean[] vis = new boolean[1001];
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] { start, 0 });
while (!queue.isEmpty()) {
int[] p = queue.poll();
int x = p[0], step = p[1];
for (int num : nums) {
for (IntBinaryOperator op : ops) {
int nx = op.applyAsInt(x, num);
if (nx == goal) {
return step + 1;
}
if (nx >= 0 && nx <= 1000 && !vis[nx]) {
queue.offer(new int[] { nx, step + 1 });
vis[nx] = true;
}
}
}
}
return -1;
}
}class Solution {
public:
int minimumOperations(vector<int>& nums, int start, int goal) {
using pii = pair<int, int>;
vector<function<int(int, int)>> ops{
[](int x, int y) { return x + y; },
[](int x, int y) { return x - y; },
[](int x, int y) { return x ^ y; },
};
vector<bool> vis(1001, false);
queue<pii> q;
q.push({start, 0});
while (!q.empty()) {
auto [x, step] = q.front();
q.pop();
for (int num : nums) {
for (auto op : ops) {
int nx = op(x, num);
if (nx == goal) {
return step + 1;
}
if (nx >= 0 && nx <= 1000 && !vis[nx]) {
q.push({nx, step + 1});
vis[nx] = true;
}
}
}
}
return -1;
}
};func minimumOperations(nums []int, start int, goal int) int {
type pair struct {
x int
step int
}
ops := []func(int, int) int{
func(x, y int) int { return x + y },
func(x, y int) int { return x - y },
func(x, y int) int { return x ^ y },
}
vis := make([]bool, 1001)
q := []pair{{start, 0}}
for len(q) > 0 {
x, step := q[0].x, q[0].step
q = q[1:]
for _, num := range nums {
for _, op := range ops {
nx := op(x, num)
if nx == goal {
return step + 1
}
if nx >= 0 && nx <= 1000 && !vis[nx] {
q = append(q, pair{nx, step + 1})
vis[nx] = true
}
}
}
}
return -1
}function minimumOperations(
nums: number[],
start: number,
goal: number
): number {
const n = nums.length;
const op1 = function (x: number, y: number): number {
return x + y;
};
const op2 = function (x: number, y: number): number {
return x - y;
};
const op3 = function (x: number, y: number): number {
return x ^ y;
};
const ops = [op1, op2, op3];
let vis = new Array(1001).fill(false);
let quenue: Array<Array<number>> = [[start, 0]];
vis[start] = true;
while (quenue.length) {
let [x, step] = quenue.shift();
for (let i = 0; i < n; i++) {
for (let j = 0; j < ops.length; j++) {
const nx = ops[j](x, nums[i]);
if (nx == goal) {
return step + 1;
}
if (nx >= 0 && nx <= 1000 && !vis[nx]) {
vis[nx] = true;
quenue.push([nx, step + 1]);
}
}
}
}
return -1;
}