public
Last active

class

  • Download Gist
heap.py
Python
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
# maxheap
def maxheapify(a,i):
while i < len(a):
l,r = 2*i+1,2*i+2
m = i
if l < len(a) and a[l] > a[i]:
m = l
if r < len(a) and a[r] > a[m]:
m = r
if m == i:
break
t = a[i]
a[i] = a[m]
a[m] = t
i = m
 
def buildheap(a):
for i in reversed(range(len(a) // 2)):
maxheapify(a,i)
 
def popmax(a):
mx = a[0]
a[0] = a[-1]
a.pop()
maxheapify(a,0)
return mx
 
if __name__ == '__main__':
a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0]
print(a)
maxheapify(a,2)
print(a)
a = [4,1,3,2,16,9,10,14,8,7]
print(a)
buildheap(a)
print(a)
popmax(a)
print(a)
lcs.py
Python
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
import operator
from functools import reduce
 
def prod(seq):
return reduce(operator.mul, seq, 1)
 
def memoize(f):
d = {}
def mem(*args):
if not args in d:
d[args] = f(*args)
return d[args]
return mem
 
def chain(ps):
@memoize
def __chain__(ps):
if len(ps) == 3:
return prod(ps)
def val(k):
return __chain__(ps[:k]+ps[k+1:]) + prod(ps[k-1:k+2])
return min(map(val, range(1,len(ps)-1)))
return __chain__(ps)
 
def lcs(x,y):
@memoize
def __lcs__(a,b):
if not a or not b:
return 0
if x[a-1] == y[b-1]:
return __lcs__(a-1,b-1) + 1
return max(__lcs__(a-1,b), __lcs__(a,b-1))
return __lcs__(len(x),len(y))
 
if __name__ == '__main__':
print(lcs('brad', 'dunbar')) #2
print(lcs('abcxyzabc', 'xyzabcxyz')) #6
print(chain((10,30,5,60))) #4500

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.