如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习校招总结offer选择也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 636. 函数的独占时间

力扣原题链接(点我直达) (opens new window)

给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。

每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。

日志是具有以下格式的字符串:function_id:start_or_end:timestamp。例如:"0:start:0" 表示函数 0 从 0 时刻开始运行。"0🔚0" 表示函数 0 在 0 时刻结束。

函数的独占时间定义是在该方法中花费的时间,调用其他函数花费的时间不算该函数的独占时间。你需要根据函数的 Id 有序地返回每个函数的独占时间。

示例 1:

输入: n = 2 logs = ["0:start:0", "1:start:2", "1🔚5", "0🔚6"] 输出:[3, 4] 说明: 函数 0 在时刻 0 开始,在执行了 2个时间单位结束于时刻 1。 现在函数 0 调用函数 1,函数 1 在时刻 2 开始,执行 4 个时间单位后结束于时刻 5。 函数 0 再次在时刻 6 开始执行,并在时刻 6 结束运行,从而执行了 1 个时间单位。 所以函数 0 总共的执行了 2 +1 =3 个时间单位,函数 1 总共执行了 4 个时间单位。 说明:

输入的日志会根据时间戳排序,而不是根据日志Id排序。 你的输出会根据函数Id排序,也就意味着你的输出数组中序号为 0 的元素相当于函数 0 的执行时间。 两个函数不会在同时开始或结束。 函数允许被递归调用,直到运行结束。 1 <= n <= 100

# 第一版,看了别人的思路,真的厉害

执行用时 :24 ms, 在所有 cpp 提交中击败了99.12%的用户

内存消耗 :11.2 MB, 在所有 cpp 提交中击败了100.00%的用户

 vector<int> exclusiveTime(int n, vector<string>& logs) {
    vector<int> result(n, 0);
		stack<pair<int, int>> myStack;//辅助栈,<first, second>分别代表<函数id,起始时间>
		//扫描所有log
		for (auto& log : logs) {
			string operation = "";//id的操作,“start”或者“end”
			int funcId = 0, timeStamp = 0, index = 0, logSize = log.size();//log的函数id、操作时间戳
			//第一步:读取函数id
			while (log[index] != ':') {
				funcId = funcId * 10 + log[index++] - '0';
			}
			index += 1;//跳过 : 
			//第二步:读取操作类型
			while (log[index] != ':') {
				operation += log[index++];
			}
			index += 1; //再次跳过 :
			//第三步:读取时间戳
			while (index < logSize) {
				timeStamp = timeStamp * 10 + log[index++] - '0';
			}
			//第四步:根据操作进行不同的处理
			if (operation == "start") {
				//如果是函数start,直接放入stack中
				myStack.push({ funcId, timeStamp });
			}
			else {//函数end的情况
				int runTime = timeStamp - myStack.top().second + 1;//计算栈顶id运行时间
				myStack.pop();
				result[funcId] += runTime;//加入到总时间中
				//如果此时栈还不为空,则说明当前栈顶函数里面嵌套了当前函数id,需要减去当前函数运行的时间
				if (!myStack.empty()) {
					result[myStack.top().first] -= runTime;
				}
			}
		}
		return result; 
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 第二版,自己复现一遍

执行用时 :28 ms, 在所有 cpp 提交中击败了93.86%的用户

内存消耗 :11.1 MB, 在所有 cpp 提交中击败了100.00%的用户

vector<int> exclusiveTime(int n, vector<string>& logs) {//自己复现一编
	vector<int> res(n,0);
	stack<pair<int, int>>st;//函数ID和起始时间的映射

	for (auto& log : logs) {
				
		int funID = 0, startTime = 0, logSize=log.size(), index=0;
		string opera= "";
		while (log[index] != ':') {//取的函数ID
			funID = funID * 10 + log[index++] - '0';
		}
		index++;//跳过 : 号
		//cout << "funID" << funID << endl;
		while (log[index] != ':') {//取的开始还是结束符号
			opera +=  log[index++];
		}
		//cout << "opera" << opera << endl;
		index++;//再次跳过 :号

		while (index<logSize) {//取的操作时间
			startTime = startTime * 10 + log[index++] - '0';
		}
		//cout << "startTime" << startTime << endl;
		if (opera == "start") {//存入开始时间
			st.push({ funID,startTime });
		}
		else {
			int totalRunTime = startTime - st.top().second + 1;
			//cout << "totaltime " << totalRunTime << endl;
			res[funID] += totalRunTime;//以0为中介,属于自己的就加上则减
			st.pop();
			if (!st.empty()) {
				res[st.top().first] -= totalRunTime;//不属于自己的就减去
			}
		}

	}
	return res;
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 第三种,别的方法,学到了,但是执行时间较久

学到了istringstream的法子

执行用时 :76 ms, 在所有 cpp 提交中击败了22.81%的用户

内存消耗 :11.1 MB, 在所有 cpp 提交中击败了100.00%的用户

vector<int> res(n, 0);
	stack<pair<int, int>> stk;

	for (auto &log : logs)
	{
		istringstream ss(log);//初始化一个string流
		string s1, s2, s3;
		getline(ss, s1, ':');//以 ; 为阶段符,将ss符合中的内容输入到 s1中,也就是输入了函数ID,此时ss中被取走的有s1和 “;” 
		getline(ss, s2, ':');//,将s1+";"去除后,对于剩下的ss以 ; 为阶段符,将ss符合中的内容输入到 s2中,也就是输入了start或者end
		getline(ss, s3);//,默认是以 \n 为结束符号的

		int id = stoi(s1), time = stoi(s3);
		string action = s2;
		
		if (action == "start")
		{
			if (!stk.empty())
				res[stk.top().first] += time - stk.top().second;
			stk.push({ id,time });
		}
		else
		{
			pair<int, int> p = stk.top();
			stk.pop();

			res[p.first] += time - p.second + 1;
			if (!stk.empty())
				stk.top().second = time + 1;
		}

	}

	return res;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33