Skip to content

Commit 2191a53

Browse files
wuduhrenwuduhren
committed
no message
1 parent 0de2fcf commit 2191a53

21 files changed

+626
-9
lines changed

‎problems/amount-of-new-area-painted-each-day.py‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
"""
2+
1. Build sorted records = [(position, index, isStart)...]
3+
2. Iterate through all positions and maintain a box with all the "index" of the records its position is in start ~ end
4+
3. The smallest index in the box is the actual one that is paiting.
5+
6+
Time: O(NLogN+P), N is the count of paint. Sorting the records takes NLogN. P is the max position.
7+
Although there is a while loop when iterate through P, each record is only being iterated once.
8+
O(NLogN + P + NLogN) ~= O(NLogN + P)
9+
Space: O(N)
10+
"""
11+
from sortedcontainers import SortedList
12+
13+
class Solution(object):
14+
def amountPainted(self, paint):
15+
ans = [0]*len(paint)
16+
box = SortedList()
17+
records = []
18+
maxPos = float('-inf')
19+
20+
#[1]
21+
for i, (start, end) in enumerate(paint):
22+
records.append((start, i, -1))
23+
records.append((end, i, 1))
24+
maxPos = max(maxPos, end)
25+
26+
records.sort()
27+
28+
#[2]
29+
i = 0
30+
for pos in xrange(maxPos+1):
31+
while i<len(records) and records[i][0]==pos:
32+
_, index, t = records[i]
33+
if t==-1:
34+
box.add(index)
35+
else:
36+
box.remove(index)
37+
i += 1
38+
39+
if box: ans[box[0]] += 1 #[3]
40+
return ans

‎problems/basic-calculator-ii.py‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
class Solution(object):
2+
def calculate(self, s):
3+
s += '+' #edge case, for last operation to be executed.
4+
lastOperation = '+' #edge case, for the first currNum
5+
operations = set(['+', '-', '*', '/'])
6+
7+
stack = []
8+
currNum = 0
9+
10+
for c in s:
11+
if c.isdigit():
12+
currNum = currNum*10 + int(c)
13+
elif c in operations:
14+
if lastOperation=='+':
15+
stack.append(currNum)
16+
currNum = 0
17+
elif lastOperation=='-':
18+
stack.append(-currNum)
19+
currNum = 0
20+
elif lastOperation=='*':
21+
currNum = stack.pop() * currNum
22+
stack.append(currNum)
23+
currNum = 0
24+
elif lastOperation=='/':
25+
currNum = stack.pop() / currNum
26+
if currNum<0: currNum += 1
27+
stack.append(currNum)
28+
currNum = 0
29+
lastOperation = c
30+
31+
return sum(stack)

‎problems/buildings-with-an-ocean-view.py‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
"""
2+
Traverse from the right and keep track of the highest building.
3+
4+
Time: O(N)
5+
Space: O(1)
6+
"""
7+
class Solution(object):
8+
def findBuildings(self, heights):
9+
ans = []
10+
currMaxHeight = 0
11+
for i in xrange(len(heights)-1, -1, -1):
12+
h = heights[i]
13+
if h>currMaxHeight: ans.append(i)
14+
currMaxHeight = max(currMaxHeight, h)
15+
16+
return reversed(ans)

‎problems/convert-binary-search-tree-to-sorted-doubly-linked-list.py‎

Lines changed: 25 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -103,4 +103,28 @@ def inOrderTraverse(root):
103103

104104
node = node.right
105105

106-
106+
"""
107+
Time: O(N)
108+
Space: O(LogN)
109+
"""
110+
class Solution(object):
111+
def treeToDoublyList(self, root):
112+
def helper(node):
113+
ll = rr = node
114+
if node.left:
115+
ll, lr = helper(node.left)
116+
node.left = lr
117+
lr.right = node
118+
119+
if node.right:
120+
rl, rr = helper(node.right)
121+
node.right = rl
122+
rl.left = node
123+
124+
return ll, rr
125+
126+
if not root: return root
127+
left, right = helper(root)
128+
right.right = left
129+
left.left = right
130+
return left

‎problems/custom-sort-string.py‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
"""
2+
Take a look at the char in s.
3+
For the char that is in the order, rearrange them to sortedChars with respect to the "order".
4+
For the char that is in not the order, put them in postString.
5+
"""
6+
class Solution(object):
7+
def customSortString(self, order, s):
8+
sortedChars = ''
9+
counter = collections.Counter(s)
10+
for c in order:
11+
if c in order:
12+
sortedChars += c*counter[c]
13+
14+
orderSet = set(order)
15+
postString = ''
16+
for c in s:
17+
if c not in orderSet:
18+
postString += c
19+
20+
return sortedChars+postString

‎problems/dot-product-of-two-sparse-vectors.py‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class SparseVector:
2+
def __init__(self, nums):
3+
self.indices = set()
4+
self.values = {}
5+
6+
for i, n in enumerate(nums):
7+
if n!=0:
8+
self.indices.add(i)
9+
self.values[i] = n
10+
11+
def dotProduct(self, vec):
12+
products = 0
13+
indices = self.indices.intersection(vec.indices)
14+
for i in indices:
15+
products += self.values[i]*vec.values[i]
16+
return products

‎problems/find-all-possible-recipes-from-given-supplies.py‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
"""
2+
Use Topological Sort
3+
1. Build an adj list and inbound.
4+
2. Starts from supplies topologically traverse the map.
5+
3. For each node popping up, if it is in recipes, add it to ans.
6+
7+
Time: O(N), N is the number of "nodes" (ingredients+recipes)
8+
Space: O(N).
9+
"""
10+
class Solution(object):
11+
def findAllRecipes(self, recipes, ingredients, supplies):
12+
N = len(recipes)
13+
adj = collections.defaultdict(list)
14+
inbounds = collections.Counter()
15+
q = collections.deque(supplies)
16+
recipeSet = set(recipes)
17+
ans = []
18+
19+
for i, recipe in enumerate(recipes):
20+
for ingredient in ingredients[i]:
21+
adj[ingredient].append(recipe)
22+
inbounds[recipe] += 1
23+
24+
while q:
25+
node = q.popleft()
26+
27+
if node in recipeSet: ans.append(node)
28+
29+
for nei in adj[node]:
30+
inbounds[nei] -= 1
31+
if inbounds[nei]==0: q.append(nei)
32+
33+
return ans

‎problems/k-closest-points-to-origin.py‎

Lines changed: 117 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,4 +12,120 @@ def kClosest(self, points, k):
1212
else:
1313
heapq.heappush(h, (-d, x, y))
1414

15-
return [(x, y) for _, x, y in h]
15+
return [(x, y) for _, x, y in h]
16+
17+
18+
"""
19+
1. Process `points` into `distances`.
20+
21+
2. Binary search the "distance". For every distance:
22+
Split the elements in `distances` by distance
23+
Put the ones smaller to smaller.
24+
Put the ones larger to larger.
25+
If len(smaller)<=k, then all the elements in the smaller must belong to the `ans`, do the same thing to the larger.
26+
Else we ignore the larger and do the same thing to the smaller again.
27+
28+
Time: O(N)
29+
The binary search range in average is N, N/2, N/4... = 2N
30+
Space: O(N)
31+
"""
32+
class Solution(object):
33+
def kClosest(self, points, K):
34+
#[1]
35+
maxD = float('-inf')
36+
minD = float('inf')
37+
distances = []
38+
for x, y in points:
39+
distance = ((x**2+y**2)**0.5)
40+
distances.append((distance, x, y))
41+
maxD = max(maxD, distance)
42+
minD = min(minD, distance)
43+
44+
#[2]
45+
ans = []
46+
smaller = []
47+
larger = []
48+
while K>0:
49+
#split distances into smaller and larger
50+
distance = (maxD+minD)/2
51+
for d, x, y in distances:
52+
if d<=distance:
53+
smaller.append((d, x, y))
54+
else:
55+
larger.append((d, x, y))
56+
57+
if len(smaller)<=K:
58+
ans += smaller
59+
K -= len(smaller)
60+
distances = larger
61+
minD = distance
62+
larger = []
63+
smaller = []
64+
else:
65+
distances = smaller
66+
maxD = distance
67+
larger = []
68+
smaller = []
69+
70+
return [(x, y) for _, x, y in ans]
71+
72+
73+
74+
"""
75+
Quick Select
76+
Time: O(N)
77+
Space: O(N), can be optimize to O(1).
78+
"""
79+
class Solution(object):
80+
def kClosest(self, points, K):
81+
"""
82+
Start State:
83+
i = s #next element after "SSS"s
84+
t = s #unprocessed elements
85+
j = e #next element after "LLLL"s
86+
87+
SSSPP?????LLL
88+
i t j
89+
90+
End State:
91+
SSSPPPPPLLLLL
92+
i jt
93+
"""
94+
def quickSelect(distances, s, e, k):
95+
96+
pivot = distances[(s+e)/2][0]
97+
i = s
98+
j = e
99+
t = s
100+
101+
while t<=j:
102+
if pivot<distances[t][0]:
103+
distances[t], distances[j] = distances[j], distances[t]
104+
j -= 1
105+
elif pivot>distances[t][0]:
106+
distances[t], distances[i] = distances[i], distances[t]
107+
i += 1
108+
t += 1
109+
else:
110+
t += 1
111+
112+
if i-s>=k:
113+
return quickSelect(distances, s, i, k)
114+
elif j-s+1>=k:
115+
return pivot
116+
else:
117+
return quickSelect(distances, t, e, k-(t-s))
118+
119+
distances = []
120+
for x, y in points:
121+
distance = ((x**2+y**2)**0.5)
122+
distances.append((distance, x, y))
123+
124+
kthSmallestDistance = quickSelect(distances, 0, len(distances)-1, K)
125+
126+
ans = []
127+
for d, x, y in distances:
128+
if len(ans)==K: break
129+
if d<=kthSmallestDistance: ans.append((x, y))
130+
131+
return ans

‎problems/longest-increasing-path-in-a-matrix.py‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
class Solution(object):
2+
def longestIncreasingPath(self, matrix):
3+
def getLongest(i, j):
4+
if (i, j) in longest: return longest[(i, j)]
5+
l = 1
6+
7+
#call getLongest to the neighbors that are larger than itself.
8+
if i+1<M and matrix[i][j]<matrix[i+1][j]:
9+
l = max(l, 1+getLongest(i+1, j))
10+
if i-1>=0 and matrix[i][j]<matrix[i-1][j]:
11+
l = max(l, 1+getLongest(i-1, j))
12+
if j+1<N and matrix[i][j]<matrix[i][j+1]:
13+
l = max(l, 1+getLongest(i, j+1))
14+
if j-1>=0 and matrix[i][j]<matrix[i][j-1]:
15+
l = max(l, 1+getLongest(i, j-1))
16+
17+
longest[(i, j)] = l
18+
self.ans = max(self.ans, l)
19+
return l
20+
21+
M = len(matrix)
22+
N = len(matrix[0])
23+
24+
longest = {}
25+
self.ans = float('-inf')
26+
27+
for i in xrange(M):
28+
for j in xrange(N):
29+
getLongest(i, j)
30+
31+
return self.ans

0 commit comments

Comments
 (0)