C++, Build a Tree-like Struct Instead of Using Stack, 26ms


  • 0
    S

    Instead of using stack, I was thinking about building a tree-like structure in which the functions being called are the children of the caller. The difference with a tree is that here children have pointers to their parent.

    Here is the definition of the node.

    struct Node{
            int id;
            int start;
            int end;
            Node* parent;  // Pointer to parent.
            int acc;   // The accumulated sum of time cost by its children.
            Node(int i): id(i), start(-1), end(-1), parent(nullptr), acc(0){}
        };
    

    Naturally, the exclusive time of a function is end-start-1-acc.

    For every item of logs, if it is "start", we create a new child of the current node and move the current node to this child. Otherwise, we calculate the exclusive time of current node and accumulate the time to its parent node.

    class Solution {
    public:
        vector<int> exclusiveTime(int n, vector<string>& logs) {
            if(logs.empty()) return vector<int>();
    
            vector<int> res(n,0);
            Node* curr = nullptr;
            for(string log: logs){
    
                //Parse the string
                int i=0;
                while(log[i]!=':') i++;
                int id = stoi(log.substr(0,i));
                int isStart = log[++i]=='s';
                while(log[i]!=':') i++;
                int time = stoi(log.substr(++i));
                
                if(isStart){
                    Node* newNode = new Node(id);
                    newNode->start = time;
                    newNode->parent = curr;
                    curr = newNode;
                }else{
                    curr->end = time;
                    // Update the exclusive time of this function.
                    res[curr->id] +=  curr->end - curr->start + 1 - curr->acc;
                    // Accumulate its time period to its parent node.
                    if(curr->parent != nullptr){
                        curr->parent->acc += curr->end - curr->start + 1;
                    }
                    curr = curr->parent;
                }
            }
            return res;
        }
    }; 
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.