ExclusiveTimeOfFunctions [source code]
public class ExclusiveTimeOfFunctions {
static
/******************************************************************************/
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
Deque<int[]> stack = new ArrayDeque<> ();
for (String s : logs) {
int[] log = parseLog (s);
if (log[1] <= 0)
stack.offerLast (log);
else {
int[] startLog = stack.pollLast ();
assert startLog[0] == log[0];
int curLen = log[1] + startLog[1];
res[log[0]] += curLen;
// Moore voting style update for immediately overarching function's exclusive time
if (!stack.isEmpty ())
res[stack.peekLast ()[0]] -= curLen;
}
}
return res;
}
/* Parse a log, return int[2]{ID, VAL}
1. ID: the id of the job
2. VAL: the time value. if this log is a START, then VAL is -start_time, rather if it's an END
log, then VAL = end_time + 1. This ensures easier calculations later: length = val_start + val_end */
public int[] parseLog (String log) {
String[] tokens = log.split ("\\:");
assert tokens.length == 3;
int id = -1, num = -1;
try {
id = Integer.parseInt (tokens[0]);
num = Integer.parseInt (tokens[2]);
} catch (Exception e) {
e.printStackTrace ();
}
assert id >= 0 && num >= 0;
if (tokens[1].equals ("start"))
return new int[] {id, -num};
else
return new int[] {id, num + 1};
}
}
/******************************************************************************/
public static void main(String[] args) {
ExclusiveTimeOfFunctions.Solution tester = new ExclusiveTimeOfFunctions.Solution();
String[][] inputs = {
{"2"}, {"0:start:0","1:start:2","1:end:5","0:end:6"},
{"1"}, {"0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"},
{"2"}, {"0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"},
{"8"}, {"0:start:0","1:start:5","2:start:6","3:start:9","4:start:11","5:start:12","6:start:14","7:start:15","1:start:24","1:end:29","7:end:34","6:end:37","5:end:39","4:end:40","3:end:45","0:start:49","0:end:54","5:start:55","5:end:59","4:start:63","4:end:66","2:start:69","2:end:70","2:start:74","6:start:78","0:start:79","0:end:80","6:end:85","1:start:89","1:end:93","2:end:96","2:end:100","1:end:102","2:start:105","2:end:109","0:end:114"},
};
int[][] answers = {
{3, 4},
{8},
{7, 1},
{20,14,35,7,6,9,10,14},
};
for (int i = 0; i < inputs.length / 2; i++) {
int n = Integer.parseInt (inputs[2 * i][0]);
List<String> logs = Arrays.asList (inputs[2 * i + 1]);
int[] ans = answers[i];
String ansStr = Printer.array (ans);
System.out.println (Printer.separator ());
int[] output = tester.exclusiveTime (n, logs);
String outputStr = Printer.array (output);
System.out.printf ("%d and [%s] -> [%s], expected: [%s]\n",
n, Printer.array (inputs[2 * i + 1]), Printer.wrapColor (outputStr, outputStr.equals (ansStr) ? "green" : "red"), ansStr
);
}
}
static String printStack (Deque<int[]> stack) {
StringBuilder sb = new StringBuilder ();
for (int[] log : stack)
sb.append (String.format ("(%d=%d) ", log[0], log[1]));
return sb.toString ();
}
}
这题刚拿到的时候还是有点吓人的, 因为害怕有类似[0,4] and [2,7]这样的interval组合出现; 但是仔细阅读题目意思之后, 发现隐藏条件, 既然是一个单线程CPU的log, 那么是否可以假设, 不存在这种overlap的存在? 所有的job之间应该是完整的包含关系; 如果这个假设成立, 那么我们就有一个很明确的括号结构.
这题如果timestamp的range有限制, 我倒是有一个简单的思路, 直接logs走一遍, 然后用一个override的思路, 给每一个time unit都label上一个latest job id, 然后最后专门给这个time数轴走一遍, 丢到最后的结果里面就行了; 不过因为这里并没有给出这样一个range, 所以这个方法未必行得通;
既然是括号结构, 想到用Stack来做应该也不是那么难;
这题写的时候发现的一个难点在于, 怎么完成这个exclusive的过程, 也就是完成不同的ID的时间归属的区分; 刚开始以为很简单, 保留一个prevLen, 然后每次一个pop之后, 直接算出长度然后减去prevLen就行了, 但是事实证明这个逻辑是完全有问题的;
这是这个时候的代码:
public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
Deque<int[]> stack = new ArrayDeque<> ();
for (String s : logs) {
int[] log = parseLog (s);
if (log[2] < 0)
stack.offerLast (log);
else {
int[] startLog = stack.pollLast ();
assert startLog[0] == log[0];
int curLen = log[2] - startLog[1];
res[log[0]] += curLen - prevLen;
prevLen = curLen;
}
}
return res;
}
后来大概想到一个思路, 就是不能只把end看成是一个switch, 而应该把push(start)也看成是一个switch;
这个方法不行; 不过想了半天, 终于想到一个感觉可行的办法; 这是一个类似Moore voting的思路: 每当完成一个interval的时候, 不仅increase被完成的这个job的结果, 而且decrease peek位置, 也就是刚完成的这个job的直接parent, 的结果;
按理说这个办法其实是挺聪明的, 不过最后这个办法还是让我debug了半天, 原因是我这个是第次使用Deque, 所以对API不熟悉; 我在有一行用peek, 实际上应该用peekLast: peek默认好像是peekFirst.
搜了一下, 就算是Deque当Stack用的时候, 其实也是可以直接用Stack原来的peek/push/pop的API的, 这样就比较不容易犯错; 当然, 掌握最本质的两头的API肯定是更有利的;
最后的速度是41ms (87%), 很不错;
editorial
Approach #1 Using Stack [Time Limit Exceeded]
public class Solution {
public int[] exclusiveTime(int n, List < String > logs) {
Stack < Integer > stack = new Stack < > ();
int[] res = new int[n];
String[] s = logs.get(0).split(":");
stack.push(Integer.parseInt(s[0]));
int i = 1, time = Integer.parseInt(s[2]);
while (i < logs.size()) {
s = logs.get(i).split(":");
while (time < Integer.parseInt(s[2])) {
res[stack.peek()]++;
time++;
}
if (s[1].equals("start"))
stack.push(Integer.parseInt(s[0]));
else {
res[stack.peek()]++;
time++;
stack.pop();
}
i++;
}
return res;
}
}
这个思路就是一个有点类似我一开始的简单的想法的一个扫描线的做法, 自然, 这个复杂度最后会是O(largest timestamp), 这个就太坑了; 所以最后很直接的就TLE了;
但是这个好像是可以解决的, 他的下一个做法就是这样:
Approach #2 Better Approach [Accepted]
public class Solution {
public int[] exclusiveTime(int n, List < String > logs) {
Stack < Integer > stack = new Stack < > ();
int[] res = new int[n];
String[] s = logs.get(0).split(":");
stack.push(Integer.parseInt(s[0]));
int i = 1, prev = Integer.parseInt(s[2]);
while (i < logs.size()) {
s = logs.get(i).split(":");
if (s[1].equals("start")) {
if (!stack.isEmpty())
res[stack.peek()] += Integer.parseInt(s[2]) - prev;
stack.push(Integer.parseInt(s[0]));
prev = Integer.parseInt(s[2]);
} else {
res[stack.peek()] += Integer.parseInt(s[2]) - prev + 1;
stack.pop();
prev = Integer.parseInt(s[2]) + 1;
}
i++;
}
return res;
}
}
总体还是一个不错的算法, prev用来记录之前的时间, 最后完成一个对时间轴进行分段的操作; 无论新来的是一个start还是end, 都对前一段进行收尾, 更新, 然后更新prev本身, 所以这个最后完成的就是一个一段一段的操作; 不过因为是用数学差值来更新, 所以最后的复杂度其实是O(N), N是log的个数;
discussion最优解:
public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
int prevTime = 0;
for (String log : logs) {
String[] parts = log.split(":");
if (!stack.isEmpty()) res[stack.peek()] += Integer.parseInt(parts[2]) - prevTime;
prevTime = Integer.parseInt(parts[2]);
if (parts[1].equals("start")) stack.push(Integer.parseInt(parts[0]));
else {
res[stack.pop()]++;
prevTime++;
}
}
return res;
}
也是这个扫描线的做法;
awice在discussion的解法:
@awice said in Python, Straightforward with Explanation:
We examine two approaches - both will be stack based.
In a more conventional approach, let's look between adjacent events, with duration
time - prev_time. If we started a function, and we have a function in the background, then it was running during this time. Otherwise, we ended the function that is most recent in our stack.def exclusiveTime(self, N, logs): ans = [0] * N stack = [] prev_time = 0 for log in logs: fn, typ, time = log.split(':') fn, time = int(fn), int(time) if typ == 'start': if stack: ans[stack[-1]] += time - prev_time stack.append(fn) prev_time = time else: ans[stack.pop()] += time - prev_time + 1 prev_time = time + 1 return ans
In the second approach, we try to record the "penalty" a function takes. For example, if function 0 is running at time [1, 10], and function 1 runs at time [3, 5], then we know function 0 ran for 10 units of time, less a 3 unit penalty. The idea is this: Whenever a function completes using T time, any functions that were running in the background take a penalty of T. Here is a slow version to illustrate the idea:
def exclusiveTime(self, N, logs): ans = [0] * N #stack = SuperStack() stack = [] for log in logs: fn, typ, time = log.split(':') fn, time = int(fn), int(time) if typ == 'start': stack.append(time) else: delta = time - stack.pop() + 1 ans[fn] += delta #stack.add_across(delta) stack = [t+delta for t in stack] #inefficient return ansThis code already ACs, but it isn't efficient. However, we can easily upgrade our stack to a "superstack" that supports
self.add_across: addition over the whole array in constant time.class SuperStack(object): def __init__(self): self.A = [] def append(self, x): self.A.append([x, 0]) def pop(self): x, y = self.A.pop() if self.A: self.A[-1][1] += y return x + y def add_across(self, y): if self.A: self.A[-1][1] += y
虽然是Python, 但是他第二个算法的思路跟我几乎是一样的. 这个人真的是厉害;
submission最优解: 27(100):
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
Deque<int[]> deque = new LinkedList<int[]>();
for (String log : logs) {
int index_1 = log.indexOf(":");
int index_2 = log.indexOf(":", index_1 + 1);
int curNum = Integer.parseInt(log.substring(0, index_1));
int curTimestamp = Integer.parseInt(log.substring(index_2 + 1, log.length()));
if (index_2 - index_1 > 5) {
if (!deque.isEmpty()) {
int[] top = deque.peek();
res[top[0]] += curTimestamp - top[1];
}
deque.push(new int[] {curNum, curTimestamp});
} else {
int[] top = deque.poll();
res[curNum] += curTimestamp - top[1] + 1;
if (!deque.isEmpty()) {
top = deque.peek();
top[1] = curTimestamp + 1;
}
}
}
return res;
}
}
其实还是一个扫描线的做法, 不过写的比较简练, 而且避免多次使用string的equals之类的操作;
不对, 这个不是扫描线的做法, 这个做法其实我自己大概想到了; 当你拿到一个start的时候, 直接将overarching job的时间全部都更新进去; 然后当你拿到一个end的时候, 除了完成并更新当前peek位置的这个job, 对于上面的parent, 要进行一个修改更新: 重新开始于当前时间; 这样任何被隔断的job, 实际上更新被分成了好几段. 这个其实也是一个挺subtle的解法, 不过我当时是真的几乎有这个想法. 当然我当时能不能真的写出来他这么整齐的一个代码, 也很难说了;
Problem Description
Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.
Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.
A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.
注意看他这里的表述, 他这里对于某一个time数字, 也要区分begin和end, 这个说明你对一个time的理解应该是一个interval一样的东西, 类似是数轴上面的一个小段, 而不是一个单纯的点point;
在实际写代码的时候, 发现这个定义可以统一化(现在start是一个time的begin, end是一个time的end, 这两者就类似index和length之间, 不是一类变量). 统一的办法也很简单, 直接就是比如end at 6, 其实就是等价于begin at 7. 这样所有出现的数字都是统一代表一个unit interval的begin的那个点.
Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their function id.
Example 1:
Input:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.
Note:
- Input logs will be sorted by timestamp, NOT log id.
- Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
- Two functions won't start or end at the same time.
- Functions could be called recursively, and will always end.
- 1 <= n <= 100
Difficulty:Medium
Total Accepted:11.2K
Total Submissions:25.2K
Contributor:fallcreek
Companies
facebookuber
Related Topics
stack