转化数字的最小运算数

标签: 广度优先搜索数组

难度: 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]（按位异或 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
-10⁹ <= nums[i], goal <= 10⁹
0 <= start <= 1000
start != goal
nums 中的所有整数互不相同

Submission

运行时间: 524 ms

内存: 16.3 MB

from collections import deque

class Solution:
    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
        if start == goal:
            return 0

        queue = deque([(start, 0)])  # (current value, number of operations)
        visited = set([start])

        while queue:
            curr, ops = queue.popleft()

            for num in nums:
                # Addition operation
                new_x = curr + num
                if new_x == goal:
                    return ops + 1
                if 0 <= new_x <= 1000 and new_x not in visited:
                    visited.add(new_x)
                    queue.append((new_x, ops + 1))

                # Subtraction operation
                new_x = curr - num
                if new_x == goal:
                    return ops + 1
                if 0 <= new_x <= 1000 and new_x not in visited:
                    visited.add(new_x)
                    queue.append((new_x, ops + 1))

                # XOR operation
                new_x = curr ^ num
                if new_x == goal:
                    return ops + 1
                if 0 <= new_x <= 1000 and new_x not in visited:
                    visited.add(new_x)
                    queue.append((new_x, ops + 1))

        return -1  # No transformation path found

solution = Solution()
nums = [2, 4, 12]
start = 2
goal = 12
result = solution.minimumOperations(nums, start, goal)
print(result)  # Output: 2

Explain

这个题解使用了广度优先搜索（BFS）来寻找将start转换为goal的最短路径。初始状态为(start, 0)，其中0表示操作次数。然后，对于队列中的每个状态，分别尝试加、减和异或三种操作，并将得到的新状态添加到队列中（如果它们在合法范围内且未被访问过）。如果在任何时候，新状态等于goal，则返回当前操作数加1。如果队列变为空，说明无法到达goal，返回-1。

时间复杂度: O(3^n)

空间复杂度: O(1)

from collections import deque

class Solution:
    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
        if start == goal:
            return 0

        queue = deque([(start, 0)])  # (current value, number of operations)
        visited = set([start])

        while queue:
            curr, ops = queue.popleft()

            for num in nums:
                # Addition operation
                new_x = curr + num
                if new_x == goal:
                    return ops + 1
                if 0 <= new_x <= 1000 and new_x not in visited:
                    visited.add(new_x)
                    queue.append((new_x, ops + 1))

                # Subtraction operation
                new_x = curr - num
                if new_x == goal:
                    return ops + 1
                if 0 <= new_x <= 1000 and new_x not in visited:
                    visited.add(new_x)
                    queue.append((new_x, ops + 1))

                # XOR operation
                new_x = curr ^ num
                if new_x == goal:
                    return ops + 1
                if 0 <= new_x <= 1000 and new_x not in visited:
                    visited.add(new_x)
                    queue.append((new_x, ops + 1))

        return -1  # No transformation path found

solution = Solution()
nums = [2, 4, 12]
start = 2
goal = 12
result = solution.minimumOperations(nums, start, goal)
print(result)  # Output: 2

Explore

在这个问题中，限制数值在0到1000范围内是为了防止数值越界并简化问题处理。在实际应用中，此范围可以视为问题的一部分规则或约束条件。超出此范围的数值可能无法保证后续操作的合法性或结果的正确性，因此，一旦数值超出这个范围，就不再将其作为有效状态加入到队列中，以避免无效计算和潜在的错误。

这里的加1代表进行了一次操作（无论是加、减或异或）使得当前状态变为目标状态goal。因为在进入循环之前已经进行了一次操作，所以我们需要在当前的操作次数基础上加1来正确反映到达目标状态所需的总操作次数。

为了防止重复访问相同状态，算法使用了一个集合（set）来存储已经访问过的状态。在尝试每种操作并生成新状态时，首先检查这个状态是否已经存在于集合中。如果存在，说明该状态已被处理过，就不再将它添加到队列中。这种方法可以有效避免重复处理相同状态，从而提高算法的效率。

算法通过在每次生成新状态后立即检查该状态是否在0到1000的合法范围内来确保数值的合法性。只有当新生成的状态符合这个范围时，才会将其添加到队列和访问过的集合中。这样可以确保所有在队列中处理的状态都是合法的，避免了处理非法或无效状态的问题。