跳到主要内容

2059.转化数字的最小运算数

· 阅读需 4 分钟

1、题干​

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

解题思路​

  • 把 start 看做树的根节点
  • start 与 nums 进行 +-^ 三种操作的结果看做第一层子节点
  • 依此类推可以构建出一棵树
  • 题目要求找到 start 转化为 goal 的最小操作数，实际就是在整颗树中找到 goal 所在的层数
  • 所以采用 BFS 方式进行查找，过程中注意处理边界条件、减少耗时操作，以免死循环或超时

代码​

/**
 * @param {number[]} nums
 * @param {number} start
 * @param {number} goal
 * @return {number}
 */
var minimumOperations = function(nums, start, goal) {
    const queueMatrix = [[start]];
    let count = 0;
    const set = new Set();

    while (queueMatrix.length) {
        const queue = queueMatrix.shift();
        count += 1;
        const newQueue = [];

        for (let k = 0; k < queue.length; k++) {
            start = queue[k];
            if (start < 0 || start > 1000 || set.has(start)) continue;

            set.add(start);
            for (let i = 0; i < nums.length; i++) {
                const n1 = start + nums[i];
                const n2 = start - nums[i];
                const n3 = start ^ nums[i];
                newQueue.push(n1);
                newQueue.push(n2);
                newQueue.push(n3);

                if (n1 === goal || n2 === goal || n3 === goal) return count;
            }
        }

        if (newQueue.length) queueMatrix.push(newQueue);
    }

    return -1;
};