Skip to content

Commit 7bd382c

Browse files
Chris WuChris Wu
Chris Wu
authored and
Chris Wu
committed
no message
1 parent 0ec60f6 commit 7bd382c

7 files changed

Lines changed: 247 additions & 5 deletions

‎clone-graph.py‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
"""
2+
approach 2 is more easy to understand
3+
but approach 1 is better, since it only iterate once
4+
both of them are O(N) in time efficiency and O(N) in space efficiency
5+
6+
1.
7+
in 'clone' we store original and clone node as key value pair [0]
8+
in 'stack' we store the original node which its clone is generated but the clone's neighbors isn't set yet [1]
9+
we pop the node in the stack and set its clone's neighbors [2]
10+
if the neighbor is not generated before we generate a clone and push it to stack [3]
11+
by this way we are basically traverse the graph by DFS
12+
13+
2.
14+
we traverse every node in the graph
15+
if a node's neighbor is not in clone, which means it hasn't been visit yet, we add it to stack
16+
by this way we have every node and its clone in the 'clone' dictionary now [0]
17+
18+
we iterate every node in the clone and setup its neighbors [1]
19+
"""
20+
class Solution(object):
21+
def cloneGraph(self, start):
22+
if start==None: return start
23+
clone = {} #[0]
24+
stack = [] #[1]
25+
26+
clone[start] = Node(start.val, [])
27+
stack.append(start)
28+
29+
while stack:
30+
node = stack.pop()
31+
for nb in node.neighbors:
32+
if nb not in clone: #[3]
33+
clone[nb] = Node(nb.val, [])
34+
stack.append(nb)
35+
clone[node].neighbors.append(clone[nb]) #[2]
36+
37+
return clone[start]
38+
39+
class Solution(object):
40+
def cloneGraph(self, start):
41+
clone = {}
42+
stack = [start]
43+
44+
while stack: #[0]
45+
node = stack.pop()
46+
if node not in clone:
47+
clone[node] = Node(node.val, [])
48+
for nb in node.neighbors:
49+
stack.append(nb)
50+
51+
for node in clone: #[1]
52+
for nb in node.neighbors:
53+
clone[node].neighbors.append(clone[nb])
54+
55+
return clone[start]
56+
57+
58+
59+
60+
61+
62+
63+
64+
65+
66+

‎evaluate-division.py‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
"""
2+
I learn the solution from @mlaw0.
3+
He used BFS, so I use DFS. The runtime is almost the same.
4+
But I think BFS is more suitable in this case, bc we don't have to go down that deep.
5+
6+
we know if a/b=2, b/c=3, then
7+
1. b/a=1/2, c/b=1/3 [2]
8+
2. a/c=2*3, becasue (a/b)*(b/c)=a/c=2*3
9+
we can build graph: a->(b, 2), b->(c, 3).
10+
a->(b, 2) means a-->2-->b
11+
b->(c, 3) means b-->3-->c
12+
so if we need a/c, we are finding a-->?-->c, which is a-->2-->b-->3-->c, which is a-->2*3-->c
13+
14+
first we build the graph [0]
15+
for every query, we find from the starting point (n1) itself [1]
16+
in the stack is the next thing we want to check if it is n2
17+
we keep on pushing neighbor or neighbor's neighbor to the stack until we find n2 [3]
18+
19+
to prevent we visit the visited node we use a set to keep track [4]
20+
21+
we can further optimize the answer by updating the graph at the same time
22+
bc it is not likely that we build the graph for a single search [5]
23+
"""
24+
class Solution(object):
25+
def calcEquation(self, equations, values, queries):
26+
def findVal(query):
27+
n1, n2 = query
28+
if n1 not in graph or n2 not in graph: return -1.0
29+
30+
stack = [(n1, 1.0)] #[1]
31+
visited = set() #[4]
32+
33+
while stack:
34+
n, val = stack.pop()
35+
visited.add(n)
36+
if n==n2:
37+
return val
38+
else:
39+
for nb, nb_val in graph[n]: #nb means neighbor
40+
if nb not in visited:
41+
stack.append((nb, nb_val*val)) #[3]
42+
if n!=n1: graph[n1].append((nb, nb_val*val)) #[5]
43+
return -1.0
44+
45+
def addEdge(n1, n2, val):
46+
if n1 in graph:
47+
graph[n1].append((n2, val))
48+
else:
49+
graph[n1] = [(n2, val)]
50+
51+
#[0]
52+
graph = {}
53+
for (n1, n2), val in zip(equations, values):
54+
addEdge(n1, n2, val)
55+
addEdge(n2, n1, 1/val)
56+
57+
return [findVal(query) for query in queries]
58+

‎evaluate-reverse-polish-notation.py‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
"""
2+
iterate through the tokens
3+
4+
if the token is +-*/
5+
then take out two operands to calculate with the operator
6+
put the result to stack
7+
(take 2 operands out bc +-*/ are all binary operator)
8+
9+
if the token is operands
10+
put it to stack
11+
12+
the final answer should be the one left in the stack
13+
"""
14+
class Solution(object):
15+
def evalRPN(self, tokens):
16+
def calculate(operator, n1, n2):
17+
if operator=='+':
18+
return n2+n1
19+
elif operator=='-':
20+
return n2-n1
21+
elif operator=='*':
22+
return n2*n1
23+
elif operator=='/' and n1!=0:
24+
#by description
25+
#division between two integers should truncate toward zero.
26+
if n2%n1!=0:
27+
return int(n2/float(n1))
28+
else:
29+
return n2/n1
30+
else:
31+
print('ERROR')
32+
33+
stack = []
34+
35+
for t in tokens:
36+
if t in '+-*/':
37+
stack.append(calculate(t, stack.pop(), stack.pop()))
38+
else:
39+
stack.append(int(t))
40+
return stack.pop()

‎min-stack.py‎

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2,23 +2,26 @@
22
class MinStack(object):
33

44
def __init__(self):
5-
self.s = []
5+
self.stack = []
66

77

88
def push(self, x):
9-
self.s.append(x)
9+
self.stack.append((x, min(x, self.getMin())))
1010

1111

1212
def pop(self):
13-
self.s.pop(len(self.s)-1)
13+
if len(self.stack)==0: return None
14+
return self.stack.pop()[0]
1415

1516

1617
def top(self):
17-
return self.s[len(self.s)-1]
18+
if len(self.stack)==0: return None
19+
return self.stack[-1][0]
1820

1921

2022
def getMin(self):
21-
return min(self.s)
23+
if len(self.stack)==0: return float('inf')
24+
return self.stack[-1][1]
2225

2326

2427

‎moving-average-from-data-stream.py‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class MovingAverage(object):
2+
3+
def __init__(self, size):
4+
self.queue = collections.deque()
5+
self.size = size
6+
self.sum = 0
7+
8+
def next(self, val):
9+
self.queue.append(val)
10+
11+
if len(self.queue)>self.size:
12+
self.sum = self.sum+val-self.queue.popleft()
13+
else:
14+
self.sum = self.sum+val
15+
16+
return self.sum/float(len(self.queue))

‎number-of-recent-calls.py‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
"""
2+
everytime we ping
3+
we put the t in the queue
4+
5+
and check the leftmost(smallest) if it is in the range of 3000
6+
if it is out of range, pop it, we don't need it anymore
7+
bc it would definitely be out of range for the next ping
8+
and bc the description says t is strictly increasing
9+
keep do the same until the leftmost is in the range
10+
11+
now all the value in the queue is in the range
12+
return the length of the queue
13+
"""
14+
from collections import deque
15+
class RecentCounter(object):
16+
def __init__(self):
17+
self.q = collections.deque()
18+
19+
def ping(self, t):
20+
self.q.append(t)
21+
while len(self.q)>0 and self.q[0]<t-3000:
22+
self.q.popleft()
23+
24+
return len(self.q)

‎task-scheduler.py‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
"""
2+
Here is what I learn from @awice and solution approach 3.
3+
4+
There are two cases: #[0]
5+
if n is small enough for all tasks to run without idle the answer would be len(tasks)
6+
if n is not small enough
7+
it would be like the Figure 2 in https://leetcode.com/problems/task-scheduler/Figures/621_Task_Scheduler_new.PNG
8+
the answer of the case2 is the number of total number of square in the Figure 2
9+
10+
in Figure 2, we can see
11+
n (cooling interval) is 4
12+
max_count is 4, max_count is the max number of each task that is going to be executed
13+
t is 2, t is the number of task with max_count, which is 'A' and 'B', they both have to be executed 4 times
14+
15+
t is the left over of the last row in Figure 2 #[1]
16+
max_count-1 is the height of the Figure 2 except last row #[2]
17+
n+1 is the width of the Figure
18+
so in case2 the answer is (max_count-1)*(n+1)+t
19+
20+
in case2 there would be no way that t is 0
21+
if t is zero, that means the last row don't have idle
22+
if the last row don't have idle, there would be no idle for all the rows
23+
in that case, it is case1
24+
25+
the answer is not possible to be smaller then len(tasks)
26+
if your case2 answer is smaller than len(tasks), it is wrong
27+
the situation would be case1
28+
that is why we take the max out of two cases #[3]
29+
"""
30+
class Solution(object):
31+
def leastInterval(self, tasks, n):
32+
task_count = collections.Counter(tasks).values()
33+
max_count = max(task_count) #[2]
34+
t = task_count.count(max_count) #[1]
35+
return max(len(tasks), (max_count-1)*(n+1)+t) #[3]

0 commit comments

Comments
 (0)