C++ stack and memorization one pass 26ms


  • 0
    B

    use an vector to remember start time of all functions

    class Solution {
    public:
        vector<int> exclusiveTime(int n, vector<string>& logs) {
            vector<int>ans(n, 0);
            vector<vector<int>>pool(n, vector<int>());
            stack<int>func_stk;
            for(auto & e : logs)
            {
                int idx1 = 0, idx2 = e.length()-1;
                while(e[idx1] != ':') idx1++;
                while(e[idx2] != ':') idx2--;
                int func_id = stoi(e.substr(0,idx1));
                int time_stamp = stoi(e.substr(idx2+1));
                if(e[idx1+3] == 'a')
                {
                    if(!func_stk.empty())
                    {
                        ans[func_stk.top()] += pool[func_stk.top()].back() + time_stamp;
                    }
                    func_stk.push(func_id);
                    pool[func_id].push_back(-time_stamp);
                }
                else
                {
                    ans[func_id] += pool[func_id].back() + time_stamp + 1;
                    func_stk.pop();
                    if(!func_stk.empty())
                        pool[func_stk.top()].push_back(-time_stamp - 1);
                }
            }
            return ans;
        }
    };

Log in to reply
 

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