Medium

题目描述

给你一个下标从 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]（按位异或）

注意，你可以按任意顺序使用每个 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
  • -10^9 <= nums[i], goal <= 10^9
  • 0 <= start <= 1000
  • start != goal
  • nums 中的所有整数互不相同

解题思路

这是一道典型的 BFS 最短路径问题。我们需要从 start 开始，通过最少的操作步数到达 goal。

核心思路：

  1. 使用 BFS 逐层搜索，第一次到达 goal 的路径就是最短的
  2. 对于当前值 x，我们可以对数组中每个数字执行三种操作：加法、减法、异或
  3. 关键约束：只有当 0 <= x <= 1000 时才能继续操作，但如果某次操作直接得到 goal，即使超出范围也是有效的

算法步骤：

  1. 使用队列进行 BFS，初始状态为 (start, 0)，表示当前值和操作次数
  2. 使用 visited 数组记录 [0, 1000] 范围内访问过的数字，避免重复访问
  3. 对队列中的每个状态，尝试所有可能的操作：
    • 如果操作结果等于 goal，直接返回操作次数 + 1
    • 如果操作结果在 [0, 1000] 范围内且未访问过，加入队列继续搜索
  4. 如果队列为空仍未找到 goal，返回 -1

优化细节：

  • 只对 [0, 1000] 范围内的值进行状态记录，因为超出此范围就不能继续操作
  • 每次操作前都要检查是否直接达到了目标值

代码实现

class Solution {
public:
    int minimumOperations(vector<int>& nums, int start, int goal) {
        queue<pair<int, int>> q;
        vector<bool> visited(1001, false);
        
        q.push({start, 0});
        visited[start] = true;
        
        while (!q.empty()) {
            auto [x, ops] = q.front();
            q.pop();
            
            for (int num : nums) {
                vector<int> next = {x + num, x - num, x ^ num};
                
                for (int nx : next) {
                    if (nx == goal) {
                        return ops + 1;
                    }
                    
                    if (nx >= 0 && nx <= 1000 && !visited[nx]) {
                        visited[nx] = true;
                        q.push({nx, ops + 1});
                    }
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
        from collections import deque
        
        queue = deque([(start, 0)])
        visited = [False] * 1001
        visited[start] = True
        
        while queue:
            x, ops = queue.popleft()
            
            for num in nums:
                for nx in [x + num, x - num, x ^ num]:
                    if nx == goal:
                        return ops + 1
                    
                    if 0 <= nx <= 1000 and not visited[nx]:
                        visited[nx] = True
                        queue.append((nx, ops + 1))
        
        return -1

public class Solution {
    public int MinimumOperations(int[] nums, int start, int goal) {
        Queue<(int x, int ops)> queue = new Queue<(int, int)>();
        bool[] visited = new bool[1001];
        
        queue.Enqueue((start, 0));
        visited[start] = true;
        
        while (queue.Count > 0) {
            var (x, ops) = queue.Dequeue();
            
            foreach (int num in nums) {
                int[] next = {x + num, x - num, x ^ num};
                
                foreach (int nx in next) {
                    if (nx == goal) {
                        return ops + 1;
                    }
                    
                    if (nx >= 0 && nx <= 1000 && !visited[nx]) {
                        visited[nx] = true;
                        queue.Enqueue((nx, ops + 1));
                    }
                }
            }
        }
        
        return -1;
    }
}

var minimumOperations = function(nums, start, goal) {
    const queue = [start];
    const visited = new Set([start]);
    let operations = 0;
    
    while (queue.length > 0) {
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const current = queue.shift();
            
            if (current === goal) {
                return operations;
            }
            
            for (const num of nums) {
                const candidates = [
                    current + num,
                    current - num,
                    current ^ num
                ];
                
                for (const next of candidates) {
                    if (next === goal) {
                        return operations + 1;
                    }
                    
                    if (next >= 0 && next <= 1000 && !visited.has(next)) {
                        visited.add(next);
                        queue.push(next);
                    }
                }
            }
        }
        
        operations++;
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1000 × n)最多访问 1001 个状态，每个状态需要尝试 3n 种操作
空间复杂度O(1000)visited 数组和队列的空间开销

相关题目