เวลาพิเศษของฟังก์ชันใน C++

สมมติว่าบน CPU แบบเธรดเดียว เราเรียกใช้ฟังก์ชันบางอย่าง ตอนนี้แต่ละฟังก์ชันมี id ที่ไม่ซ้ำกันระหว่าง 0 ถึง N-1 เราจะจัดเก็บบันทึกในลำดับการประทับเวลาที่อธิบายเมื่อมีการป้อนหรือออกจากฟังก์ชัน

แต่ละบันทึกจะเป็นสตริงที่เขียนรูปแบบนี้:"{function_id}:{"start" | "end"}:{timestamp}" ตัวอย่างเช่น หากสตริงเป็นเหมือน "0:start:3" แสดงว่าฟังก์ชันที่มี id 0 เริ่มต้นที่จุดเริ่มต้นของการประทับเวลา 3 "1:end:2" หมายถึงฟังก์ชันที่มี id 1 สิ้นสุดเมื่อสิ้นสุดการประทับเวลา 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 หน่วยในการดำเนินการ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ ret ขนาด n กำหนด stack st

• j :=0, ก่อนหน้า :=0

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของล็อกอาร์เรย์ – 1

  • temp :=logs[i], j :=0, id :=0, num :=0, type :=สตริงว่าง

• ในขณะที่ temp[j] ไม่ใช่โคลอน

  • id :=id * 10 + temp[j] เป็นตัวเลข

  • เพิ่มขึ้น 1

• เพิ่มขึ้น 1

• ในขณะที่ temp[j] ไม่ใช่โคลอน

  • type :=พิมพ์ concatenate temp[j]

  • เพิ่มขึ้น 1

• เพิ่มขึ้น 1

• ในขณะที่ j <ขนาดของอุณหภูมิ

  • num :=num * 10 + temp[j] เป็นตัวเลข

  • เพิ่มขึ้น 1

• ถ้า type =start แล้ว

  • ถ้า st ไม่ว่างเปล่า

    • เพิ่ม ret[stack top element] โดย num – ก่อนหน้า

  • แทรก d ลงใน st, ก่อนหน้า :=num

• อย่างอื่น

  • x :=ด้านบนของ st และลบส่วนบนของสแต็ก

  • ret[x] :=ret[x] + (num + 1) – ก่อนหน้า

  • ก่อนหน้า :=num + 1

• รีเทิร์น

ตัวอย่าง(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, ]