极客笔记Java 根据B队列的执行顺序找出在A队列中执行任务所花费的时间
目标是根据B队列的执行顺序，确定完成队列A中任务所需的最小时间。给定两个大小为N的队列A和B，其中：
- 如果B队列头部的任务也是A队列头部的任务，则弹出该任务并执行。
-
如果B队列头部的任务不是A队列头部的任务，则将当前任务从A队列弹出并推入队列末尾。
-
队列中每次推入和弹出操作消耗一单位的时间，并且每个任务需要固定的时间完成。
为了解决这个问题，我们可以按照B队列给定的顺序模拟执行任务，同时跟踪A队列的当前状态。我们需要对B队列中的每个任务执行以下步骤：
- 检查B队列头部的任务是否与A队列头部的任务匹配。
-
如果任务匹配，则通过从两个队列中弹出该任务来执行它。
-
如果任务不匹配，则从A队列头部弹出任务并将其推到队列尾部。
-
每次推入和弹出操作时，将时间计数器增加1。
伪代码：
以下是execute_tasks函数的伪代码：
function execute_tasks(A, B):
time = 0
while B is not empty:
if A[0] == B[0]:
task = A.pop(0)
B.pop(0)
time = time + 1
else:
task = A.pop(0)
A.append(task)
time = time + 1
return time
请注意，这假设A和B都是代表队列的列表（或数组）。pop(0)方法从列表中删除第一个元素并返回它，而append(task)将任务添加到列表的末尾。在Python中，A[0]用于访问列表A的第一个元素。is not empty比较检查列表是否非空，而while循环会重复执行，直到B为空。
Java实现
以下是上述伪代码的Java实现。
例子
import java.util.ArrayList;
import java.util.List;
public class Main{
public static int execute_tasks(List<Integer> A, List<Integer> B) {
int time = 0;
while (!B.isEmpty()) {
if (A.get(0).equals(B.get(0))) {
int task = A.remove(0);
B.remove(0);
time++;
} else {
int task = A.remove(0);
A.add(task);
time++;
}
}
return time;
}
public static void main(String args[]) {
List<Integer> arrayList1 = new ArrayList<Integer>();
arrayList1.add(3);
arrayList1.add(2);
arrayList1.add(1);
List<Integer> arrayList2 = new ArrayList<Integer>();
arrayList2.add(1);
arrayList2.add(2);
arrayList2.add(3);
int time = Main.execute_tasks(arrayList1, arrayList2);
System.out.println("Time Taken: "+time);
}
}
输出
Time Taken: 6
该算法的时间复杂度为O(N^2)，因为我们可能需要对队列A中的每个任务迭代遍历队列B。然而，由于输入规模很小（N <= 100），这个算法对于实际目的来说应该足够高效。
- 所提供解决方案中的execute_tasks()方法的时间复杂度为O(N^2)，其中N是队列A和B的总大小。这是由于在最坏情况下，我们可能需要为队列B中的每个任务重复这个过程。对队列A执行的操作（弹出和追加）的时间复杂度为O(1)，但遍历队列A的所有任务的时间复杂度为O(N)。
-
该函数具有O(N)的空间复杂度，因为必须将列表A和B保存在内存中。任务的总数量决定了使用多少内存，而不是它们的执行顺序。时间计数器和当前任务也存储在一些常量大小的变量中，但它们对整体空间复杂度的影响很小。
使用Java Map数据结构
您可以使用Map数据结构来优化此代码，以存储队列A中任务的索引。这将允许我们在任务不在队列前端时快速查找其在A中的位置，而不必每次都搜索整个队列。
Java实现
示例
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
public class Demo{
public static int execute_tasks(List<Integer> A, List<Integer> B) {
int time = 0;
Map<Integer, Integer> taskIndex = new HashMap<>();
for (int i = 0; i < A.size(); i++) {
taskIndex.put(A.get(i), i);
}
int nextIndex = 0;
for (int i = 0; i < B.size(); i++) {
int task = B.get(i);
if (taskIndex.containsKey(task)) {
int index = taskIndex.get(task);
int numMoves = index - nextIndex;
A.remove(index);
A.add(0, task);
time += numMoves + 1;
nextIndex++;
} else {
A.remove(0);
A.add(task);
time += 2;
}
}
return time;
}
public static void main(String args[]) {
List<Integer> arrayList1 = new ArrayList<Integer>();
arrayList1.add(3);
arrayList1.add(2);
arrayList1.add(1);
List<Integer> arrayList2 = new ArrayList<Integer>();
arrayList2.add(1);
arrayList2.add(2);
arrayList2.add(3);
int time = Demo.execute_tasks(arrayList1, arrayList2);
System.out.println("Time Taken: "+time);
}
}
输出
Time Taken: 3
taskIndex() 函数用于存储A中任务的索引。函数开始的for循环通过迭代A的元素并存储它们的索引来填充这个map。nextIndex()变量用于跟踪任务在B中在A中的预期位置。
在B的for循环中，如果B中的当前任务在A中被找到，我们使用taskIndex map来找到它在A中的索引，并计算将其移到队列前面所需的移动次数。然后，我们从A中的原来位置移除该任务，将其添加到A的前面，并相应地更新时间和nextIndex。
如果B中的当前任务在A中找不到，我们只需将A中前面的任务移除，将其添加到A的末尾，并将时间更新为2。
在Python中使用map
通过使用map将A中任务的位置查找时间复杂度从O(N)减少到O(1)，从而将总体时间复杂度降低为O(N)，其中N是队列的大小。由于使用了taskIndex map，空间复杂度仍为O(N)。
实现
示例
def min_time(A, B):
time = 0
i = 0
A_set = set(A)
for b in B:
if b in A_set:
while A[i] != b:
i = (i+1) % len(A)
time += 1
time += 1
i = (i+1) % len(A)
else:
time += 1
return time
A = [3, 2, 1]
B = [1, 2, 3]
time = min_time(A, B);
print("Time Taken: ",time);
输出
Time Taken: 7