This action will force synchronization from doocs/leetcode, which will overwrite any changes that you have made since you forked the repository, and can not be recovered!!!
Synchronous operation will process in the background and will refresh the page when finishing processing. Please be patient.
给你一个下标从 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
中的所有整数互不相同BFS 最小步数模型。本题搜索空间不大,可以直接使用朴素 BFS,以下题解中还提供了双向 BFS 的题解代码,仅供参考。
双向 BFS 是 BFS 常见的一个优化方法,主要实现思路如下:
while q1 and q2:
if len(q1) <= len(q2):
# 优先选择较少元素的队列进行扩展
extend(m1, m2, q1)
else:
extend(m2, m1, q2)
def extend(m1, m2, q):
# 新一轮扩展
for _ in range(len(q)):
p = q.popleft()
step = m1[p]
for t in next(p):
if t in m1:
# 此前已经访问过
continue
if t in m2:
# 另一个方向已经搜索过,说明找到了一条最短的连通路径
return step + 1 + m2[t]
q.append(t)
m1[t] = step + 1
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:
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
双向 BFS:
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 {
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(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;
}
}
双向 BFS:
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) {
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;
}
};
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;
}
};
双向 BFS:
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 {
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
}
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
}
双向 BFS:
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
}
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;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。