Leetcode Stack 341,636 @ Java－CONY的世界

341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

這一題要注意的地方是 NestedInteger 要在 hasNext() 裡面展開，而不是在next()

因為如果展開後沒有integer 要return false

ex.[ [ ] ] 的測資

如果是在next 裡面展開就會錯誤，因為實際上根本沒有可以return的 integer

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {

    Stack<NestedInteger> stack = new Stack();
    
    public NestedIterator(List<NestedInteger> nestedList) {
        for(int index=nestedList.size()-1; index >=0; index--)
            stack.push(nestedList.get(index));
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while(!stack.empty()){
            NestedInteger cur = stack.peek();   
            if(cur.isInteger())
                return true;
            stack.pop();
            List<NestedInteger> list = cur.getList();
            for(int index= list.size()-1; index>=0; index--)
                stack.push(list.get(index));
        }
        return false;
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

636. Exclusive Time of Functions

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.

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

因為是function call ，所以可以直覺想到用stack

function id 不是照順序的，所以要將其塞入stack 紀錄，至於時間accumulation 則可以直接累積在要return 的 int[ ]

這裡我一開始思路就是想太複雜還想說要把累積時間也塞到stack裡面，所以一開始還想說要用function id 與之前是否相同來判斷是要塞到stack 或是直接放入 int [] result

但是因為測資裡面又有像是 ex.

["0:start:0",

"0:start:2",

"0:end:4",

"0:start:6",

"0:end:7",

"0:end:8",] 因此無法work

看解答是用更簡潔的方式，因為基本上interval accumulation 就是上一段到這一段的差，所以跟function id 是沒關係的（function id 只是要讓你正確accumulation 到 int[] result )

因此所有的 start 一律把 function id 放到stack 裡面，然後藉由peek 做到正確更新上一個interval 值到累積到 return 的 int[] result 裡

然後要注意的是end 的 prev_t 要加1，因為令一個片段要從t+1算起，如果是start 就沒有這個問題

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        Stack<Integer> stack = new Stack();
        int previous_t = 0;
        int[] result = new int[n];
        for(String s:logs) {
            String[] p = s.split(":");
            int id = Integer.valueOf(p[0]), time = Integer.valueOf(p[2]);

            if(p[1].equals("start")) {
                if(!stack.empty())   result[stack.peek()] += time-previous_t; 
                stack.push(id);
                previous_t = time;
            } else {
                result[stack.pop()] += time-previous_t+1;
                previous_t = time+1;
            }
        }
        return result;
    }
}