C++での関数の排他時間

シングルスレッドCPUで、いくつかの関数を実行するとします。これで、各関数のIDは0からN-1の間で一意になります。関数がいつ開始または終了したかを説明するタイムスタンプ順にログを保存します。

ここで、各ログは次の形式で記述された文字列です： "{function_id}：{"start "|" end "}：{timestamp}"。たとえば、文字列が「0：start：3」の場合、これはID 0の関数がタイムスタンプ3の開始時に開始されたことを意味します。「1：end：2」はID1の関数がタイムスタンプの終了時に終了したことを意味します。 2.関数の排他時間は、この関数で費やされた時間の単位数です。

したがって、入力がn =2で、logs =["0：start：0"、 "1：start：2"、 "1：end：5"、 "0：end：6"]の場合、出力は次のようになります。 [3,4]になります。これは、関数0が時間0の開始時に開始し、次に2単位の時間を実行し、時間1の終了に達するためです。その後、関数1は時間2の開始時に開始し、4単位の時間を実行し、時間5で終了します。 。関数0は、時間6の開始時に再び実行され、時間6の終了時にも終了するため、1単位時間実行されます。したがって、関数0は2 + 1 =3単位の合計実行時間を費やし、関数1は4単位の合計実行時間を費やしていることがわかります。

これを解決するには、次の手順に従います-

• サイズnの配列retを定義し、スタックstを定義します

• j：=0、前：=0

• 0からログ配列のサイズまでの範囲のiの場合– 1

  • temp：=logs [i]、j：=0、id：=0、num：=0、type：=empty string

• temp[j]はコロンではありません

  • id：=id * 10 + temp [j] as number

  • jを1増やします

• jを1増やします

• temp[j]はコロンではありません

  • type：=type concatenate temp [j]

  • jを1増やします

• jを1増やします

• 一方、j<温度のサイズ

  • num：=num * 10 + temp [j] as number

  • jを1増やします

• type =startの場合、

  • stが空でない場合

    • ret [スタックトップ要素]をnumだけ増やします– prev

  • dをstに挿入します。prev：=num

• それ以外の場合

  • x：=stの最上位、およびスタックの最上位を削除

  • ret [x]：=ret [x] +（num + 1）– prev

  • 前：=num + 1

• retを返す

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> exclusiveTime(int n, vector<string>& logs) {
      vector <int> ret(n);
      stack <int> st;
      int id, num;
      int j = 0;
      string temp;
      string type;
      int prev = 0;
      for(int i = 0; i < logs.size(); i++){
         temp = logs[i];
         j = 0;
         id = 0;
         num = 0;
         type = "";
         while(temp[j] != ':'){
            id = id * 10 + (temp[j] - '0');
            j++;
         }
         j++;
         while(temp[j] != ':'){
            type += temp[j];
            j++;
         }
         j++;
         while(j < temp.size()){
            num = num * 10 + temp[j] - '0';
            j++;
         }
         if(type == "start"){
            if(!st.empty()){
               ret[st.top()] += num - prev;
            }
            st.push(id);
            prev = num;
         } else {
            int x = st.top();
            st.pop();
            ret[x] += (num + 1) - prev;
            prev = num + 1;
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"0:start:0","1:start:2","1:end:5","0:end:6"};
   Solution ob;
   print_vector(ob.exclusiveTime(2, v));
}

入力

2
["0:start:0","1:start:2","1:end:5","0:end:6"]

出力

[3, 4, ]