原文链接: https://leetcode-cn.com/problems/minimum-operations-to-convert-number

英文原文

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:

Input: nums = [1], start = 0, goal = 3
Output: 3
Explanation: 
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.

中文题目

给你一个下标从 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
• -109 <= nums[i], goal <= 109
• 0 <= start <= 1000
• start != goal
• nums 中的所有整数互不相同

通过代码

高赞题解

解题思路

leetcode上的最短距离类问题 -> 大概率会用BFS解决

题目意思其实非常直白，我们直接从start开始搜索所有的操作，看最短多少次可以搜索到goal即可。
为了记录步数，我们每次出队将队列清空，计步器自增操作 step++。
每个出队的元素，我们进行三种不同的运算；如果超过范围或者已经遍历过，我们直接跳过。
如果和目标值一样，我们直接返回step。
其余情况我们入队，并将访问标记置为true。

代码

class Solution {
public:
    int visited[1005] = {0};
    
    int minimumOperations(vector<int>& nums, int start, int goal) {
        queue<int> Q;
        Q.push(start);
        
        for (int i = 0; i < 1005; i++) {
            visited[i] = 0;
        }
        
        int step = 0;
        visited[start] = 1;
        while (!Q.empty()) {
            step++;
            queue<int> QQ;
            while(!Q.empty()) {
                int x = Q.front();
                Q.pop();
                for (int i = 0; i < nums.size(); i++) {
                    int t1 = x + nums[i];
                    int t2 = x - nums[i];
                    int t3 = x ^ nums[i];
                    if (t1 == goal || t2 == goal || t3 == goal) return step;
                    if (!(t1 < 0 || t1 > 1000 || visited[t1])) {
                        QQ.push(t1);
                        visited[t1] = 1;
                    }
                    if (!(t2 < 0 || t2 > 1000 || visited[t2])) {
                        QQ.push(t2);
                        visited[t2] = 1;
                    }
                    if (!(t3 < 0 || t3 > 1000 || visited[t3])) {
                        QQ.push(t3);
                        visited[t3] = 1;
                    }
                }
            }
            Q = QQ;
        }
        
        
        return -1;
    }
    
    
};

关于我

大家好，我是微扰酱。现在是五道口【悖论13】剧本杀的股东之一，点评搜索即可，欢迎大家来探店。
微扰酱18年毕业于上海交通大学，是一个在阿里、字节、腾讯都工作过的工程师，有丰富的面试经验。从 2021.4 开始在emqx从事存储研发，希望在今年多多输出。

最后，如果对你有帮助，可以点个赞支持一下我哦 也欢迎在leetcode上关注我。

欢迎留言预定配图！

统计信息

通过次数	提交次数	AC比率
3846	9066	42.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言