数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学根据B中的执行顺序查找A中任务的执行时间
目标是确定在队列A和B（大小均为N）给定的情况下，根据队列B中的执行顺序完成队列A中任务所需的最小时间。
如果在队列B头部识别的任务也在队列A头部，则弹出此任务并运行。
如果在队列B头部发现的任务未在队列A头部找到，则从队列A弹出当前任务并将其推送到末尾。
队列中的每个推送和弹出操作花费一个时间单位，每个作业的完成时间固定。
为了解决这个问题，我们可以模拟按照队列B给出的顺序执行任务，同时跟踪队列A的当前状态。对于队列B中的每个任务，我们需要执行以下步骤：
检查队列B头部任务是否与队列A头部任务匹配。
如果任务匹配，则通过从两个队列中弹出任务来执行任务。
如果任务不匹配，则从队列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)方法将task添加到列表的末尾。在Python中，可以使用A[0]访问列表A的第一个元素。非空比较检查列表是否非空，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)，因为我们可能需要为队列B中的每个任务迭代队列A中的所有任务。但是，由于输入大小较小(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的元素并存储它们的索引来填充此映射。nextIndex()变量用于跟踪B中下一个任务在A中预期的位置。
在B的for循环中，如果在A中找到B中的当前任务，我们使用taskIndex映射查找其在A中的索引并计算将其移到队列A头部所需的移动次数。然后，我们将任务从其在A中的原始位置删除，将其添加到A的头部，并相应地更新时间和nextIndex。
如果在A中找不到B中的当前任务，我们只需删除A头部任务，将其添加到A尾部，并将时间加2。
在Python中使用映射
通过使用映射存储A中任务的索引，我们将查找任务位置的时间复杂度从O(N)降低到O(1)，从而使整体时间复杂度为O(N)，其中N是队列的大小。由于使用了taskIndex映射，空间复杂度仍然是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
83 次浏览
