Question

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

English Version

题目描述

给你一个下标从 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 中的所有整数互不相同

解法

方法一

class Solution:
  def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
    op1 = lambda x, y: x + y
    op2 = lambda x, y: x - y
    op3 = lambda x, y: x ^ y
    ops = [op1, op2, op3]
    vis = [False] * 1001
    q = deque([(start, 0)])
    while q:
      x, step = q.popleft()
      for num in nums:
        for op in ops:
          nx = op(x, num)
          if nx == goal:
            return step + 1
          if 0 <= nx <= 1000 and not vis[nx]:
            q.append((nx, step + 1))
            vis[nx] = True
    return -1

class Solution {
  public int minimumOperations(int[] nums, int start, int goal) {
    IntBinaryOperator op1 = (x, y) -> x + y;
    IntBinaryOperator op2 = (x, y) -> x - y;
    IntBinaryOperator op3 = (x, y) -> x ^ y;
    IntBinaryOperator[] ops = {op1, op2, op3};
    boolean[] vis = new boolean[1001];
    Queue<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[] {start, 0});
    while (!queue.isEmpty()) {
      int[] p = queue.poll();
      int x = p[0], step = p[1];
      for (int num : nums) {
        for (IntBinaryOperator op : ops) {
          int nx = op.applyAsInt(x, num);
          if (nx == goal) {
            return step + 1;
          }
          if (nx >= 0 && nx <= 1000 && !vis[nx]) {
            queue.offer(new int[] {nx, step + 1});
            vis[nx] = true;
          }
        }
      }
    }
    return -1;
  }
}

class Solution {
public:
  int minimumOperations(vector<int>& nums, int start, int goal) {
    using pii = pair<int, int>;
    vector<function<int(int, int)>> ops{
      [](int x, int y) { return x + y; },
      [](int x, int y) { return x - y; },
      [](int x, int y) { return x ^ y; },
    };
    vector<bool> vis(1001, false);
    queue<pii> q;
    q.push({start, 0});
    while (!q.empty()) {
      auto [x, step] = q.front();
      q.pop();
      for (int num : nums) {
        for (auto op : ops) {
          int nx = op(x, num);
          if (nx == goal) {
            return step + 1;
          }
          if (nx >= 0 && nx <= 1000 && !vis[nx]) {
            q.push({nx, step + 1});
            vis[nx] = true;
          }
        }
      }
    }
    return -1;
  }
};

func minimumOperations(nums []int, start int, goal int) int {
  type pair struct {
    x  int
    step int
  }

  ops := []func(int, int) int{
    func(x, y int) int { return x + y },
    func(x, y int) int { return x - y },
    func(x, y int) int { return x ^ y },
  }
  vis := make([]bool, 1001)
  q := []pair{{start, 0}}

  for len(q) > 0 {
    x, step := q[0].x, q[0].step
    q = q[1:]
    for _, num := range nums {
      for _, op := range ops {
        nx := op(x, num)
        if nx == goal {
          return step + 1
        }
        if nx >= 0 && nx <= 1000 && !vis[nx] {
          q = append(q, pair{nx, step + 1})
          vis[nx] = true
        }
      }
    }
  }
  return -1
}

function minimumOperations(nums: number[], start: number, goal: number): number {
  const n = nums.length;
  const op1 = function (x: number, y: number): number {
    return x + y;
  };
  const op2 = function (x: number, y: number): number {
    return x - y;
  };
  const op3 = function (x: number, y: number): number {
    return x ^ y;
  };
  const ops = [op1, op2, op3];
  let vis = new Array(1001).fill(false);
  let quenue: Array<Array<number>> = [[start, 0]];
  vis[start] = true;
  while (quenue.length) {
    let [x, step] = quenue.shift();
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < ops.length; j++) {
        const nx = ops[j](x, nums[i]);
        if (nx == goal) {
          return step + 1;
        }
        if (nx >= 0 && nx <= 1000 && !vis[nx]) {
          vis[nx] = true;
          quenue.push([nx, step + 1]);
        }
      }
    }
  }
  return -1;
}

方法二

class Solution:
  def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
    def next(x):
      res = []
      for num in nums:
        res.append(x + num)
        res.append(x - num)
        res.append(x ^ num)
      return res

    q = deque([start])
    vis = {start}
    ans = 0
    while q:
      ans += 1
      for _ in range(len(q)):
        x = q.popleft()
        for y in next(x):
          if y == goal:
            return ans
          if 0 <= y <= 1000 and y not in vis:
            vis.add(y)
            q.append(y)
    return -1

class Solution {
  public int minimumOperations(int[] nums, int start, int goal) {
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(start);
    boolean[] vis = new boolean[1001];
    int ans = 0;
    while (!q.isEmpty()) {
      ++ans;
      for (int n = q.size(); n > 0; --n) {
        int x = q.poll();
        for (int y : next(nums, x)) {
          if (y == goal) {
            return ans;
          }
          if (y >= 0 && y <= 1000 && !vis[y]) {
            vis[y] = true;
            q.offer(y);
          }
        }
      }
    }
    return -1;
  }

  private List<Integer> next(int[] nums, int x) {
    List<Integer> res = new ArrayList<>();
    for (int num : nums) {
      res.add(x + num);
      res.add(x - num);
      res.add(x ^ num);
    }
    return res;
  }
}

class Solution {
public:
  int minimumOperations(vector<int>& nums, int start, int goal) {
    queue<int> q{{start}};
    vector<bool> vis(1001);
    int ans = 0;
    while (!q.empty()) {
      ++ans;
      for (int n = q.size(); n > 0; --n) {
        int x = q.front();
        q.pop();
        for (int y : next(nums, x)) {
          if (y == goal) return ans;
          if (y >= 0 && y <= 1000 && !vis[y]) {
            vis[y] = true;
            q.push(y);
          }
        }
      }
    }
    return -1;
  }

  vector<int> next(vector<int>& nums, int x) {
    vector<int> res;
    for (int num : nums) {
      res.push_back(x + num);
      res.push_back(x - num);
      res.push_back(x ^ num);
    }
    return res;
  }
};

func minimumOperations(nums []int, start int, goal int) int {
  next := func(x int) []int {
    var res []int
    for _, num := range nums {
      res = append(res, []int{x + num, x - num, x ^ num}...)
    }
    return res
  }
  q := []int{start}
  vis := make([]bool, 1001)
  ans := 0
  for len(q) > 0 {
    ans++
    for n := len(q); n > 0; n-- {
      x := q[0]
      q = q[1:]
      for _, y := range next(x) {
        if y == goal {
          return ans
        }
        if y >= 0 && y <= 1000 && !vis[y] {
          vis[y] = true
          q = append(q, y)
        }
      }
    }
  }
  return -1
}

方法三

class Solution:
  def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
    def next(x):
      res = []
      for num in nums:
        res.append(x + num)
        res.append(x - num)
        res.append(x ^ num)
      return res

    def extend(m1, m2, q):
      for _ in range(len(q)):
        x = q.popleft()
        step = m1[x]
        for y in next(x):
          if y in m1:
            continue
          if y in m2:
            return step + 1 + m2[y]
          if 0 <= y <= 1000:
            m1[y] = step + 1
            q.append(y)
      return -1

    m1, m2 = {start: 0}, {goal: 0}
    q1, q2 = deque([start]), deque([goal])
    while q1 and q2:
      t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2)
      if t != -1:
        return t
    return -1

class Solution {
  private int[] nums;

  public int minimumOperations(int[] nums, int start, int goal) {
    this.nums = nums;
    Map<Integer, Integer> m1 = new HashMap<>();
    Map<Integer, Integer> m2 = new HashMap<>();
    Deque<Integer> q1 = new ArrayDeque<>();
    Deque<Integer> q2 = new ArrayDeque<>();
    m1.put(start, 0);
    m2.put(goal, 0);
    q1.offer(start);
    q2.offer(goal);
    while (!q1.isEmpty() && !q2.isEmpty()) {
      int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
      if (t != -1) {
        return t;
      }
    }
    return -1;
  }

  private int extend(Map<Integer, Integer> m1, Map<Integer, Integer> m2, Deque<Integer> q) {
    for (int i = q.size(); i > 0; --i) {
      int x = q.poll();
      int step = m1.get(x);
      for (int y : next(x)) {
        if (m1.containsKey(y)) {
          continue;
        }
        if (m2.containsKey(y)) {
          return step + 1 + m2.get(y);
        }
        if (y >= 0 && y <= 1000) {
          m1.put(y, step + 1);
          q.offer(y);
        }
      }
    }
    return -1;
  }

  private List<Integer> next(int x) {
    List<Integer> res = new ArrayList<>();
    for (int num : nums) {
      res.add(x + num);
      res.add(x - num);
      res.add(x ^ num);
    }
    return res;
  }
}

class Solution {
public:
  int minimumOperations(vector<int>& nums, int start, int goal) {
    unordered_map<int, int> m1;
    unordered_map<int, int> m2;
    m1[start] = 0;
    m2[goal] = 0;
    queue<int> q1{{start}};
    queue<int> q2{{goal}};
    while (!q1.empty() && !q2.empty()) {
      int t = q1.size() <= q2.size() ? extend(m1, m2, q1, nums) : extend(m2, m1, q2, nums);
      if (t != -1) return t;
    }
    return -1;
  }

  int extend(unordered_map<int, int>& m1, unordered_map<int, int>& m2, queue<int>& q, vector<int>& nums) {
    for (int i = q.size(); i > 0; --i) {
      int x = q.front();
      int step = m1[x];
      q.pop();
      for (int y : next(nums, x)) {
        if (m1.count(y)) continue;
        if (m2.count(y)) return step + 1 + m2[y];
        if (y >= 0 && y <= 1000) {
          m1[y] = step + 1;
          q.push(y);
        }
      }
    }
    return -1;
  }

  vector<int> next(vector<int>& nums, int x) {
    vector<int> res;
    for (int num : nums) {
      res.push_back(x + num);
      res.push_back(x - num);
      res.push_back(x ^ num);
    }
    return res;
  }
};

func minimumOperations(nums []int, start int, goal int) int {
  next := func(x int) []int {
    var res []int
    for _, num := range nums {
      res = append(res, []int{x + num, x - num, x ^ num}...)
    }
    return res
  }
  m1, m2 := map[int]int{start: 0}, map[int]int{goal: 0}
  q1, q2 := []int{start}, []int{goal}
  extend := func() int {
    for i := len(q1); i > 0; i-- {
      x := q1[0]
      q1 = q1[1:]
      step, _ := m1[x]
      for _, y := range next(x) {
        if _, ok := m1[y]; ok {
          continue
        }
        if v, ok := m2[y]; ok {
          return step + 1 + v
        }
        if y >= 0 && y <= 1000 {
          m1[y] = step + 1
          q1 = append(q1, y)
        }
      }
    }
    return -1
  }
  for len(q1) > 0 && len(q2) > 0 {
    if len(q1) > len(q2) {
      m1, m2 = m2, m1
      q1, q2 = q2, q1
    }
    t := extend()
    if t != -1 {
      return t
    }
  }
  return -1
}