题目描述
给你一个下标从 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 <= 1090 <= start <= 1000start != goalnums 中的所有整数互不相同
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | 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;
}
|
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | 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
}
|
方法三
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | 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
}
|