Skip to content

Commit 0c053b4

Browse files
wuduhrenwuduhren
committed
no message
1 parent 2d438e1 commit 0c053b4

13 files changed

Lines changed: 645 additions & 0 deletions

‎common/bellman–ford.py‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
"""
2+
First, we use `distance` to track the distance from start to all others.
3+
For V nodes, it takes at least V-1 iteration to complete the algorithm.
4+
For every iteration,
5+
We use every node as the middle point to see if it can "loosen" the path from start to mid to mid's neighbors
6+
If it can loosen the path, we update the `distance`.
7+
The time complexity is O(VE)
8+
"""
9+
def min_path(G, N, start, end):
10+
distance = [float('inf') for _ in xrange(N+1)]
11+
distance[start] = 0
12+
13+
for _ in xrange(N-1):
14+
for mid, dis in enumerate(distance):
15+
if dis==float('inf'): continue
16+
for dis_to_nei, nei in G[mid]:
17+
distance[nei] = min(distance[nei], dis+dis_to_nei)
18+
return distance[end]
19+
20+
21+
G = {
22+
0: [(-2, 1), (4, 2)],
23+
1: [(5, 2)],
24+
2: [(12, 3), (5, 4)],
25+
3: [(-8, 4)],
26+
4: []
27+
}
28+
N = 4 #nodes count
29+
start = 0
30+
end = 4
31+
print min_path(G, N, start, end)

‎common/binary-search-tree.py‎

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
class Node(object):
2+
def __init__(self, val):
3+
self.left = None
4+
self.right = None
5+
self.val = val
6+
7+
8+
class BinarySearchTree(object):
9+
def __init__(self, val):
10+
self.root = Node(val)
11+
12+
def insert(self, val):
13+
def helper(node, val):
14+
if val>node.val:
15+
if node.right:
16+
helper(node.right, val)
17+
else:
18+
node.right = Node(val)
19+
elif val<node.val:
20+
if node.left:
21+
helper(node.left, val)
22+
else:
23+
node.left = Node(val)
24+
helper(self.root, val)
25+
# self.printTree()
26+
27+
def search(self, val):
28+
def helper(node, val):
29+
if node==None:
30+
return False
31+
elif val==node.val:
32+
return True
33+
elif val>node.val:
34+
return helper(node.right, val)
35+
elif val<node.val:
36+
return helper(node.left, val)
37+
38+
print helper(self.root, val)
39+
# self.printTree()
40+
41+
def inOrderPrint(self):
42+
def helper(node):
43+
if node.left: helper(node.left)
44+
print node.val
45+
if node.right: helper(node.right)
46+
helper(self.root)
47+
48+
def preOrderPrint(self):
49+
def helper(node):
50+
print node.val
51+
if node.left: helper(node.left)
52+
if node.right: helper(node.right)
53+
helper(self.root)
54+
55+
def postOrderPrint(self):
56+
def helper(node):
57+
if node.left: helper(node.left)
58+
if node.right: helper(node.right)
59+
print node.val
60+
helper(self.root)
61+
62+
tree = BinarySearchTree(4)
63+
tree.insert(2)
64+
tree.insert(1)
65+
tree.insert(3)
66+
tree.insert(5)
67+
tree.insert(5)
68+
tree.insert(7)
69+
70+
tree.inOrderPrint()
71+
print '====='
72+
tree.preOrderPrint()
73+
print '====='
74+
tree.postOrderPrint()
75+
print '====='
76+
77+
tree.search(3)
78+
tree.search(10)
79+
80+
81+
82+
83+
84+
85+
86+
87+
88+
89+
90+
91+
92+
93+
94+
95+
96+
97+

‎common/dijkstra.py‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
import heapq
2+
3+
"""
4+
If we only want to find the shortest distance to the end and not all the nodes's shortest distance
5+
The ending condition will be when `end` pop out from the `pq`.
6+
And the path would be all the nodes that were popped out.
7+
"""
8+
9+
#heap implementation
10+
def min_path(G, start, end):
11+
distance = {}
12+
pq = []
13+
prev = {}
14+
path_str = ''
15+
visited = set()
16+
17+
distance[start] = 0
18+
heapq.heappush(pq, (0, start))
19+
20+
while pq:
21+
dis_to_mid, mid = heapq.heappop(pq)
22+
visited.add(mid)
23+
24+
for dis, nei in G[mid]:
25+
if nei not in distance or distance[nei]>dis_to_mid+dis:
26+
distance[nei] = dis_to_mid+dis
27+
prev[nei] = mid
28+
if nei not in visited:
29+
heapq.heappush(pq, (distance[nei], nei))
30+
31+
curr = end
32+
while True:
33+
if curr not in prev: break
34+
path_str = ' -> '+prev[curr]+path_str
35+
curr = prev[curr]
36+
37+
return path_str+' = '+str(distance[end])
38+
39+
40+
41+
#normal implementation
42+
def min_path(G, start, end):
43+
distance = {} #shortest distance from start
44+
prev = {}
45+
path_str = ''
46+
visited = set()
47+
48+
distance[start] = 0
49+
while True:
50+
#find nearest unvisited node
51+
mid = None
52+
dis_to_mid = float('inf')
53+
for node in distance:
54+
if node not in visited and distance[node]<dis_to_mid:
55+
mid = node
56+
dis_to_mid = distance[node]
57+
58+
if mid==None: break
59+
visited.add(mid)
60+
61+
#try to use mid to loosen the prev from start to mid's neighbors
62+
for dis, nei in G[mid]:
63+
if nei not in distance or dis_to_mid+dis<distance[nei]:
64+
distance[nei] = dis_to_mid+dis
65+
prev[nei] = mid
66+
67+
curr = end
68+
while True:
69+
if curr not in prev: break
70+
path_str = ' -> '+prev[curr]+path_str
71+
curr = prev[curr]
72+
73+
print path_str+' = '+str(distance[end])
74+
75+
G = {
76+
'0': [(1, '1'), (12, '2')],
77+
'1': [(9, '2'), (3, '3')],
78+
'2': [(5, '4')],
79+
'3': [(4, '2'), (13, '4'), (15, '5')],
80+
'4': [(4, '5')],
81+
'5': []
82+
}
83+
84+
print min_path(G, '0', '5')
85+
86+
87+

‎common/heap-sort.py‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
def heapSort(A):
2+
#build max heap
3+
def heapify(A, n, i):
4+
if i>=n: return
5+
l, r = i*2+1, i*2+2
6+
left = A[l] if l<n else float('-inf')
7+
right = A[r] if r<n else float('-inf')
8+
9+
if left>A[i] or right>A[i]:
10+
if left>right:
11+
A[i], A[l] = A[l], A[i]
12+
heapify(A, n, l)
13+
else:
14+
A[i], A[r] = A[r], A[i]
15+
heapify(A, n, r)
16+
17+
n = len(A)
18+
19+
for i in reversed(xrange(n)):
20+
heapify(A, n, i)
21+
22+
for i in reversed(xrange(1, n)):
23+
A[i], A[0] = A[0], A[i]
24+
heapify(A, i, 0)
25+
26+
27+
28+
A = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
29+
heapSort(A)
30+
print A
31+
32+
"""
33+
Time Complexity O(NLogN) in best, average, worst case.
34+
Space Complexity O(1)
35+
"""

‎common/insertion-sort.py‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
def insertionSort(nums):
2+
for i in xrange(len(nums)):
3+
num = nums[i]
4+
j = i-1
5+
while j>=0 and num<nums[j]:
6+
nums[j+1] = nums[j]
7+
j-=1
8+
nums[j+1] = num
9+
return nums
10+
11+
12+
if __name__ == '__main__':
13+
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
14+
print insertionSort(test)
15+
16+
"""
17+
Time Complexity is O(N^2) in average and worst case. O(N) in best case.
18+
Space Complexity is O(1).
19+
"""

‎common/knapsack.py‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
def get_max_value(value, weight, max_weight):
2+
N = len(value)
3+
K = [[0 for _ in xrange(max_weight+1)] for _ in xrange(N+1)]
4+
bag = []
5+
6+
for i in xrange(N+1):
7+
for mw in xrange(max_weight+1):
8+
if i==0 or mw==0:
9+
K[i][mw] = 0
10+
continue
11+
w = weight[i-1]
12+
v = value[i-1]
13+
if w>mw:
14+
K[i][mw] = K[i-1][mw]
15+
else:
16+
K[i][mw] = max(v+K[i-1][mw-w], K[i-1][mw])
17+
18+
max_value = K[-1][-1]
19+
20+
w = max_weight
21+
i = N
22+
while i>0:
23+
if K[i][w]-K[i-1][w]>0:
24+
bag.append(i-1)
25+
w = w - weight[i-1]
26+
i = i-1
27+
28+
print 'bag: ', bag
29+
print 'max_value', max_value
30+
return max_value
31+
32+
33+
value = [60, 100, 120]
34+
weight = [10, 20, 30]
35+
max_weight = 50
36+
get_max_value(value, weight, max_weight)
37+
38+
value = [40, 100, 50, 60]
39+
weight = [20, 10, 40, 30]
40+
max_weight = 60
41+
get_max_value(value, weight, max_weight)
42+

‎common/merge-sort-in-place.py‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
def merge(A, start, mid, end):
2+
L, R = A[start:mid], A[mid:end]
3+
i = j = 0
4+
k = start
5+
for l in xrange(k,end):
6+
if j>=len(R) or (i<len(L) and L[i]<R[j]):
7+
A[l] = L[i]
8+
i = i+1
9+
else:
10+
A[l] = R[j]
11+
j = j+1
12+
13+
def mergeSort(A, p, r):
14+
if r - p > 1:
15+
mid = (p+r)/2
16+
mergeSort(A, p, mid)
17+
mergeSort(A, mid, r)
18+
merge(A, p, mid, r)
19+
20+
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
21+
mergeSort(A, 0, len(A))
22+
print A

0 commit comments

Comments
 (0)