You are given a 0-indexed integer array nums
containing distinct numbers, an integer start
, and an integer goal
. There is an integer x
that is initially set to start
, and you want to perform operations on x
such that it is converted to goal
. You can perform the following operation repeatedly on the number x
:
If 0 <= x <= 1000
, then for any index i
in the array (0 <= i < nums.length
), you can set x
to any of the following:
x + nums[i]
x - nums[i]
x ^ nums[i]
(bitwise-XOR)
Note that you can use each nums[i]
any number of times in any order. Operations that set x
to be out of the range 0 <= x <= 1000
are valid, but no more operations can be done afterward.
Return the minimum number of operations needed to convert x = start
into goal
, and -1
if it is not possible.
Example 1:
Input: nums = [1,3], start = 6, goal = 4 Output: 2 Explanation: We can go from 6 → 7 → 4 with the following 2 operations. - 6 ^ 1 = 7 - 7 ^ 3 = 4
Example 2:
Input: nums = [2,4,12], start = 2, goal = 12 Output: 2 Explanation: We can go from 2 → 14 → 12 with the following 2 operations. - 2 + 12 = 14 - 14 - 2 = 12
Example 3:
Input: nums = [3,5,7], start = 0, goal = -4 Output: 2 Explanation: We can go from 0 → 3 → -4 with the following 2 operations. - 0 + 3 = 3 - 3 - 7 = -4 Note that the last operation sets x out of the range 0 <= x <= 1000, which is valid.
Example 4:
Input: nums = [2,8,16], start = 0, goal = 1 Output: -1 Explanation: There is no way to convert 0 into 1.
Example 5:
1 2 3 4 5 6 7 |
<strong>Input:</strong> nums = [1], start = 0, goal = 3 <strong>Output:</strong> 3 <strong>Explanation:</strong> We can go from 0 → 1 → 2 → 3 with the following 3 operations. - 0 + 1 = 1 - 1 + 1 = 2 - 2 + 1 = 3 |
Constraints:
1 <= nums.length <= 1000
-109 <= nums[i], goal <= 109
0 <= start <= 1000
start != goal
- All the integers in
nums
are distinct.
Solution: BFS
Time complexity: O(n*m)
Space complexity: O(m)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int minimumOperations(vector<int>& nums, int start, int goal) { vector<int> seen(1001); queue<int> q{{start}}; for (int ans = 1, s = 1; !q.empty(); ++ans, s = q.size()) { while (s--) { int x = q.front(); q.pop(); for (int n : nums) for (int t : {x + n, x - n, x ^ n}) if (t == goal) return ans; else if (t < 0 || t > 1000 || seen[t]++) continue; else q.push(t); } } return -1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment