forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
minimum-operations-to-make-a-subsequence.py
123 lines (109 loc) · 3.54 KB
/
minimum-operations-to-make-a-subsequence.py
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# Time: O(nlogn)
# Space: O(n)
import bisect
class Solution(object):
def minOperations(self, target, arr):
"""
:type target: List[int]
:type arr: List[int]
:rtype: int
"""
lookup = {x:i for i, x in enumerate(target)}
lis = []
for x in arr:
if x not in lookup:
continue
i = bisect.bisect_left(lis, lookup[x])
if i == len(lis):
lis.append(lookup[x])
else:
lis[i] = lookup[x]
return len(target)-len(lis)
# Range Maximum Query
class SegmentTree(object): # 0-based index
def __init__(self, N,
build_fn=lambda x, y: [y]*(2*x),
query_fn=lambda x, y: y if x is None else max(x, y), # (lambda x, y: y if x is None else min(x, y))
update_fn=lambda x, y: y,
default_val=0):
self.N = N
self.H = (N-1).bit_length()
self.query_fn = query_fn
self.update_fn = update_fn
self.default_val = default_val
self.tree = build_fn(N, default_val)
self.lazy = [None]*N
def __apply(self, x, val):
self.tree[x] = self.update_fn(self.tree[x], val)
if x < self.N:
self.lazy[x] = self.update_fn(self.lazy[x], val)
def update(self, L, R, h): # Time: O(logN), Space: O(N)
def pull(x):
while x > 1:
x //= 2
self.tree[x] = self.query_fn(self.tree[x*2], self.tree[x*2+1])
if self.lazy[x] is not None:
self.tree[x] = self.update_fn(self.tree[x], self.lazy[x])
L += self.N
R += self.N
L0, R0 = L, R
while L <= R:
if L & 1: # is right child
self.__apply(L, h)
L += 1
if R & 1 == 0: # is left child
self.__apply(R, h)
R -= 1
L //= 2
R //= 2
pull(L0)
pull(R0)
def query(self, L, R): # Time: O(logN), Space: O(N)
def push(x):
n = 2**self.H
while n != 1:
y = x // n
if self.lazy[y] is not None:
self.__apply(y*2, self.lazy[y])
self.__apply(y*2 + 1, self.lazy[y])
self.lazy[y] = None
n //= 2
result = None
if L > R:
return result
L += self.N
R += self.N
push(L)
push(R)
while L <= R:
if L & 1: # is right child
result = self.query_fn(result, self.tree[L])
L += 1
if R & 1 == 0: # is left child
result = self.query_fn(result, self.tree[R])
R -= 1
L //= 2
R //= 2
return result
def __str__(self):
showList = []
for i in xrange(self.N):
showList.append(self.query(i, i))
return ",".join(map(str, showList))
# Time: O(nlogn)
# Space: O(n)
# segment tree solution
class Solution2(object):
def minOperations(self, target, arr):
"""
:type target: List[int]
:type arr: List[int]
:rtype: int
"""
lookup = {x:i for i, x in enumerate(target)}
st = SegmentTree(len(lookup))
for x in arr:
if x not in lookup:
continue
st.update(lookup[x], lookup[x], st.query(0, lookup[x]-1)+1 if lookup[x] >= 1 else 1)
return len(target)-(st.query(0, len(lookup)-1) if len(lookup) >= 1 else 0)