a870 - 10. List Maker
題目描述
題目要求實作一個清單操作程式，可以根據輸入的指令進行新增、插入和移除操作。輸入以 "SHOW" 指令結束，程式需要將最終清單的內容以空格分隔輸出。
解題思路
這題的核心在於處理不同指令的邏輯。使用 std::list 容器來儲存清單，因為 std::list 提供了方便的插入和刪除操作，且在插入/刪除操作時效率較高。程式迴圈讀取指令，根據指令類型執行相應的操作：
- "ADD": 將輸入的字串加到清單的末尾。
- "INSERT": 將輸入的字串插入到指定字串的前面。需要遍歷清單找到指定字串的位置。
- "REMOVE": 從清單中移除指定的字串。
- "SHOW": 結束輸入，輸出清單內容。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 是指令的數量，m 是清單的最大長度。在 "INSERT" 和 "REMOVE" 操作中，最壞情況下需要遍歷整個清單。
- 空間複雜度: O(m)，其中 m 是清單的最大長度。
程式碼
#include <iostream>
#include <list>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
list <string> ans;
string a;
while(cin >> a){
if(a=="SHOW")break;
else if(a=="ADD"){
cin >> a;
ans.push_back(a);
}
else if(a=="INSERT"){
string b;
cin >> a >> b;
for(auto it=ans.begin();it!=ans.end();++it){
if(*it==b){
ans.insert(it,a);
break;
}
}
}
else{
cin >> a;
ans.remove(a);
}
}
for(auto it=ans.begin();it!=ans.end();++it)
cout << *it << " ";
}