Skip to content
Övningar till 7 feb
Matris
There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.
Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.
Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph looks like this:
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
1. Steps to Solve Problems
Matrix can be expanded to a graph related problem. The steps are:
(1) building a graph where the index are the node number, and the graph[i] would be a list of elements (could be other_node or a tuple or a list (other_node, weight)).
(2) Second step is to decompose the problem into subproblems.
(3) where each subproblem could be resolved by Dynamic Programming (BFS or DFS). Note: There might need some minor changes to adopt the standard algorithms.
(4) After this, we need to further thinking about how to improve the efficiency (time and space). Normally, the condition that might lead near ending of the graph algorithm.
(5) Explain the difference of the time complexity and the space complexity to the interviewers
According to this order, the above example is resolved with the following python code:
import sys
class Solution(object):
def findCheapestPrice(self, n, flights, src, dst, K):
"""
:type n: int
:type flights: List[List[int]]
:type src: int
:type dst: int
:type K: int
:rtype: int
"""
#(1). Construct Graph
#one dimension with elements to be list
graph = [[] for _ in xrange(n)]
for s,e,w in flights:
graph[s].append((e,w))
#(2) Graph Algorithm
q= [(src,0)] #stop and price
count = 0
min_price= sys.maxint #record the minimum price so far
while q:
next_stops = []
for cur, acc_price in q: #same level
for end,price in graph[cur]:
#conditional satisfied, save the price
if end==dst:
min_price = min(min_price, acc_price+price)
#(4) Cut down the complexity
#Instead of directly add the next stop, we only add those stops that have less accumulated price
if min_price>acc_price+price:
next_stops.append((end,acc_price+price) )
#(4) Instead of directly add the next stop, we only add those stops that have
if count==K:
if min_price<sys.maxint:
return min_price
else:
return -1
q=next_stops[:]
count+=1
# this is important too
if count<=K:
if min_price<sys.maxint:
return min_price
else:
return -1
Another example focusing about python code: 399. Evaluate Division
2. Graph Algorithms
(a) Represent Graph
Adjacency list: [[1,2,3],[3,1],[4,6,1]], node 0 connects to 1,2,3, node 1 connect to 3,1, node 2 connects to 4,6,1
graph = [[] for _ in xrange(nodes)]
Adjacency matrices:
graph = [[0 for _ in xrange(cols)] for _ in xrange(rows)] #normally, rows=cols
If you need a “name” for each node, and before the graph is complete, you do not know how many nodes you might get, use dictionary, for example, we are given a list of edges[[“a”,”c”],[b,c],[b,e]….]
from collections import defaultdict
d = defaultdict(set) # structure initialization
# add an edge (remember to add to both vertices!) for ver1, ver2 in edges:
d[ver1].add(ver2)graph = { "a" : ["c"],
"b" : ["c", "e"],
"c" : ["a", "b", "d", "e"],
"d" : ["c"],
"e" : ["c", "b"],
"f" : []
}
If we need weights for each edge, use dictionary from the default dictionary to represent:
graph= collections.defaultdict(dict)
for (num, den), val in zip(equations, values):
graph[num][num] = graph[den][den] = 1.0
graph[num][den] = val
graph[den][num] = 1 / val
#defaultdict(<type 'dict'>, {u'a': {u'a': 1.0, u'b': 2.0}, u'c': {u'c': 1.0, u'b': 0.3333333333333333}, u'b': {u'a': 0.5, u'c': 3.0, u'b': 1.0}})
Function to generate the list of all edges:
def generate_edges(graph):
edges = []
for node in graph:
for neighbour in graph[node]:
edges.append((node, neighbour)) return edgesprint(generate_edges(graph))
(b) Breadth-First-Search (BFS)
#implement using a queue
def BFS(root):
q = [root]
root.visited = 1
while q:
n=q.pop()
visit(n) #finish visit
for node in n.adjacent:
if not node.visited:
node.visited = 1 #start to visit
q.insert(0,node)# a mutant for trees to visit it level by level
def BFS(root):
q = [root]
root.visited = 1
level = 0
while q:
n=q.pop()
visit(n) #finish visit
for node in n.adjacent:
if not node.visited:
node.visited = 1 #start to visit
q.insert(0,node)
Or we use the library Queue:
Example of how to wait for enqueued tasks to be completed:
def worker():
while True:
item = q.get()
do_work(item)
q.task_done()q = Queue()
for i in range(num_worker_threads):
t = Thread(target=worker)
t.daemon = True
t.start()for item in source():
q.put(item)q.join()
© Depth-First-Search (DFS)
#Recursive
def DFS(root):
#END Condition
if not root:
return
visit(root)
for node in root.adjacent:
if not node.visited:
DFS(node)#Iterative, implemented using a stack
def DFS_iter():
root.visited = 1
stack = []
stack.append(root)
while stack:
n=stack.pop()
visit(n)
n.visited=1
for node in n.adjacent:
if not node.visited:
stack.append(node)
Topological Sort:
Topological Sorting vs Depth First Traversal (DFS):
In
, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices. For example, in the given graph, the vertex ‘5’ should be printed before vertex ‘0’, but unlike
, the vertex ‘4’ should also be printed before vertex ‘0’. So Topological sorting is different from DFS. For example, a DFS of the shown graph is “5 2 3 1 0 4”, but it is not a topological sortingIn
, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.# The function to do Topological Sort. It uses recursive
# topologicalSortUtil()
def topologicalSort(self):
# Mark all the vertices as not visited
visited = [False]*self.V
stack =[]# Call the recursive helper function to store Topological
# Sort starting from all vertices one by one
for i in n(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
# Print contents of stack
print stack# A recursive function used by topologicalSort
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
stack.insert(0,v)
In some cases, we need to detect cycles:
# -1:being visiting, 0: not visited, 1: done visiting
def DFS_cycle_detect(self,v,visited,stack):
if visited[v]==-1: #visiting again
return False
elif visited[v]==1: #repeated visiting
return True
visited[v] = -1 #being visiting
for i in self.graph[v]:
if visited[i] == 0: #not visited
if not self.DFS_cycle_detect(i,visited,stack):
return False
stack.insert(0,v)
visited[v]=1 #done visiting
return True
3. Examples
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
Solution: first to convert it into a graph, this is a path search, then do a DFS to find solution for this. Time complexity is O(k*(V+E)), k is the total number of queries, space complexity is O(V+E).
class Solution(object):
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
quot = collections.defaultdict(dict)
for (num, den), val in zip(equations, values):
quot[num][num] = quot[den][den] = 1.0
quot[num][den] = val
quot[den][num] = 1 / val
def DFS_iter(src, end):
stack = [(src,1.0)] #source and value
visited =set([src]) #*** set needs [src] to initialize
while stack:
cur, val = stack.pop()
if cur == end:
return val
visited.add(node) for node, w in quot[cur].items():
if not node in visited:
stack.append((node, val*w))
return -1.0res = []
for num, den in queries:
if num not in quot:
res.append(-1.0)
else:
res.append(DFS_iter(num,den))
return res
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
Do it layer by layer, like BFS, f(r1,r2,c1,c2)
Want to print your doc?
This is not the way.
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.