資料結構
網路
關係資料庫管理系統 (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 次瀏覽
