力扣 5916. 转化数字的最小运算数

题目来源：https://leetcode-cn.com/problems/minimum-operations-to-convert-number/

大致题意：
给定一个数组，和一个初始值和目标值。可以对每个数组元素值 + - ^ 三种运算使初始值变为目标值，其中每个数组不限使用次数。如果当前数不在 [0, 1000] 之内，那么将不能够再做运算

思路

一开始使用 DFS，然后存最小操作数，若当前值等于目标值就更新最小值。但是这样对运算结果算多次，应该使用标记数组标记被操作过的数，防止重复计算。
可是这样的话，因为 DFS 的原因，第一次遍历到该数的操作次数不一定是最小的（没有考虑当前步所有可能结果，就直接下一步）。所以使用 BFS 更为合适，BFS 保证第一次找到的即为最小操作数

BFS

1. 初始时，使用队列存下 start 和 操作数 0
2. 当队列不为空时，计算当前队首元素对应的临时结果 + - ^ 每个数组元素的结果，若计算结果越界，查看其是否等于目标值，若等于直接返回操作数；若计算结果不越界，判断其是否已被标记，若未被标记，标记并存入队列

代码：

public int minimumOperations(int[] nums, int start, int goal) {
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{start, 0}); // 初始时存入 start
        boolean[] vis = new boolean[1010];  // 标记数组
        // BFS
        while (!queue.isEmpty()) {
            int[] pair = queue.poll();
            int curNum = pair[0];
            int opCount = pair[1];
            if (curNum == goal) {   // 若等于 goal，返回操作数
                return opCount;
            }
            for (int i = 0; i < nums.length; i++) { // 遍历数组，将符合条件的数值对存入队列、
                // 对于当前元素的三种运算结果
                int add = curNum + nums[i];
                int minus = curNum - nums[i];
                int xor = curNum ^ nums[i];
                if (add < 0 || add > 1000) {    // 若结果越界
                    if (add == goal) {
                        return opCount + 1;
                    }
                } else if (!vis[add]) { // 若结果不越界且未被标记
                    vis[add] = true;
                    queue.add(new int[]{add, opCount + 1});
                }
                if (minus < 0 || minus > 1000) {
                    if (minus == goal) {
                        return opCount + 1;
                    }
                } else if (!vis[minus]) {
                    vis[minus] = true;
                    queue.add(new int[]{minus, opCount + 1});
                }
                if (xor < 0 || xor > 1000) {
                    if (xor == goal) {
                        return opCount + 1;
                    }
                } else if (!vis[xor]) {
                    vis[xor] = true;
                    queue.add(new int[]{xor, opCount + 1});
                }
            }
        }
        return -1;
    }