Stack真题

骨骼清奇：
LC 394 Decode String
LC 844 Backspace String Compare
LC 341 Flatten Nested List Iterator

Uber:
LC 636 Exclusive Time of Functions

LC 394 Decode String
s = "3[a2[c]]", return "accaccacc".

class Solution(object):
    def decodeString(self, s):
        stack = []
        stack.append(["", 1])
        #This number 1 here is not used
        num = ""
        for ch in s:
            if ch.isdigit():
                num += ch
            elif ch == '[':
                stack.append(["", int(num)])
                num = ""
            elif ch == ']':
                st, k = stack.pop()
                stack[-1][0] += st*k
            else:
                stack[-1][0] += ch
        return stack[0][0]

LC 844 Backspace String Compare
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Method one: build string, but space is not O(1)

class Solution(object):
    def backspaceCompare(self, S, T):
        def build(S):
            ans = []
            for c in S:
                if c != '#':
                    ans.append(c)
                elif ans:
                    ans.pop()
            return "".join(ans)
        return build(S) == build(T)

Method 2: reduce function

functools.reduce(func, iter, [initial_value]) cumulatively performs an operation on all the iterable’s elements.

In order to handle below cases, we should set initial value as ""
"a##c"
"#a#c"
Output: True

class Solution(object):
    def backspaceCompare(self, S, T):
        from functools import reduce
        backspace = lambda s,nextc:s[:-1] if nextc=="#" else s+nextc
        return reduce(backspace,S,"")==reduce(backspace,T,"")

Follow up: Can you solve it in O(N) time and O(1) space?
If we do it backward, when we meet a char and we can be sure this char won't be deleted. If we meet a '#', it tell us we need to skip next lowercase char.

class Solution:
    def backspaceCompare(self, S, T):
        si, ti = len(S) - 1, len(T) - 1
        skip_s = skip_t = 0
        
        while si >= 0 or ti >= 0:
            # si stops at non-deleted character in S or -1
            while si >= 0:
                if S[si] == '#':
                    skip_s += 1
                    si -= 1
                elif S[si] != '#' and skip_s > 0:
                    skip_s -= 1
                    si -= 1
                else:
                    break
            
            # ti stops at non-deleted character in T or -1
            while ti >= 0:
                if T[ti] == '#':
                    skip_t += 1
                    ti -= 1
                elif T[ti] != '#' and skip_t > 0:
                    skip_t -= 1
                    ti -= 1
                else:
                    break

            if (ti < 0 and si >= 0) or (si < 0 and ti >= 0):
                # eg. S = "a#", T = "a" 
                return False
            if (ti >= 0 and si >= 0) and S[si] != T[ti]:
                return False
            
            si -= 1
            ti -= 1
        return True

构造一个iterator, 每次yield都是没有被删除的字母！

class Solution(object):
    def backspaceCompare(self, S, T):
        def F(S):
            skip = 0
            for x in reversed(S):
                if x == '#':
                    skip += 1
                elif skip:
                    skip -= 1
                else:
                    yield x

        return all(x == y for x, y in itertools.zip_longest(F(S), F(T)))

LC 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.
NestedInteger有isinteger(), getinteger(),getlist()
Your NestedIterator object will be instantiated and called as such:
i, v = NestedIterator(nestedList), []
while i.hasNext(): v.append(i.next())

LC 636 Exclusive Time of Functions
Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU.

Method 1 : Stack holds the starting time of each function that has been called. We has the elapsed time to the starting time to exclude it from calculation.

def exclusiveTime(self, N, logs):
    ans = [0] * N
    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 = [t+delta for t in stack]

    return ans

Actually, function A only care about the very first function that starts and ends during its own run-time, say they are function B and C. B and C both run during the run time of A respectively. A does not care if there will be function called in B or C. So we can augment our stack to keep track of the raw run time of B and C and that is the time when A does to sleep.

class Solution(object):
    def exclusiveTime(self, n, logs):
        ans = [0] * n
        stack = []
        
        for log in logs:
            fid, state, time = log.split(':')
            fid , time = int(fid),int(time)
            
            if state == 'start':
                stack.append([time, 0])
            else:
                start_time, off_time = stack.pop()
                ans[fid] += time - start_time + 1 - off_time
                if stack:  #already started
                    stack[-1][1] += time - start_time + 1
        return ans