CodingQuestion/src/LeetCode-636-Exclusive-Time-of-Functions.java at master · drinkbeer/CodingQuestion · GitHub

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
    /*
    https://leetcode.com/problems/exclusive-time-of-functions/discuss/293215/Simple-Java-solution-using-Stack
    https://leetcode.com/problems/exclusive-time-of-functions/discuss/105084/How-is-function-1-executing-4-units-of-time

    */
//     public int[] exclusiveTime(int n, List<String> logs) {
//         if (n == 0 || logs.size() == 0) return new int[0];

//         List<Pair> pairs = new ArrayList<>();
//         for (String str : logs) {
//             pairs.add(parseLogs(str));
//         }

//         Stack<Pair> stack = new Stack<>();
//         int[] res = new int[n];
//         int prevStartTime = 0;
//         for (Pair p : pairs) {
//             if ("start".equals(p.sign)) {
//                 if (!stack.isEmpty()) {
//                     Pair prev = stack.peek();
//                     res[prev.id] += p.time - prevStartTime;
//                 }

//                 stack.push(p);
//                 prevStartTime = p.time;
//             } else {
//                 Pair start = stack.pop();   // start.id must equals p.id
//                 res[p.id] += p.time - prevStartTime + 1;
//                 prevStartTime = p.time + 1;
//             }
//         }

//         return res;
//     }

//     private Pair parseLogs(String log) {
//         String[] strs = log.split(":");
//         int id = Integer.parseInt(strs[0]);
//         String sign = strs[1];
//         int time = Integer.parseInt(strs[2]);
//         return new Pair(id, sign, time);
//     }

//     private class Pair {
//         int id;
//         String sign;
//         int time;

//         public Pair(int id, String sign, int time) {
//             this.id = id;
//             this.sign = sign;
//             this.time = time;
//         }
//     }

    public int[] exclusiveTime(int n, List<String> logs) {
        if (n == 0 || logs.size() == 0) return new int[0];

        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        int prevStartTime = 0;
        for (String s : logs) {
            String[] strs = s.split(":");
            int id = Integer.parseInt(strs[0]);
            int time =  Integer.parseInt(strs[2]);

            if ("start".equals(strs[1])) {
                if (!stack.isEmpty()) {
                    res[stack.peek()] += time - prevStartTime; // time should not be included
                }

                stack.push(id);
                prevStartTime = time;
            } else {
                res[stack.pop()] += time - prevStartTime + 1;
                prevStartTime = time + 1;
            }
        }

        return res;
    }
}