class Solution {
public:
int minimumOperations(vector<int>& nums, int start, int goal) {
}
};
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 <= 1090 <= start <= 1000start != goalnums 中的所有整数互不相同原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 3.1 MB, 提交时间: 2023-09-14 00:24:44
/**
* 问题可以抽象成一张图，一次运算对应着图中的一条边。
* 我们要从 start 出发，求到 goal 的最短路，这可以用 BFS 来做。
*/
func minimumOperations(nums []int, start, goal int) int {
vis := [1001]bool{}
vis[start] = true
q := []int{start}
for step := 1; q != nil; step++ {
tmp := q
q = nil
for _, v := range tmp {
for _, num := range nums {
for _, x := range []int{v + num, v - num, v ^ num} {
if x == goal {
return step
}
// 由于超过范围无法继续运算，故不入队
if 0 <= x && x <= 1000 && !vis[x] {
vis[x] = true
q = append(q, x)
}
}
}
}
}
return -1
}
java 解法, 执行用时: 56 ms, 内存消耗: 42.3 MB, 提交时间: 2023-09-14 00:08:44
class Solution {
public int minimumOperations(int[] nums, int s, int t) {
Deque<Integer> d = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();
d.addLast(s);
map.put(s, 0);
while (!d.isEmpty()) {
int cur = d.pollFirst();
int step = map.get(cur);
for (int i : nums) {
int[] result = new int[]{cur + i, cur - i, cur ^ i};
for (int next : result) {
if (next == t) return step + 1;
if (next < 0 || next > 1000) continue;
if (map.containsKey(next)) continue;
map.put(next, step + 1);
d.addLast(next);
}
}
}
return -1;
}
}
java 解法, 执行用时: 47 ms, 内存消耗: 42.5 MB, 提交时间: 2023-09-14 00:08:15
class Solution {
public int minimumOperations(int[] nums, int start, int goal) {
Deque<Integer> q = new LinkedList<>();
q.offer(start);
boolean[] visited = new boolean[1001];
visited[start] = true;
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
step++;
while (size-- > 0){//当前队列元素对应同一个step
int poll = q.poll();
for (int n : nums) {
for (int x : new int[]{poll - n, poll + n, poll ^ n}) {
if (x == goal) {
return step;
}
if (x >= 0 && x <= 1000 && !visited[x]) {
q.offer(x);
visited[x] = true;
}
}
}
}
}
return -1;
}
}
cpp 解法, 执行用时: 196 ms, 内存消耗: 9.4 MB, 提交时间: 2023-09-14 00:07:45
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;
}
};
python3 解法, 执行用时: 1736 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-14 00:07:17
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