[C++] Solution - stack


  • 2
    /**
     * Every time end an function, deduce its life span from its parent
     */
    class Solution {
    public:
        vector<int> exclusiveTime(int n, vector<string>& logs) {
            vector<int> times(n, 0);
            stack<pair<int, int>> starters;
            for (int i = 0; i < logs.size(); i++) {
                Line line = getLine(logs[i]);
                if (line.start) {
                    starters.push({ line.fid, line.time });
                }
                else {
                    pair<int, int> starter = starters.top();
                    int lifespan = line.time + 1 - starter.second;
                    starters.pop();
                    times[line.fid] += lifespan;
                    if (!starters.empty()) {
                        times[starters.top().first] -= lifespan;
                    }
                }
            }
            return times;
        }
    
        struct Line {
            int fid;
            bool start;
            int time;
            Line(int fid, bool start, int time) : fid(fid), start(start), time(time) {};
        };
    
        Line getLine(string s) {
            int colon1 = s.find(":", 0);
            int colon2 = s.find(":", colon1 + 1);
            string fid = s.substr(0, colon1);
            string start = s.substr(colon1 + 1, colon2 - (colon1 + 1));
            string time = s.substr(colon2 + 1);
            return Line(stoi(fid), start == "start", stoi(time));
        }
    
    };
    

  • 0

    C++ different approach. I hope it's easy to understand after adding some comments.

    class Solution {
    public:
        vector<int> exclusiveTime(int n, vector<string>& logs) {
            vector<int> res(n);
            stack<pair<int, int> > stk;
            
            for (int i=0;i<logs.size();i++){
                string temp = logs[i];
                istringstream ss(temp);
                int id, time;
                string action;
                getline(ss, temp, ':');
                id = stoi(temp);
                getline(ss, temp, ':');
                action = temp;
                getline(ss, temp, ':');
                time = stoi(temp);
                
                if (action=="start"){
                    if (!stk.empty()){ //there is already a previous function so lets add the time of execution of previous function until this point
                        res[stk.top().first] += time-stk.top().second;
                    }
                    stk.push({id, time});
                }else{
                    auto curr = stk.top();
                    stk.pop();
                    res[curr.first] += time-curr.second+1;
                    if (!stk.empty()) stk.top().second = time+1; 
                    // we've already counted the time of execution of caller function before this function started. 
                    //So now we only have to account for the time between the current function's end time and caller function's end time.
                    //This is done by setting the start time for the caller function to be the end time of current function. 
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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