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 = [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 中的所有整數互不相同

解題思路

利用隊列完成廣度優先搜索，并且使用set記錄已經遍歷過的元素，每次對于x進行如下操作

• x + nums[i]
• x - nums[i]
• x ^ nums[i]（按位異或 XOR）
  再將結果加入到隊列里面，當運算結果越過 0 <= x <= 1000 范圍，那么就不將其加入隊列當中。

代碼

class Solution {
public:int minimumOperations(vector<int> nums, int start, int goal) {queue<int> q;int d(1);q.push(start);unordered_set<int> s{start};while (q.size() != 0) {int len=q.size();for (int i = 0; i < len; ++i) {int  cur=q.front();q.pop();for (auto n:nums){if (goal==n+cur)return d;if (goal==cur-n)return d;if (goal==(cur^n))return d;if (cur+n<=1000&&cur+n>=0&&s.find(cur+n)==s.end()){q.push(cur+n);s.insert(cur+n);}if (cur-n<=1000&&cur-n>=0&&s.find(cur-n)==s.end()){q.push(cur-n);s.insert(cur-n);}if ((cur^n)<=1000&&(cur^n)>=0&&s.find(cur^n)==s.end()){q.push(cur^n);s.insert(cur^n);}}}d++;}return -1;}
};