2059-转化数字的最小运算数

给你一个下标从 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 = [2,4,12], start = 2, goal = 12
**输出：** 2
**解释：**
可以按 2 → 14 → 12 的转化路径进行，只需执行下述 2 次运算：
- 2 + 12 = 14
- 14 - 2 = 12

示例 2：

**输入：** nums = [3,5,7], start = 0, goal = -4
**输出：** 2
**解释：**
可以按 0 → 3 → -4 的转化路径进行，只需执行下述 2 次运算：
- 0 + 3 = 3
- 3 - 7 = -4
注意，最后一步运算使 x 超过范围 0 <= x <= 1000 ，但该运算仍然可以生效。

示例 3：

**输入：** nums = [2,8,16], start = 0, goal = 1
**输出：** -1
**解释：**
无法将 0 转化为 1

提示：

• 1 <= nums.length <= 1000
• -109 <= nums[i], goal <= 109
• 0 <= start <= 1000
• start != goal
• nums 中的所有整数互不相同

方法一：广度优先搜索

思路与算法

我们可以使用广度优先搜索寻找将初始值转化为目标值的最小次数。

在广度优先搜索的过程中，我们在队列中保存 (x, \textit{step}) 二元组，其中 x 为当前整数的值，step 为当前值对应的转化次数。注意到如果 x 不在可以操作的范围（本题为 [0, 1000] 闭区间内的整数）内，除非 x = \textit{goal 恰好成立，否则由于我们无法进行任何操作，该数一定无法转化为目标值。故我们无需将可操作范围以外的数值加入队列。且由于初始值一定在可操作范围内，因此我们可以保证队列中的值一定在可操作范围内。

除此以外，为了避免重复遍历，我们需要用数组 vis 来维护可操作范围内整数是否已被加入过队列。

当我们遍历到 x 时，我们枚举数组中的元素和加、减与按位异或三种操作，计算生成的值 nx，此时有以下几种情况：

• nx 恰好等于目标值 goal，此时我们应当返回 step}) + 1，即初始值转化为目标值的最小次数作为答案；

• nx 不在可操作范围，此时我们无需做任何操作；

• nx 在可操作范围，且 nx 已被加入过队列，此时我们无需做任何操作；

• nx 在可操作范围，且 nx 未被加入过队列，此时我们需要更新 nx 的访问情况，并将 (\textit{nx}, \textit{step} + 1) 二元组加入队列。其中 step} + 1 为新生成的值对应的转化次数。

最终，如果不存在转化为目标值的方案，我们返回 -1 作为答案。

代码

[sol1-C++]

class Solution {
public:
    int minimumOperations(vector<int>& nums, int start, int goal) {
        int n = nums.size();
        auto op1 = [](int x, int y) -> int { return x + y; };
        auto op2 = [](int x, int y) -> int { return x - y; };
        auto op3 = [](int x, int y) -> int { return x ^ y; };
        vector<function<int(int, int)>> ops = {op1, op2, op3};   // 运算符列表
        vector<int> vis(1001, 0);   // 可操作范围内整数的访问情况
        queue<pair<int, int>> q;
        q.emplace(start, 0);
        vis[start] = 1;
        while (!q.empty()){
            auto [x, step] = q.front();
            q.pop();
            // 枚举数组中的元素和操作符并计算新生成的数值
            for (int i = 0; i < n; ++i){
                for (auto& op: ops){
                    int nx = op(x, nums[i]);
                    // 如果新生成的数值等于目标值，则返回对应操作数
                    if (nx == goal){
                        return step + 1;
                    }
                    // 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列
                    if (nx >= 0 && nx <= 1000 && !vis[nx]){
                        vis[nx] = 1;
                        q.emplace(nx, step + 1);
                    }
                }
            }
        }
        // 不存在从初始值到目标值的转化方案
        return -1;
    }
};

[sol1-Python3]

class Solution:
    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
        n = len(nums)
        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)])
        vis[start] = True
        while q:
            x, step = q.popleft()
            # 枚举数组中的元素和操作符并计算新生成的数值
            for i in range(n):
                for op in ops:
                    nx = op(x, nums[i])
                    # 如果新生成的数值等于目标值，则返回对应操作数
                    if nx == goal:
                        return step + 1
                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列
                    if 0 <= nx <= 1000 and vis[nx] is False:
                        vis[nx] = True
                        q.append((nx, step + 1))
        # 不存在从初始值到目标值的转化方案
        return -1

复杂度分析

• 时间复杂度：O(mn)，其中 n 为 nums 的长度，m 为可对 x 进行操作的取值范围大小。广度优先搜索至多需要将 O(m) 个数值加入队列，对于每个加入队列的数值可能的操作种数为 O(n) 个。

• 空间复杂度：O(m)。即为广度优先搜索队列的空间开销。