【LeetCode教學】3508. Implement Router

設計一個能夠有效率地管理Network Router中Data Packet的資料結構。

題目連結：連結點此。

題目描述

每個packet包含以下屬性：

• source：產生packet的機器的唯一識別碼。
• destination：目標機器的唯一識別碼。
• timestamp：packet到達路由器的時間。

實作 Router class：

Router(int memoryLimit)：使用固定的記憶體限制初始化 Router 物件。

• memoryLimit是路由器在任意給定時間內可以儲存的最大packet數量。
• 如果新增packet超過此限制，則必須移除最舊的packet以釋放空間。

bool addPacket(int source, int destination, int timestamp)：將具有指定屬性的packet新增至路由器。

• 如果路由器中已存在具有相同來源、目標和時間戳記的另一個packet，則該資料包被視為重複packet。
• 如果packet新增成功（即它不是重複packet），則傳回 true；否則傳回 false。

int[] forwardPacket()：依先進先出 (FIFO) 順序轉送下一個packet。

• 從儲存中移除packet。
• 以 [source, destination, timestamp] 陣列的形式傳回packet。
• 如果沒有要轉送的packet，則傳回空陣列。

int getCount(int destination, int startTime, int endTime)：

• 傳回目前儲存在路由器中（即尚未轉送）且具有指定目標位址且timestamp在 [startTime, endTime] 範圍內的packet數量。

請注意，addPacket 的查詢將按時間戳記的升序進行。

題目限制

• 2 <= memoryLimit <= 105
• 1 <= source, destination <= 2 * 105
• 1 <= timestamp <= 109
• 1 <= startTime <= endTime <= 109
• At most 105 calls will be made to addPacket, forwardPacket, and getCount methods altogether.
• queries for addPacket will be made in increasing order of timestamp.

解題方法1：deque+tuple

簡單易懂的方法，但是對於頻繁的操作效率很低。

例如有個測試資料是操作10萬次getCount()，這時就會超過時間限制。

完整程式碼1

class Router {
private:
    deque<tuple<int, int, int>> packetStorage;  //以先進先出資料結構儲存packet，使用deque而不是queue是因為deque支援隨機存取
    int routerSize;  //packetStorage的容量
public:
    Router(int memoryLimit) {
        routerSize = memoryLimit;
    }
    
    bool addPacket(int source, int destination, int timestamp) {

        //遍歷packetStorage檢查是否有一模一樣的packet
        for (int i = 0; i < packetStorage.size(); i++)
        {   
            if (source == get<0>(packetStorage[i]) && 
                destination == get<1>(packetStorage[i]) &&
                timestamp == get<2>(packetStorage[i]))
            {
                return false;
            }
        }

        //如果packetStorage已經滿了，先把最早推入的資料移除
        if (packetStorage.size() >= routerSize) 
        {
            packetStorage.pop_front();            
        }

        //新增一個packet推入packetStorage
        packetStorage.push_back({source, destination, timestamp});
        return true;
    }
    
    vector<int> forwardPacket() {

        if (packetStorage.size() > 0)  //如果packetStorage裡面有packet
        {
            auto [source, destination, timestamp] = packetStorage.front();  //取得最早推入packetStorage的packet
            packetStorage.pop_front();  //將最早推入packetStorage的packet移除
            return {source, destination, timestamp};
        }
        else  //如果packetStorage裡面沒有packet
        {
            return {};
        }
    }
    
    int getCount(int destination, int startTime, int endTime) {

        //遍歷packetStorage尋找符合條件的packet
        int count = 0;
        for (int i = 0; i < packetStorage.size(); i++)
        {
            if (destination == get<1>(packetStorage[i]) &&
                startTime <= get<2>(packetStorage[i]) &&
                endTime >= get<2>(packetStorage[i]))
            {
                count += 1;
            }
        }
        return count;
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */

解題方法2：set+queue

針對檢查是不是重複packet的動作選用查找動作速度快的STL容器，但是對於getCount()的操作效率還是很低，會超過時間限制。

完整程式碼2

class Router {
private:
    int maxPacket;  //packet的容量
    set<vector<int>> packetSet;  //儲存封包{source,destination,timestamp}，選用查找速度快的STL容器（用來檢查重複封包）
    queue<vector<int>> packetQueue;  //儲存封包{source,destination,timestamp}，按照先後順序排列，最先推入queue的封包最先被推出

public:
    Router(int memoryLimit) {
        //指定packet的容量
        maxPacket = memoryLimit;
    }
    
    bool addPacket(int source, int destination, int timestamp) {

        vector<int> packet = {source, destination, timestamp};

        //檢查是不是重複封包
        if (packetSet.find(packet) != packetSet.end())
        {
            return false;
        }

        //檢查封包容量是否已滿
        if (packetSet.size() >= maxPacket)
        {            
            //將最早出現的封包從packetQueue移除
            vector<int> tempPacket = packetQueue.front();
            packetQueue.pop();
            
            //將最早出現的封包從packetSet移除
            packetSet.erase(tempPacket);
        }
        
        //加入此封包
        packetSet.insert(packet);
        packetQueue.push(packet);

        return true;
    }
    
    vector<int> forwardPacket() {

        //檢查packetQueue是否為空
        if (packetQueue.empty() == true) return {};

        //取得最早推入packetQueue的封包
        vector<int> forwarding = packetQueue.front();
        
        //將最早出現的封包從packetQueue移除
        packetQueue.pop();
        
        //將最早出現的封包從packetSet移除
        packetSet.erase(forwarding);
        
        //返回當前處理的封包
        return {forwarding[0], forwarding[1], forwarding[2]};
    }
    
    int getCount(int destination, int startTime, int endTime) {
        
        int result = 0;  //有幾個符合條件的封包
        queue<vector<int>> tempQueue = packetQueue;
        while (tempQueue.empty() == false)  //逐一檢查封包是否有符合條件
        {
            vector<int> tempPacket = tempQueue.front();
            tempQueue.pop();
            if (tempPacket[2] < startTime) continue;
            else if (tempPacket[2] > endTime) break;
            else if (tempPacket[1] == destination) result += 1;
        }
        return result;
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */

解題方法3：queue+unordered_map

1. 變數宣告

• 使用unordered_map<long long, bool> packetExist;儲存packet是否已經存在的資訊
  • 用來在addPacket()高效檢查是不是重複packet。
  • 將source,destination,timestamp三個數據合併成一個long long作為unordered_map的key以增加查找效率。
• 使用queue<vector<int>> packetQueue;儲存packet的完整資訊
  • packet的格式為{source,destination,timestamp}
  • 使用queue是因為可以按照先後順序排列，最先推入queue的packet最先被推出，符合forwardPacket()的需求。
• 使用unordered_map<int, vector<int>> destinationTimestamp;儲存packet的destination和timestamp資訊
  • packet的格式為{destination,timestamp}
  • 用來在getCount()可以高效查找而設計。
  • 不需要儲存source因為在getCount()內查找時只需要用到destination和timestamp的資訊。
  • 第二個成員使用vector而不是multiset是因為在getCount()內計算元素距離(數量)時的時間複雜度：對於隨機存取迭代器（如 vector），distance 是 O(1)；對於雙向迭代器（如 multiset），distance 是 O(k)。

2. 將source,destination,timestamp三個數據合併成一個long long，作為unordered_map的key。

source和destination的範圍為[1, 2*10^5]，各佔用18 bits，timestamp的範圍為[1, 10^9]，佔用30 bits，總共需要66 bits超出了long long的64 bits。

這邊規劃source使用MSB的17 bits、destination使用中間的17 bits、timestamp使用LSB的30 bits。

long long encode(int source, int destination, int timestamp)
{
    //1 <= source, destination <= 2 * 10^5, used 18 bits
    //1 <= timestamp <= 10^9, used 30 bits
    return ((long long)source << 47) | ((long long)destination << 30) | timestamp;
}

3. 建構子

在建構函式時初始化packet的容量。

Router(int memoryLimit) {
    maxPacket = memoryLimit;
}

4. 新增packet

先透過packetExist檢查是不是重複packet，如果重複的話直接返回false。

然後透過packetQueue檢查當前的packet數量是否有超出限制，如果超過的話依序將最早出現的packet從packetQueue、packetExist、destinationTimestamp三個變數中移除。

最後依序將新的packet加入packetQueue、packetExist、destinationTimestamp三個變數。

bool addPacket(int source, int destination, int timestamp) {
	//4.
	vector<int> packet = {source, destination, timestamp};

	//檢查是不是重複封包
	if (packetExist.find(encode(source, destination, timestamp)) != packetExist.end())
	{
		return false;
	}

	//檢查封包容量是否已滿
	if (packetQueue.size() >= maxPacket)
	{            
		//將最早出現的封包從packetQueue移除
		vector<int> tempPacket = packetQueue.front();
		packetQueue.pop();
		
		//將最早出現的封包從packetExist移除
		packetExist.erase(encode(tempPacket[0], tempPacket[1], tempPacket[2]));

		//將最早出現的封包從destinationTimestamp移除
		vector<int>& timestamps = destinationTimestamp[tempPacket[1]];  //在destinationTimestamp[destination]記錄了所有相同destination的封包的timestamp
		auto it = find(timestamps.begin(), timestamps.end(), tempPacket[2]);  //在destinationTimestamp[destination]尋找指定的timestamp
		timestamps.erase(it);
	}
	
	//加入此封包
	packetExist[encode(source, destination, timestamp)] = true;
	packetQueue.push(packet);
	destinationTimestamp[destination].push_back(timestamp);

	return true;
}

5. 轉送packet

先檢查packetQueue是否為空，如果為空的話就不用做下列工作直接返回空陣列。

先取得最早推入packetQueue的packet（因為稍後要返回該packet的資料），然後依序將該packet從packetQueue、packetExist、destinationTimestamp三個變數中移除。

vector<int> forwardPacket() {
	//5.forwardPacket
	//檢查packetQueue是否為空
	if (packetQueue.empty() == true) return {};

	//取得最早推入packetQueue的封包
	vector<int> forwarding = packetQueue.front();
	
	//將最早出現的封包從packetQueue移除
	packetQueue.pop();
	
	//將最早出現的封包從packetExist移除
	packetExist.erase(encode(forwarding[0], forwarding[1], forwarding[2]));
	
	//將最早出現的封包從destinationTimestamp移除
	vector<int>& timestamps = destinationTimestamp[forwarding[1]];  //在destinationTimestamp[destination]記錄了所有相同destination的封包的timestamp
	auto it = find(timestamps.begin(), timestamps.end(), forwarding[2]);  //在destinationTimestamp[destination]尋找指定的timestamp
	timestamps.erase(it);
	
	//返回當前處理的封包
	return forwarding;
}

6. 計算packet數量

我們事先在變數destinationTimestamp儲存了packet的destination和timestamp資訊，所以此時我們先找到指向destinationTimestamp[destination]的疊代器，就可以知道有多少個packet擁有相同的destination（但timestamp不同）。

然後我們需要的是一段timestamp之間的多個結果（從startTime到endTime），所以要計算有多少個packet符合這個條件。如果使用for來遍歷vector的話效率稍嫌偏低，所以這裡改用包含在C++標準函式庫<algorithm>裡面的函式lower_bound和upper_bound，lower_bound可以找到在vector裡面第一個大於等於指定條件的元素、upper_bound可以找到在vector裡面第一個大於指定條件的元素，然後利用distance計算這兩個元素的距離就可以得到有多少個packet符合條件。

例如：vector<int> example = [1,1,1,2,2,3,4,5,5,5,5,6,6,7];，auto it1 = lower_bound(example.begin(), example.end(), 2)會返回指向index 3的疊代器（第一個數值為2的元素）、auto it2 = upper_bound(example.begin(), example.end(), 5)會返回指向index 11的疊代器（第一個數值大於5的元素），最後使用distance(it1, it2)就會算出有11-3=8個元素的數值介於[2, 5]之間。

在變數宣告時使用vector而不是multiset來儲存此處的timestamp，是因為此處計算元素距離時的時間複雜度：對於隨機存取迭代器（如 vector），distance 是 O(1)；對於雙向迭代器（如 multiset），distance 是 O(k)。

另外因為題目表示packet的timestamp會是遞增的，可以視為已經由小到大排序了，所以可以使用這種計算方式。

int getCount(int destination, int startTime, int endTime) {
	//6.計算packet數量
	//尋找指向destinationTimestamp[destination]的iterator
	auto it = destinationTimestamp.find(destination);

	//找不到destinationTimestamp[destination]
	if (it == destinationTimestamp.end())
	{
		return 0;
	}
	
	//找到了destinationTimestamp[destination]，然後計算其vector<int>的每個成員有幾個是在startTime到endTime的範圍內
	const vector<int>& timestamps = it->second;
	auto lower = lower_bound(timestamps.begin(), timestamps.end(), startTime);  //因為需要的元素是在[startTime,endTime]的區間，所以先取得timestamps中第一個>=startTime的元素的iterator
	auto upper = upper_bound(timestamps.begin(), timestamps.end(), endTime);  //因為需要的元素是在[startTime,endTime]的區間，所以再取得timestamps中第一個>endTime的元素的iterator
	return distance(lower, upper);  //計算兩個iterator的距離，也就是有幾個符合條件的封包（因為有對元素排序所以可以用這種算法）
}

完整程式碼3

class Router {
private:
    //1.變數宣告
    int maxPacket;  //packet的容量
    unordered_map<long long, bool> packetExist;  //用來快速檢查重複封包，將source+destination+timestamp三個整數組合起來作為unordered_map的key，value表示當前key是否已經存在，如果key為true表示該封包已經存在了。
    queue<vector<int>> packetQueue;  //儲存封包{source,destination,timestamp}，按照先後順序排列，最先推入queue的封包最先被推出
    unordered_map<int, vector<int>> destinationTimestamp;  //儲存{destination,timestamp}，為了在getCount()可以高效率查找。第二個成員使用vector而不是multiset是因為在getCount()內計算元素距離(數量)時的時間複雜度：對於隨機存取迭代器（如 vector），distance 是 O(1)；對於雙向迭代器（如 multiset），distance 是 O(k)。

    //2.將source,destination,timestamp三個數據合併成一個long long
    long long encode(int source, int destination, int timestamp)  //將source+destination+timestamp三個整數組合起來(作為unordered_map的key)
    {
        //1 <= source, destination <= 2 * 10^5, used 18 bits
        //1 <= timestamp <= 10^9, used 30 bits
        return ((long long)source << 47) | ((long long)destination << 30) | timestamp;
    }

public:
    Router(int memoryLimit) {
        //3.初始化packet的容量
        maxPacket = memoryLimit;
    }
    
    bool addPacket(int source, int destination, int timestamp) {
        //4.加入packet
        vector<int> packet = {source, destination, timestamp};

        //檢查是不是重複封包
        if (packetExist.find(encode(source, destination, timestamp)) != packetExist.end())
        {
            return false;
        }

        //檢查封包容量是否已滿
        if (packetQueue.size() >= maxPacket)
        {            
            //將最早出現的封包從packetQueue移除
            vector<int> tempPacket = packetQueue.front();
            packetQueue.pop();
            
            //將最早出現的封包從packetExist移除
            packetExist.erase(encode(tempPacket[0], tempPacket[1], tempPacket[2]));

            //將最早出現的封包從destinationTimestamp移除
            vector<int>& timestamps = destinationTimestamp[tempPacket[1]];  //在destinationTimestamp[destination]記錄了所有相同destination的封包的timestamp
            auto it = find(timestamps.begin(), timestamps.end(), tempPacket[2]);  //在destinationTimestamp[destination]尋找指定的timestamp
            timestamps.erase(it);
        }
        
        //加入此封包
        packetExist[encode(source, destination, timestamp)] = true;
        packetQueue.push(packet);
        destinationTimestamp[destination].push_back(timestamp);

        return true;
    }
    
    vector<int> forwardPacket() {
        //5.轉送packet
        //檢查packetQueue是否為空
        if (packetQueue.empty() == true) return {};

        //取得最早推入packetQueue的封包
        vector<int> forwarding = packetQueue.front();
        
        //將最早出現的封包從packetQueue移除
        packetQueue.pop();
        
        //將最早出現的封包從packetExist移除
        packetExist.erase(encode(forwarding[0], forwarding[1], forwarding[2]));
        
        //將最早出現的封包從destinationTimestamp移除
        vector<int>& timestamps = destinationTimestamp[forwarding[1]];  //在destinationTimestamp[destination]記錄了所有相同destination的封包的timestamp
        auto it = find(timestamps.begin(), timestamps.end(), forwarding[2]);  //在destinationTimestamp[destination]尋找指定的timestamp
        timestamps.erase(it);
        
        //返回當前處理的封包
        return forwarding;
    }
    
    int getCount(int destination, int startTime, int endTime) {
        //6.計算packet數量
        //尋找指向destinationTimestamp[destination]的iterator
        auto it = destinationTimestamp.find(destination);

        //找不到destinationTimestamp[destination]
        if (it == destinationTimestamp.end())
        {
            return 0;
        }
        
        //找到了destinationTimestamp[destination]，然後計算其vector<int>的每個成員有幾個是在startTime到endTime的範圍內
        const vector<int>& timestamps = it->second;
        auto lower = lower_bound(timestamps.begin(), timestamps.end(), startTime);  //因為需要的元素是在[startTime,endTime]的區間，所以先取得timestamps中第一個>=startTime的元素的iterator
        auto upper = upper_bound(timestamps.begin(), timestamps.end(), endTime);  //因為需要的元素是在[startTime,endTime]的區間，所以再取得timestamps中第一個>endTime的元素的iterator
        return distance(lower, upper);  //計算兩個iterator的距離，也就是有幾個符合條件的封包（因為有對元素排序所以可以用這種算法）
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */

測試資料

Input:
["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]
[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]

Output:
[null, true, true, false, true, true, [2, 5, 90], true, 1]

Input:
["Router", "addPacket", "forwardPacket", "forwardPacket"]
[[2], [7, 4, 90], [], []]

Output:
[null, true, [7, 4, 90], []]

Input:
["Router","addPacket","forwardPacket","addPacket","addPacket","forwardPacket"]
[[2],[2,1,6],[],[1,2,6],[1,3,6],[]]

Output:
[null,true,[2,1,6],true,true,[1,2,6]]

Input:
["Router","addPacket","addPacket","forwardPacket","getCount"]
[[2],[5,2,4],[4,2,4],[],[2,4,4]]

Output:
[null,true,true,[5,2,4],1]

另外可以嘗試用大量執行getCount()的case測試自己寫的程式夠不夠高效，例如連續執行10萬次getCount()。

時間與空間複雜度

時間複雜度：

空間複雜度：

其他相關題目