leetcode
leetcode 1801 ~ 1850
转化数字的最小运算数

转化数字的最小运算数

难度:

标签:

题目描述

代码结果

运行时间: 524 ms, 内存: 16.3 MB


/*
思路:
1. 使用广度优先搜索(BFS)来找到从start到goal的最短路径。
2. 每一步可以通过对x执行加、减、异或操作来生成新的状态。
3. 使用Stream来处理nums数组。
4. 使用一个队列来存储当前的状态和操作次数,并且使用一个布尔数组来记录访问过的状态以避免重复计算。
5. 当某个状态等于goal时,返回操作次数。
6. 如果队列为空且未找到goal,返回-1。
*/
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int minimumOperations(int[] nums, int start, int goal) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[] visited = new boolean[1001];
        queue.add(new int[]{start, 0});
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0], steps = current[1];
            if (x == goal) return steps;
            if (x < 0 || x > 1000 || visited[x]) continue;
            visited[x] = true;
            IntStream.of(nums).forEach(num -> {
                queue.add(new int[]{x + num, steps + 1});
                queue.add(new int[]{x - num, steps + 1});
                queue.add(new int[]{x ^ num, steps + 1});
            });
        }
        return -1;
    }
}

解释

方法:

这个题解使用了广度优先搜索(BFS)来寻找将start转换为goal的最短路径。初始状态为(start, 0),其中0表示操作次数。然后,对于队列中的每个状态,分别尝试加、减和异或三种操作,并将得到的新状态添加到队列中(如果它们在合法范围内且未被访问过)。如果在任何时候,新状态等于goal,则返回当前操作数加1。如果队列变为空,说明无法到达goal,返回-1。

时间复杂度:

O(3^n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么算法中对0到1000之外的数值进行操作后就不能再进行其他操作?
在这个问题中,限制数值在0到1000范围内是为了防止数值越界并简化问题处理。在实际应用中,此范围可以视为问题的一部分规则或约束条件。超出此范围的数值可能无法保证后续操作的合法性或结果的正确性,因此,一旦数值超出这个范围,就不再将其作为有效状态加入到队列中,以避免无效计算和潜在的错误。
🦆
在算法描述中提到,如果新状态等于goal,则返回当前操作数加1,这里的加1是指什么?
这里的加1代表进行了一次操作(无论是加、减或异或)使得当前状态变为目标状态goal。因为在进入循环之前已经进行了一次操作,所以我们需要在当前的操作次数基础上加1来正确反映到达目标状态所需的总操作次数。
🦆
使用BFS进行搜索时,如何确保不会重复访问相同的状态?
为了防止重复访问相同状态,算法使用了一个集合(set)来存储已经访问过的状态。在尝试每种操作并生成新状态时,首先检查这个状态是否已经存在于集合中。如果存在,说明该状态已被处理过,就不再将它添加到队列中。这种方法可以有效避免重复处理相同状态,从而提高算法的效率。
🦆
在处理边界情况时,算法是如何确保在数值操作后仍然保持在0到1000的范围内?
算法通过在每次生成新状态后立即检查该状态是否在0到1000的合法范围内来确保数值的合法性。只有当新生成的状态符合这个范围时,才会将其添加到队列和访问过的集合中。这样可以确保所有在队列中处理的状态都是合法的,避免了处理非法或无效状态的问题。

相关问题