文章目录 - 1. 题目
- 2. 解题
1. 题目
给你一个下标从 0 开始的整数数组 nums ，该数组由 互不相同 的数字组成。另给你两个整数 start 和 goal 。
整数 x 的值最开始设为 start ，你打算执行一些运算使 x 转化为 goal 。你可以对数字 x 重复执行下述运算：
- 如果
0 <= x <= 1000
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
-10^9 <= nums[i], goal <= 10^9
0 <= start <= 1000
start != goal
nums 中的所有整数互不相同 复制
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-operations-to-convert-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 广度优先搜索，注意只有在 [ 0, 1000] 范围内的才能够进入队列
class Solution {
public:
int minimumOperations(vector<int>& nums, int start, int goal) {
queue<int> q;
vector<int> vis(1001, false);
q.push(start);
vis[start] = true;
int step = 0;
while(!q.empty())
{
int size = q.size();
while(size--)
{
int x = q.front();
q.pop();
for(auto num : nums)
{
if(x+num==goal) return step+1;
if(x-num==goal) return step+1;
if((x^num)==goal) return step+1;
if(x+num>=0 && x+num<=1000 && !vis[x+num])
{
vis[x+num] = true;
q.push(x+num);
}
if(x-num>=0 && x-num<=1000 && !vis[x-num])
{
vis[x-num] = true;
q.push(x-num);
}
if((x^num)>=0 && (x^num)<=1000 && !vis[x^num])
{
vis[x^num] = true;
q.push(x^num);
}
}
}
step++;
}
return -1;
}
}; 复制
20 ms 9 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/