骨骼清奇：
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
